Convex Hull

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:

[kml_flashembed movie=”http://www.bit-101.com/blog/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

This entry was posted in ActionScript. Bookmark the permalink.

10 Responses to Convex Hull

  1. For comparison,

    http://www.lostinactionscript.com/blog/index.php/2007/06/12/convex-hull-algorithms-for-actionscript/

    It’s good to have an ever-growing body of knowledge and example codes in this area.

    regards,

    – jim

  2. lenny says:

    neat, very nice. thanks for sharing keith.

  3. nice implementation.

    I´ve played with Voronoi Diagrams recently…
    http://www.dasprinzip.com/prinzipiell/2008/08/25/voronoi-tesselations/

    (really looking forward for the 25lines “contest”, even if voronoi´s don´t fit into 25 lines… 😉

    cheers,
    -frank

  4. kp says:

    Frank, yeah I actually ran across your site a few days ago looking at Voronoi stuff. That looks pretty nice. I’d love to see how you are doing it.

  5. Matt says:

    Interesting,
    a few months ago I was in the need of a convex hull algorithm and ported a java implementation to as3. I also did some experiments with convex hull shrinking, unfortunately it was awful slow. Someone should do a package with those algorithms they’re really useful, also concave hull algorithms would be very interesting to see.
    You can check out my approach here: http://www.roawr.com/convexhull/
    It uses the Jarvis March algorithm which isn’t the fastest but easy to code.

  6. Cool! I was doing that last summer (needed to get delaunay triangulation for swf>xna), and yeah, that site is the best : ). I ended up with C# code to do it, great to see this happening in flash (C# is great, and fast, but tends to sit on your hard drive waiting for a friend — unlike flash).

    I also tried it with shaders (trying to get flash running on the gpu). That very quickly devolved into hours of totally useless animation tweaking, so fun. Shaders remind me of flash in that way, but oh man can you do a lot on there!

    I think the code is in these links, it is mostly JS based, but probably flash would need a totally more suitable approach as you are doing anyway. Very cool to see this, the flash player certainly has come a long way eh?

    http://blog.debreuil.com/archive/2007/07/19/5325.aspx
    http://blog.debreuil.com/archive/2007/07/20/5332.aspx

  7. Thx Keith,

    in the moment I´m boosting up the performance of my calculations, so let me just optimize the code a bit more and I´ll send you the sources in a view days (promised!). 😉

  8. Rothrock says:

    Your blog got me interested in this. And I found this website: http://geometryalgorithms.com/Archive/algorithm_0109/algorithm_0109.htm

    They have a real interesting way of doing the part that you are doing with atan2. It seems like it might be a faster way to do it. They give it as a function, but it could easily be inlined. I think. Here is their C++ implementation.

    // isLeft(): tests if a point is Left|On|Right of an infinite line.
    // Input: three points P0, P1, and P2
    // Return: >0 for P2 left of the line through P0 and P1
    // =0 for P2 on the line
    // <0 for P2 right of the line
    // See: the January 2001 Algorithm on Area of Triangles
    inline float
    isLeft( Point P0, Point P1, Point P2 )
    {
    return (P1.x – P0.x)*(P2.y – P0.y) – (P2.x – P0.x)*(P1.y – P0.y);
    }

  9. …so, as announced last September, I now have rewritten my complete Voronoi Classes and updatet a few methods to Flash10. Now it all actually runs up to 5 times faster than before.

    http://www.dasprinzip.com/prinzipiell/2008/12/17/voronoi-and-vectors/

Leave a Reply