algorithm - Sorting Geographical non-contiguous line segments along an implied curve -

given:

a set (for sake of discussion call s), unordered collection of line segments. each line segment defined 2 longitude-latitude end-points. while of line segments follow implied curve, there "gaps" between each of segments, of various sizes. refer curve "implied" because not explicitly defined anywhere. information have available line segments contained within s.

desired result:

a sequence (for sake of discussion call r), ordered collection of line segments. each line segment defined before, following same implied curve before sorted position along implied curve.

context (i.e. "why in heck need this?"):

basically have incomplete geographical data needs normalized , "completed" doing simple interpolation form complete curve no gaps. might ask "why not fit curve line segment end-points , done it?" -- well, that's not quite after. line segments precisely should located, , there no need final curve "smooth". in fact, intend connect each of segments straight-line (the crudest form of interpolation imaginable). but, connecting segments easy; hard part sorting them.

so in summary: performant algorithm going s r?

you can use k-d tree or cover tree find nearby points quickly.

if need 1 continuous curve, suggest short traveling salesman path incorporates given edges reasonable reconstruction. use 2-opt k-d tree way bentley described (paywalled, sorry; think there's description in this chapter on tsp local search johnson , mcgeoch). 1 modification needed ensure initial path includes given edges , 2-opt moves not remove edges.