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

Question

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

我有一个工作版本，不过能达到超过50万个多边形性能时变得缓慢。我的版本遍历每个面并将每个边的已排序顶点添加到stl :: set。我的数据集将主要是三角形和四边形多边形，并且大部分边缘将被共享。

有没有比这更聪明的算法？

Answer 1

是
使用双哈希映射。
每条边都有两个索引A，B。可以说A> B
第一个顶级哈希映射将A映射到另一个哈希映射，该映射依次将B映射到表示您想要的每个边的信息的某个值。 （或只是一个布尔，如果你不需要保留边缘信息）。
基本上这会创建一个由散列图组成的两级树。

要查找边缘在这个结构中，你需要较大的指数，在顶层看它与哈希映射结束。然后取较小的索引并在第二个哈希映射中查找它。

Answer 2

只是为了澄清，你想，一个多边形列表如下：

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

，而不是边缘然后是这样的：

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

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

那么你要删除重复的乙 - Visual C VS C-B的优势和分享呢？

你用算法看到了什么样的性能问题？我会说有一个合理的散列实现的集合应该表现很好。另一方面，如果你的散列不是最优的数据，你会有很多冲突，这可能会严重影响性能。

Answer 3

你们都是对的。使用一个好的hashset已经获得了超出所需级别的性能。我结束了自己的小哈希集合。

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

Answer 4

首先你需要确保你的顶点是唯一的。那就是如果你只想在一个特定位置有一个边缘。然后，我用这个数据结构

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

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

边缘包含顶点指数构成中有序的边缘。因此，如果sampleEdge是由索引号为12和5的顶点组成的边，则sampleEdge.first = 5和sampleEdge。12

然后，你可以做

uniqueEdges[sampleEdge] = true;

所有边缘。 uniqueEdges将保存所有独特的边缘。

Answer 5

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

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/edgehash.c

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_edgehash.h

这使用BLI_mempool， https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.c

https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_mempool.h