3

Given:

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.

Desired Result:

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.

Context (i.e. "Why in the heck do I need this?"):

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?

4

2 回答 2

2

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

如果您需要一条连续的曲线，我建议包含给定边缘的短旅行推销员路径将是合理的重建。您可以按照Bentley 描述的方式将2-opt与 kd 树一起使用（付费墙，抱歉；我认为本章中还有 Johnson 和 McGeoch 对 TSP 本地搜索的描述）。需要进行的一项修改是确保初始路径包括给定的边缘，并且 2-opt 移动不会删除这些边缘。

于 2013-04-05T12:33:52.850 回答
1

我猜隐含曲线有两个属性。一是它是连续的，这意味着没有分段。其次，它的一阶导数是连续的，这意味着没有角。

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

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

通过此函数，您可以找到每条线与另一条线的相关程度。比你可以简单地连接具有最强关系的线。虽然我猜贪心算法并不意味着你总能得到最优解。

于 2013-04-05T12:35:39.273 回答