多边形网格中唯一查找边的算法

题

我正在寻找一种好的算法，可以从一组多边形数据中获得独特的边缘。在这种情况下，多边形由两个数组定义。一个数组是每个多边形的点数，另一个数组是顶点索引列表。

我有一个正在运行的版本，但是当达到超过500,000的多边形时性能会变慢。我的版本遍历每个面，并将每个边的排序顶点添加到stl :: set。我的数据集主要是三角形和四边形多边形，大多数边将被共享。

这有更聪明的算法吗？

解决方案

是，点击使用双哈希映射。
每条边都有两个索引A，B。让我们说A <！> gt; B.结果第一个顶级哈希映射将A映射到另一个哈希映射，该哈希映射又将B映射到某个值，该值表示您想要的关于每个边的信息。（或者如果你不需要保留边缘信息，那么只是一个bool）本质上，这会创建一个由哈希映射组成的二级树。

要在此结构中查找边缘，您可以获取较大的索引，在顶层查找并最终得到哈希映射。然后获取较小的索引并在第二个哈希映射中查找它。

其他提示

您想要澄清一个像这样的多边形列表：

A +-----+ B
   \    |\
    \ 1 | \
     \  |  \
      \ | 2 \
       \|    \
      C +-----+ D

然后代替这样的边缘：

A - B -+
B - C  +- first polygon
C - A -+

B - D -+
D - C  +- second polygon
C - B -+

然后你想删除重复的B - C与C - B边缘并分享吗？

您在算法中遇到了什么样的性能问题？我会说一个具有合理哈希实现的集应该执行得很好。另一方面，如果您的哈希值不是数据的最佳值，那么您将遇到很多可能会严重影响性能的冲突。

你们都是对的。使用良好的hashset使性能远远超出了所需的水平。我最终滚动了自己的小哈希集。

边的总数将在N / 2和N之间.N是网格中唯一顶点的数量。所有共享边都是N / 2，所有唯一边都是N.从那里我分配一个uint64的缓冲区并将我的索引打包成这些值。使用一小组独特的表格，我可以快速找到独特的边缘！

继承人在Blender中使用的边缘散列的C实现正是为了快速从面创建边缘，可能会为其他人提供一些自己的提示。

首先，您需要确保您的顶点是唯一的。也就是说，如果您只想在某个位置使用一条边。然后我使用这个数据结构

typedef std::pair<int, int> Edge;

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Edge包含按排序顺序组成边的顶点索引。因此，如果sampleEdge是由索引号为12和5的顶点组成的边，则sampleEdge.first = 5和sampleEdge.12

然后你可以做

uniqueEdges[sampleEdge] = true;

表示所有边缘。 uniqueEdges将保留所有独特的边缘。

许可以下： CC-BY-SA 和归因