AS3 – Creating a Convex Polygon from Unordered Points

Let’s pretend you have an application that lets users create shapes to be used in a physics simulation and that the user must click on the screen to set the vertices of the shape. Many physics engines only support convex polygons, or shapes that don’t have inlets, bites, or coves, basically shapes that don’t have inward facing edges. With this limitation we have to be able to restrict [read as "guide"] the user to make only convex polygons. For this we are going to need an algorithm that takes an unordered set of points and finds the convex hull that encloses those points. This way the user can click and add points at random, if desired, and your program will keep track of what points create a convex polygon, while the others are thrown away [or dealt with however you see fit].

The Graham Scan Algorithm is a process of ordering a random set of points and then calculating jumps to the points in that set that constitute a convex polygon. In this algorithm there are three steps. First is to find a corner point, usually the topmost, leftmost point in the set. The second step is to order all other points by the polar angle between the corner point and the point in question. The last step is to traverse the set, taking each proceeding subset of three points (n, n-1, n-2) to determine whether the angle made by these three points is a left turn, right turn, or a straight line. If the turn made is our desired turn [which is usually left - but in Flash it's right, due to the flipped y-axis] then we add that point to the convex hull. If the turn is not our desired turn, we get rid of that point and move on.

Here is an example that shows first the data set drawn from point to point. Each successive line gets progressively whiter. In the second step we find the corner point, order the other points and then show the outer polygon.

Example

Example

Here’s the code for the class:

/**
 *  Use this class freely - 2009 blog.efnx.com
 */


package
{
    import flash.geom.Point;
   
public class GrahamScan extends Object
{
    /**
     *  The Graham scan is a method of computing the convex hull of a finite set of points
     *  in the plane with time complexity O(n log n). It is named after Ronald Graham, who
     *  published the original algorithm in 1972. The algorithm finds all vertices of
     *  the convex hull ordered along its boundary. It may also be easily modified to report
     *  all input points that lie on the boundary of their convex hull.
     */

   
    public function GrahamScan()
    {
        super();
    }
   
    /**
     *  Returns a convex hull given an unordered array of points.
     */

    public static function convexHull(data:Array):Array
    {
        return findHull( order(data) );
    }
    /**
     *  Orders an array of points counterclockwise.
     */

    public static function order(data:Array):Array
    {
        trace("GrahamScan::order()");
        // first run through all the points and find the upper left [lower left]
        var p:Point = data[0];
        var n:int   = data.length;
        for (var i:int = 1; i < n; i++)
        {
            //trace("   p:",p,"d:",data[i]);
            if(data[i].y < p.y)
            {
                //trace("   d.y < p.y / d is new p.");
                p = data[i];
            }
            else if(data[i].y == p.y && data[i].x < p.x)
            {
                //trace("   d.y == p.y, d.x < p.x / d is new p.");
                p = data[i];
            }
        }
        // next find all the cotangents of the angles made by the point P and the
        // other points
        var sorted  :Array = new Array();
        // we need arrays for positive and negative values, because Array.sort
        // will put sort the negatives backwards.
        var pos     :Array = new Array();
        var neg     :Array = new Array();
        // add points back in order
        for (i = 0; i < n; i++)
        {
            var a   :Number = data[i].x - p.x;
            var b   :Number = data[i].y - p.y;
            var cot :Number = b/a;
            if(cot < 0)
                neg.push({point:data[i], cotangent:cot});
            else
                pos.push({point:data[i], cotangent:cot});
        }
        // sort the arrays
        pos.sortOn("cotangent", Array.NUMERIC | Array.DESCENDING);
        neg.sortOn("cotangent", Array.NUMERIC | Array.DESCENDING);
        sorted = neg.concat(pos);
       
        var ordered :Array = new Array();
            ordered.push(p);
        for (i = 0; i < n; i++)
        {
            if(p == sorted[i].point)
                continue;
            ordered.push(sorted[i].point)
        }
        return ordered;
    }
    /**
     *  Given an array of points ordered counterclockwise, findHull will
     *  filter the points and return an array containing the vertices of a
     *  convex polygon that envelopes those points.
     */

    public static function findHull(data:Array):Array
    {
        trace("GrahamScan::findHull()");
        var n   :int    = data.length;
        var hull:Array  = new Array();
            hull.push(data[0]); // add the pivot
            hull.push(data[1]); // makes first vector
           
        for (var i:int = 2; i < n; i++)
        {
            while(direction(hull[hull.length - 2], hull[hull.length - 1], data[i]) >= 0)
                hull.pop();
            hull.push(data[i]);
        }
       
        return hull;
    }
    /**
     *
     */

    private static function direction(p1:Point, p2:Point, p3:Point):Number
    {
        // > 0  is right turn
        // == 0 is collinear
        // < 0  is left turn
        // we only want right turns, usually we want right turns, but
        // flash's grid is flipped on y.
        return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
    }
}

}

Tags: , ,

10 Responses to “AS3 – Creating a Convex Polygon from Unordered Points”

  1. [...] Regarding the problem of concave polys and vertex limits I found a great AS3 class for polygon triangulation over here: http://actionsnippet.com/?p=1462 That class takes a polygon and spits out a bunch of triangles, which when put together assumes the same hull shape as the original polygon. This solved a lot of my problems. However, triangulation does not work when there are overlapping segments in the polygon, which might easily be the case when one jots a bunch of lines on the screen in no particular order. So I needed something to make order from that kind of mess. What I found was the Graham scan algorithm, neatly converted to AS3 at http://blog.efnx.com/as3-creating-a-convex-polygon-from-unordered-points/ [...]

  2. You cannot believe how long ive been searching for something like this. Scrolled through 8 pages of Google results and couldn’t find anything. Very first page on Bing. There this is… Gotta start using this more often

  3. Kevin Tanadi Says:

    In the code : “while(direction(hull[hull.length - 2], hull[hull.length - 1], data[i]) > 0)”
    it should be “while(direction(hull[hull.length - 2], hull[hull.length - 1], data[i]) >= 0)”

    because if there are two nodes with same position (same x, and y), it will still be included in the result..

  4. Ah, yes thanks! Must have been an artifact from flash’s flipped cartesian coordinates, since in this case we only want left hand turns, not right hand, nor collinear.

  5. Nice script! i was searching exactly this one!!

  6. Me too! Wow – typed in ‘forming a convex polygon from unordered points’ came straight here, and got it working on AS3 in 2 mins. Thanks so much Schell! Really appreciate it.

  7. No prob, I’m glad it worked.

  8. Hi Schell, you really saved my day ;) Now I just need to draw a smooth curved outline around those points. Thanks a lot for sharing this peace of code!!

  9. One problem I ran into using this code is when some of those points have the same angle. Do you have a solution for the following coords:
    (x=0, y=0),(x=510, y=0),(x=510, y=419),(x=0, y=419),(x=0, y=423),(x=168, y=423),(x=168, y=538),(x=0, y=538)

  10. Feonyx – Meaning they have the same angle with respect to the corner point? If that’s the case, the point that gets picked *should* be whichever one is furthest from the corner point…is this what is happening?

Leave a Reply


Follow me on GitHub
Follow me on Google+
Follow me on Twitter
Thrilling.
EFNX is proudly powered by WordPress
Entries (RSS) and Comments (RSS).