algorithm - 连接无序线段

Question

我的算法生成一个包含(通常)几千条线段(全部为二维)的列表，我需要将这些线段连接成大折线。这些生成的折线可能是封闭的或开放的，但它们永远不会自相交。线段不是定向的，即可能需要翻转线段才能将其连接到相邻线段。

找到这些折线的极快方法是什么？我必须实时执行此操作，因此任何超过 -say- 10ms 的时间都不是解决方案。

我在 C# 中执行此操作，但我正在寻找想法，而不是来源。

Answer 1

端点散列可行吗？

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

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