排序地理不连续的线段沿着一个隐含的曲线 [英] Sorting Geographical non-contiguous line segments along an implied curve

问题描述

考虑：

一个集（为便于讨论，我们将其称为取值），这是一个 无序收集线段。每个线段被定义为两个经纬度端点。而所有的线段按照隐含的曲线中，有每个段之间的差距各种尺寸的，。我们把这种曲线的暗示的，因为它没有明确定义的任何地方。我们有可用的唯一信息是包含在取值线段。

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.

所需的结果：

一个序列（为了讨论的方便，我们将其称为研究），这是一个 订购收集线段。每一个线段是指像以前一样，遵循同样的隐含曲线之前，但​​现在的排序由他们沿隐含的曲线位置

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.

上下文（即为什么在赫克我需要这个？）：

基本上我有需要是不完整的地理数据的归的和完成做一些非常简单的插值，形成一个完整的曲线的没有的差距。你可能会问：为什么不只是曲线拟合所有线段端点，并用它做？ - 嗯，这不是完全是我后。线段是precisely他们应该被定位，并且也没有必要对最终曲线是光滑。事实上，我打算用直线（插值可以想象的最原始的形式）连接各个节段。但是，连接部分很容易;最困难的部分是对它们进行排序。

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?

推荐答案

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

You can use a k-d tree or a cover tree to find nearby points quickly.

如果你需要一个连续的曲线，我会建议短旅行商路径结合给定边将是一个合理的重建。你可以用kd树一起使用 2-OPT 方式的宾利描述（paywalled，对不起，我认为也是在的本章由约翰逊和McGeoch TSP本地搜索）。所需要的一个修改将是确保初始路径包括给定的边缘和用2-最优操作不删除这些边

If you need one continuous curve, I would suggest that a short traveling salesman path that incorporates the given edges would be a reasonable reconstruction. You could use 2-opt together with a k-d tree the way Bentley described (paywalled, sorry; I think there's also a description in this chapter on TSP local search by Johnson and McGeoch). The one modification needed would be to ensure that the initial path includes the given edges and that 2-opt moves do not remove those edges.

这篇关于排序地理不连续的线段沿着一个隐含的曲线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！