ConvexHull.hx

package com.grapefrukt.games.slicer.utils;

/**
 * ...
 * @author Martin Jonasson, [email protected]
 */

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;
	}
	
}