连接无序线段

Question

我的算法生成了一个由数千条线段(全部是2D)组成的列表，我需要将它们连接成大的折线。生成的这些多段线可能是闭合的，也可能是开放的，但它们永远不会自相交。线段不是定向的，即可能需要先翻转线段，然后才能将其连接到其相邻线段。

找到这些折线的极快方法是什么？我必须实时地做这件事，所以任何花费时间超过-比如说- 10ms的都不是解决方案。

我用C#做这件事，但我是在寻找想法，而不是源码。

Answer 1

端点的散列可以工作吗？

如果端点完全匹配，那么您只需在散列中存储每个对象两次，每个端点存储一次。然后，对于每个对象，查找其两个端点。您将获得需要连接的任何其他对象。

如果端点有任何类型的不精确，那么您将需要一个spatial index，可能还需要一个that uses an R-tree。只需创建一个2d散列网格，就可以获得类似的效果。哈希网格包含附近端点的桶。您需要检查相邻的单元格。