How to sort (x,y) points on a plane

413 Views Asked by At

I have a set of points on a plane $(x,y)$ which form a bounded region. I need to sort the points in order as they appear while moving around the boundary of the region, starting at some user specified point. My current algorithm looks for the closest point, and adds that, etc. The trouble is that this fails when there is a sharp or pinch section, and the closest data point might not be the logical next one in the boundary line, so it skips over those points.

Are there any other algorithms I could use to get around this problem? region with a pinch

Here is a simpler version which exhibits the problem and where it is more obvious than the above what it should look like if you remove the lines: more obvious example