Given:
A Set (for the sake of discussion we will call it S
), which is an unordered collection of line segments. Each line segment is defined as two Longitude-Latitude end-points. While all of the line segments follow an implied curve, there are "gaps" between each of the segments, of various sizes. We refer to this curve as "implied" because it is not explicitly defined anywhere. The only information that we have available are the line segments contained within S
.
Desired Result:
A sequence (for the sake of discussion we will call it R
), which is an ordered collection of line segments. Each line segment is defined just as before, following the same implied curve as before but are now sorted by their position along the implied curve.
Context (i.e. "Why in the heck do I need this?"):
Basically I have incomplete geographical data that needs to be normalized and "completed" by doing some very simple interpolation to form a complete curve with no gaps. You might ask "why not just fit a curve to all the line segment end-points and be done with it?" -- well, that's not quite what I am after. The line segments are precisely where they should be located, and there is no need for the final curve to be "smooth". In fact, I intend to connect each of the segments with a straight-line (the crudest form of interpolation imaginable). But, connecting the segments is easy; the hard part is sorting them.
So In Summary: What would be a performant algorithm for going from S
to R
?