我正在寻找一种好的算法，可以从一组多边形数据中获得独特的边缘。在这种情况下，多边形由两个数组定义。一个数组是每个多边形的点数，另一个数组是顶点索引列表。
我有一个正在运行的版本，但是当达到超过500,000的多边形时性能会变慢。我的版本遍历每个面，并将每个边的排序顶点添加到stl :: set。我的数据集主要是三角形和四边形多边形，大多数边将被共享。
有更聪明的算法吗？
是 使用双哈希映射。 每条边都有两个索引A，B。让我们说A> 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实现正是为了快速从面创建边缘，可能会为其他人提供一些自己的提示。
这使用BLI_mempool，https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.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将保留所有独特的边缘。