Skip to content

Instantly share code, notes, and snippets.

@grapefrukt
Created December 1, 2014 17:35
Show Gist options
  • Save grapefrukt/a4031af2a1a7bc5caaea to your computer and use it in GitHub Desktop.
Save grapefrukt/a4031af2a1a7bc5caaea to your computer and use it in GitHub Desktop.
package com.grapefrukt.games.slicer.utils;
/**
* ...
* @author Martin Jonasson, m@grapefrukt.com
*/
class ConvexHull {
public static function get<T:{x:Float, y:Float}>(vertices:Array<T>):Array<T> {
// code derived from http://notejot.com/2008/11/convex-hull-in-2d-andrews-algorithm/
var pointsHolder = [];
// need to filter out duplicates 1st
for (i in 0 ... vertices.length) {
var d:Float = 1;
// for (j = 0;(d > 0) && (j < pointsHolder.length); j++)
var j = 0;
while ((d > 0) && (j < pointsHolder.length)) {
d *= distance(vertices[i], pointsHolder[j]);
j++;
}
if (d > 0) {
pointsHolder.push(vertices[i]);
}
}
var topHull = [];
var bottomHull = [];
// triangles are always convex
if (pointsHolder.length < 4) return pointsHolder;
// lexicographic sort
pointsHolder.sort(_sort);
// compute top part of hull
topHull.push(0);
topHull.push(1);
//for (i = 2;i < pointsHolder.length; i++) {
for (i in 2 ... pointsHolder.length) {
if (towardsLeft(pointsHolder[topHull[topHull.length - 2]], pointsHolder[topHull[topHull.length - 1]], pointsHolder[i])) {
topHull.pop();
while (topHull.length >= 2) {
if (towardsLeft(pointsHolder[topHull[topHull.length - 2]], pointsHolder[topHull[topHull.length - 1]], pointsHolder[i])) {
topHull.pop();
} else {
topHull.push(i);
break;
}
}
if (topHull.length == 1)
topHull.push(i);
}
else
{
topHull.push(i);
}
}
// compute bottom part of hull
bottomHull.push(0);
bottomHull.push(1);
//for (i = 2;i < pointsHolder.length; i++)
for (i in 2 ... pointsHolder.length) {
if (!towardsLeft(pointsHolder[bottomHull[bottomHull.length - 2]], pointsHolder[bottomHull[bottomHull.length - 1]], pointsHolder[i])) {
bottomHull.pop();
while (bottomHull.length >= 2) {
if (!towardsLeft(pointsHolder[bottomHull[bottomHull.length - 2]], pointsHolder[bottomHull[bottomHull.length - 1]], pointsHolder[i])) {
bottomHull.pop();
} else {
bottomHull.push(i);
break;
}
}
if (bottomHull.length == 1) bottomHull.push(i);
} else {
bottomHull.push(i);
}
}
bottomHull.reverse();
bottomHull.shift();
// convert to Polygon2D format
var ix = topHull.concat(bottomHull);
var vs = [];
for (i in 0 ... ix.length - 1) vs.push(pointsHolder[ix[i]]);
return vs;
}
static private function _sort<T:{x:Float, y:Float}>(a:T, b:T) {
if (a.x > b.x) return 1;
if (a.x < b.x) return -1;
if (a.y > b.y) return 1;
if (a.y < b.y) return -1;
return 0;
}
/**
* Used by convexHull() code.
*/
static function towardsLeft<T:{x:Float, y:Float}>(origin:T, p1:T, p2:T):Bool {
// funny thing is that convexHull() works regardless if either < or > is used here
//return (new Polygon2D([origin, p1, p2]).area() < 0);
return area([origin, p1, p2]) < 0;
}
static public function area<T:{x:Float, y:Float}>(vertices:Array<T>) {
var a:Float = 0;
var n = vertices.length;
for (i in 0 ... n) a += vertices[i].x * vertices[(i + 1) % n].y - vertices[(i + 1) % n].x * vertices[i].y;
return 0.5 * a;
}
static function distance<T:{x:Float, y:Float}>(a:T, b:T):Float {
var cX:Float = a.x - b.x;
var cY:Float = a.y - b.y;
return Math.sqrt(cX*cX + cY*cY);
}
// stolen from: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
static public function containsPoint<T:{x:Float, y:Float}>(vertices:Array<T>, p:T):Bool {
var c = false;
var j = vertices.length - 1;
for (i in 0 ... vertices.length) {
if (((vertices[i].y > p.y) != (vertices[j].y > p.y)) && (p.x < (vertices[j].x - vertices[i].x) * (p.y - vertices[i].y) / (vertices[j].y - vertices[i].y) + vertices[i].x)) {
c = !c;
}
j = i;
}
return c;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment