Convex Hull

Sep 08 2008 Published by under ActionScript

Send to Kindle

In my quest for information on Voronoi, I was led here: http://www.cs.berkeley.edu/~jrs/274/, and found some stuff on Convex Hulls that looked interesting. So I created this, just click away, hit a key to clear:

A convex hull is the smallest convex polygon containing all the points in a set. You can also say that if you banged a nail into each pont and then wrapped a string around all the nails, you’d get the convex hull for that set.

Crappy timeline code below. I’m not sure how “standard” my solution is. I started reading about the winding method, had an epiphany of how that would work in AS, and abandoned reading to start coding. And it worked.

[SWF(width = 500,height = 500, backgroundColor=0xcccccc)]

var points:Array = new Array();
stage.addEventListener(MouseEvent.CLICK, onClick);
stage.addEventListener(KeyboardEvent.KEY_UP, onKey);
function onClick(event:MouseEvent):void
{
	var p:Point = new Point(mouseX,mouseY);
	points.push(p);
	graphics.clear();
	drawPoints();
	var hull:Array = convexHull(points);
	drawHull(hull);
}

function onKey(event:KeyboardEvent):void
{
	graphics.clear();
	points = new Array();
}

function convexHull(points:Array):Array
{
	points.sortOn("x", Array.NUMERIC);
	var point:Point = points[0] as Point;
	var hull:Array = new Array();
	var angle:Number = Math.PI / 2;
	while (point != hull[0])
	{
		hull.push(point);
		var bestAngle:Number = Number.MAX_VALUE;
		var bestIndex:int;
		for (var i:int = 0; i < points.length; i++)
		{
			var testPoint:Point = points[i] as Point;
			if (testPoint == point)
			{
				continue;
			}
			var dx:Number = testPoint.x - point.x;
			var dy:Number = testPoint.y - point.y;
			var testAngle:Number = Math.atan2(dy,dx);
			testAngle -= angle;
			while (testAngle < 0)
			{
				testAngle+=Math.PI*2;
			}
			if (testAngle<bestAngle)
			{
				bestAngle=testAngle;
				bestIndex=i;
			}
		}
		point=points[bestIndex];
		angle+=bestAngle;
	}
	return hull;
}

function drawHull(hull:Array):void
{
	graphics.lineStyle(0);
	graphics.moveTo(hull[0].x, hull[0].y);
	for(var i:int = 1; i < hull.length; i++)
	{
		graphics.lineTo(hull[i].x, hull[i].y);
	}
	graphics.lineTo(hull[0].x, hull[0].y);
}

function drawPoints():void
{
	for (var i:int = 0; i < points.length; i++)
	{
		var p:Point=points[i] as Point;
		graphics.beginFill(0);
		graphics.drawCircle(p.x, p.y, 2);
		graphics.endFill();
	}
}
Send to Kindle

12 responses so far

Leave a Reply