沿着暗示的曲线排序地理非连续线段

Question

给定：

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

期望结果：

一个序列（我们将其称为R），它是一组有序的线段。每个线段与之前相同，仍然遵循相同的隐含曲线，但现在按照它们沿着隐含曲线的位置排序。

背景（即“为什么我需要这个？”）：

基本上，我有不完整的地理数据，需要通过进行一些非常简单的插值来进行归一化和“完成”，以形成一个完整的曲线，其中没有间隙。您可能会问“为什么不只是将曲线拟合到所有线段的端点并完成它？”——嗯，这不是我想要的。线段正好位于它们应该位于的位置，最终曲线不需要“平滑”。事实上，我打算用直线连接每个线段（最粗糙的插值形式）。但是，连接线段很容易，难的部分是排序。

因此，总结一下：从S到R的高效算法是什么？

- Ryan Delucchi

---

曲线可以是任何形状吗？也许你可以发布一张S的图片来展示它的样子？ - angelatlarge

想象一条远足小径：基本上你已经有了它。非常紧密的弯道不太可能成为曲线的一部分，并且假设尖锐的拐角根本不存在。 - Ryan Delucchi

你有没有考虑过简单地获取一条线段上的点到另一条线段上的点之间的最短距离？而与原始点距离最短的线段将成为R中的下一条线段。这可能是n^2。太慢了吗？ - masotann

我希望我能做得比O(n^2)更好。 - Ryan Delucchi

@RyanDelucchi：从侧面还是从顶部开始徒步旅行？如果从侧面开始，那么一切都可以按照x轴排序，但我认为你的问题肯定更加棘手，对吧？你试图找到段的组合，使得曲线看起来最不混乱，是吗？ - angelatlarge

曲线已固定，线段位于特定位置（换句话说：曲线和线段已经预定义）。我试图确定这些线段沿曲线的顺序。 - Ryan Delucchi

Answer 1

您可以使用k-d树或覆盖树快速找到附近的点。

如果您需要一个连续的曲线，我建议使用包含给定边的短旅行商路径作为合理的重构。您可以使用2-opt和k-d树，就像Bentley描述的那样（需要付费，抱歉；我认为在Johnson和McGeoch关于TSP局部搜索的这章中也有描述）。唯一需要修改的是确保初始路径包括给定的边，并且2-opt移动不会删除这些边。

- David Eisenstat

---

k-d树听起来是一个很好的方法。至于连接线段，我认为直接连边对于我的情况可能已经足够了（因为数据中的间隙非常强烈地表明准确性不是那么重要）。事实证明，我已经在使用恒定时间分桶方案来细分我的表面区域，因此我可以选择将k-树限制在单个存储桶（或一系列存储桶）中。这将创建这些k-d树大小的上限。我会进一步研究并稍后报告。 - Ryan Delucchi

Answer 2

我猜测暗含的曲线具有两个特性。其一是连续的，这意味着没有分段。其二，其一阶导数是连续的，这意味着没有拐角。

从第二个属性可以看出，如果两条直线之间的夹角越接近，它们就越相关。但我认为这还不够。您可以定义一个成本函数，该函数取决于线之间的角度和距离。

C = A*angle + B*distance（其中A、B应进行测试和调整）

从这个函数中，您可以找到每条线与另一条线的关系程度。然后，您只需简单地连接与最强关系的线。虽然我认为贪心算法并不意味着您总会得到最优解。

- Gorkem

---

这实际上与我早期的一个想法非常相似，但有两个问题：1）你仍然需要计算每对线段之间的距离问题；2）线段之间的角度并不相关于线段是否应该连接。 - Ryan Delucchi

我不同意你关于角度的观点。它们提供了一些提示，但随着距离的增加，它们的含义很快就会丢失。因此，找到正确的成本函数是一个问题，它可能不像我所说的那样是线性的。关于复杂性的一般规则：如果n不高，大多数情况下不用担心 :) 但是如果n很高，您应该检查空间分割算法，我的最爱是http://en.wikipedia.org/wiki/Bin_%28computational_geometry%29，在最好的情况下为O(1)。 - Gorkem

我实际上正在处理一组非常庞大的数据，因此n非常高（想想OpenStreetMap数据 ;-))。但是，你提出的角度在短距离内更有意义的观点很好。由于我还使用了恒定时间桶分割空间的方案，因此在这些桶内结合角度的想法实际上可能非常有帮助。看起来kd-tree是解决这个问题的一个强有力的候选者。 - Ryan Delucchi

我实际上不得不把这个项目搁置一边（因为在做其他事情），但现在我再次研究它，我更倾向于使用“Bin”算法，而且我甚至可能会考虑角度和距离...敬请期待 :-) - Ryan Delucchi