How to draw a polygon from a set of unordered points

Question

Currently, I am using a convex hull algorithm to get the outer most points from a set of points randomly placed. What I aim to do is draw a polygon from the set of points returned by the convex hull however, when I try to draw the polygon it looks quite strange.

My question, how do I order the points so the polygon draws correctly?

Thanks.

EDIT:

Also, I have tried sorting using orderby(...).ThenBy(...) and I cant seem to get it working.

Answer 1

Have you tried the gift wrapping algorithm ( http://en.wikipedia.org/wiki/Gift_wrapping_algorithm)? This should return points in the correct order.

Answer 2

I had an issue where a random set of points were generated from which a wrapped elevation vector needed a base contour. Having read the link supplied by @user1149913 and found a sample of gift-wrapping a hull, the following is a sample of my implementation:

  private static PointCollection CalculateContour (List<Point> points) {
     // locate lower-leftmost point
     int hull = 0;
     int i;
     for (i = 1 ; i < points.Count ; i++) {
        if (ComparePoint(points[i], points[hull])) {
           hull = i;
        }
     }

     // wrap contour
     var outIndices = new int[points.Count];
     int endPt;
     i = 0;
     do {
        outIndices[i++] = hull;
        endPt = 0;
        for (int j = 1 ; j < points.Count ; j++)
           if (hull == endPt || IsLeft(points[hull], points[endPt], points[j]))
              endPt = j;
        hull = endPt;
     } while (endPt != outIndices[0]);

     // build countour points
     var contourPoints = new PointCollection(points.Capacity);
     int results = i;
     for (i = 0 ; i < results ; i++)
        contourPoints.Add(points[outIndices[i]]);
     return contourPoints;
  }