I have a set of (x,y) data points which describe an envelope or wiggly line. That is for certain x values, there are more than one y values, and for certain y values there are more than one x value.
A circle is an example of this, although my data describes an open version of a squashed version of a circle.
I would like to sort this data such that each data point follows the one before, much like following a point around the circumference of the circle from one point around the circle back to itself, although in my case it does not have to come back to the start. I just need to sort all the data points such that I follow the curve from the start to end.
Obviously sorting by x value or y value does not work. Are there any algorithms to sort the data points the way I require?
Assuming that these points are so numerous that for any given point, the nearest distinct points are on the same section of your expected curve than a different section, you may use a greedy algorithm used in the travelling salesman problem.
Select any point as the first in a list. Now for the latest point on the list, calculate the Euclidean distance to all other points that are not currently on the list; you can make his more efficient by limiting the comparisons based on a maximum difference in either or both coordinates. Select the point thus described with the least such distance and add it to the list. Repeat this until all points are on the list.
Note that if a point lies too far from the expected curve, it may be "skipped" by this algorithm and then placed at the end of the list. Orientation of the list is also not determined, except by the point chosen first, since this algorithm will (almost) always move in a single direction.