In my quest for information on Voronoi, I was led here: https://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:
[kml_flashembed movie=“https://www.bit-101.com/2003/wp-content/uploads/2008/09/convexhull.swf” height=“500″ width=“500″ /]
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.
[php lang=“actionscript”][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(); } }[/php]