algorithm - 沿隐含曲线对地理上不连续的线段进行排序

Question

给定:

一个集合(为了便于讨论，我们将其称为 S)，它是一个无序线段集合。每条线段定义为两个经纬度端点。虽然所有的线段都遵循隐含的曲线，但每个线段之间存在各种大小的“间隙”。我们将此曲线称为“隐含”，因为它没有在任何地方明确定义。我们唯一可用的信息是 S 中包含的线段。

期望的结果:

一个序列(为了便于讨论，我们将其称为 R)，它是一个有序线段集合。每条线段都像以前一样定义，遵循与以前相同的隐含曲线，但现在按它们沿隐含曲线的位置排序。

上下文(即“我到底为什么需要这个？”):

基本上，我有不完整的地理数据，需要通过一些非常简单的插值来规范化和“完成”，以形成一条没有间隙的完整曲线。您可能会问“为什么不直接将曲线拟合到所有线段端点并完成它呢？” ——好吧，这不是我想要的。线段恰好在它们应该在的位置，最终的曲线不需要“平滑”。事实上，我打算用一条直线连接每个线段(可以想象的最粗略的插值形式)。但是，连接线段很容易；困难的部分是对它们进行分类。

总结:从 S 到 R 的高性能算法是什么？

Answer 1

您可以使用 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 移动不会删除这些边。