Given:
Set（为了便于讨论，我们将其称为 S ），这是一个 unordered 线段集合 . 每个线段定义为两个经度 - 纬度 endpoints . 虽然所有线段都遵循隐含曲线，但每个线段之间有各种尺寸的"gaps" . 我们将此曲线称为"implied"，因为它未在任何地方明确定义 . 我们唯一可用的信息是 S 中包含的线段 .
Desired Result:
一个序列（为了讨论起见，我们将其称为 R ），这是一个 ordered 行段集合 . 每个线段的定义与之前一样，遵循与之前相同的隐含曲线，但现在是 sorted by their position along the implied curve .
Context (i.e. "Why in the heck do I need this?"):
基本上我有不完整的地理数据，需要进行标准化，并通过一些非常简单的插值来形成一个没有间隙的完整曲线 . 你可能会问"why not just fit a curve to all the line segment end-points and be done with it?" - 嗯，那不是我所追求的 . 线段正好位于它们应该位于的位置，并且最终曲线不需要"smooth" . 实际上，我打算用直线（可以想象的最粗略的插值形式）连接每个段 . 但是，连接段很容易;困难的部分是对它们进行排序 .
So In Summary: What would be a performant algorithm for going from S to R?
2 回答
您可以使用k-d tree或cover tree快速查找附近的点 .
如果你需要一条连续的曲线，我建议一个包含给定边的短的traveling salesman路径将是一个合理的重建 . 您可以将2-opt与k-d树一起使用Bentley described（管道，抱歉;我认为this chapter on TSP local search by Johnson and McGeoch中也有描述） . 所需的一个修改是确保初始路径包括给定边缘并且2-opt移动不会移除那些边缘 .
我猜隐含的曲线有两个属性 . 一个是持续的，这意味着没有细分 . 其次，它的一阶导数是连续的，这意味着没有角落 .
从第二个属性我们可以说，如果两条线之间的角度彼此更接近，它们就更相关 . 但我想这还不够 . 您可以定义成本函数，该函数取决于线条之间的角度和线条的距离 .
C = Aangle + Bdistance （其中A，B应进行测试和调整）
通过此功能，您可以找到每条线与另一条线相关的线数 . 比你可以简单地连接具有最强关系的线 . 虽然我猜贪婪的算法并不意味着你将始终获得最佳解决方案 .