加入无序的线段 [英] Joining unordered line segments

问题描述

我的算法产生了一个（通常）几千条线段（全部为2D）的列表，我需要将它们合并成大的折线。这些生成的折线可能会关闭或打开，但它们永远不会自相交。线段不是直接的，也就是说，它可能需要翻转线段才能连接到它的邻居。

什么是非常快速的查找方式这些折线？我必须实时做到这一点，所以任何需要超过-say-10ms的东西都不是解决方案。

我在C＃中这样做，但是我'寻找想法，而不是来源。

解决方案

终点的散列会起作用吗？

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

如果端点有任何不准确的地方，那么您需要一个空间索引，可能还有一个使用R-tree 。你可以通过创建一个2d哈希网格来获得类似的效果。散列网格包含附近端点的桶。您需要检查邻近的单元。

My algorithm produces a list of (usually) several thousand line segments (all 2D) which I need to join up into large polylines. These resulting polylines might be closed or open, but they are never self-intersecting. The line segments are not directed, i.e. it might be needed to flip a line segment before it can be joined to its neighbour.

What would be an extremely fast way of finding these polylines? I have to do this in real-time, so anything that takes longer than -say- 10ms is not a solution.

I'm doing this in C#, but I'm looking for ideas, not source.

解决方案

Would a hash of endpoints work?

If the endpoints match exactly then you can just store each object twice in a hash, once by each endpoint. Then, for each object, look up both its end points. You will get any other objects that need to be joined.

If the endpoints have any kind of imprecision, then you will need a spatial index, and probably one that uses an R-tree. You can get a similar effect by just making a 2d hash grid. The hash grid contains buckets of nearby endpoints. You will need to check neighboring cells.

这篇关于加入无序的线段的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！