title: Sort a set of coplanar 3d points in a desired order
body: <p>I have a set of three-dimensional points that all lie in the same plane.  The points are simply "x y z" entries in a text file.  <strong>I would like to find a way to sort these points so that I could draw a simple polygon through all the points</strong>.  I had several ideas:</p>
  
  <p><strong>Idea 1:</strong> Pick a point known to lie inside the polygon that is defined by the set of points and draw a ray to an arbitrary point in the set.  Then use an angular function of some sort to find the closest point <em>by angle</em> to the first one, then so on for all the rest.  The problem with this idea is that I don't know how to find a point that is guaranteed to be inside the region.  I wanted to use the centroid, but not all of these sets are going to be convex.  They could look like either of the following two images:</p>
  
  <p><a href="https://i.stack.imgur.com/ouhdW.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ouhdW.png" alt="enter image description here"></a></p>
  
  <p>As you can see in the second image, the centroid may not lie inside the polygon, and actually if the turning point is too steep in the corner there the angular function that I had in mind might not work either.</p>
  
  <p><strong>Idea 2:</strong> This seems like one of the easier problems that could be solved according to something like the Traveling Salesman problem.  But I know there are lots of different particular solutions and approximations to solving TSPs and I am a bit rusty on where to begin.</p>
  
  <p><strong>Idea 3:</strong> Use a simple distance function that would start with an arbitrary point and find the the point that is closest to it, then find the point (not one already found) closest to <em>that</em> and so on.  This seems like the easiest one to do but I wonder if I am not forseeing any problems that arise.</p>
  
  <p>I would appreciate any input as to the best way to solve this, and whether I am overlooking an even simpler method.  I am programming this in C++ so another good answer would include libraries or functions that can do things like find a 3d centroid, or solve a TSP, etc.  Thanks in advance for your help.</p>