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;
  }

Answer 3

This is not a full solution but a guide in the right direction. I faced a very similar problem just recently and I found a reddit post with an answer (https://www.reddit.com/r/DnDBehindTheScreen/comments/8efeta/a_random_star_chart_generator/dxvlsyt/) suggesting to use Delaunay triangulation which basically returns a solution with all possible triangles made within the data points you have. Once you have all possible triangles, which by definition you know won't result on any overlapped lines, you can chose which lines you use which result on all nodes being connected.

I was coding my solution on python and fortunately there's lots of scientific libraries on python. I was working on a random sky chart generator which would draw constellations out of those stars. In order to get all possible triangles (and draw them, just for fun), before going into the algorithm to draw the actual constellations, all I had to do was this:

    # 2D array of the coordinates of every star generated randomly before
    points = list(points_dict.keys())
        
    from scipy.spatial import Delaunay
    tri = Delaunay(points)
    
    # Draw the debug constellation with the full array of lines
    debug_constellation = Constellation(quadrants = quadrants, name_display_style = config.constellation_name_display_style)
    for star in available_stars:
        debug_constellation.add_star(star)
    for triangle in tri.simplices:
        star_ids = []
        for index in triangle:
            star_ids.append(points_dict[points[index]].id)
        debug_constellation.draw_segment(star_ids, is_closed = True)

    # Code to generate the image follows below

You can see the full implementation here: fake_sky_chart_generator/fake_libs/constellation_algorithms/delaunay.py

This is the result: