從多邊形網格中找到唯一邊的算法

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