Convex Hull

Sep 08 2008 Published by keith under ActionScript

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.

[as][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=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();
}
}[/as]

12 responses so far

Leave a Reply