Algorytm unikalnego znajdowania krawędzi z siatki wielokątnej

Question

Poszukuję dobrego algorytmu, który da mi unikalne krawędzie z zestawu danych wielokąta. W tym przypadku wieloboki są definiowane przez dwie tablice. Jedna tablica to liczba punktów na wielokąt, a druga tablica to lista indeksów wierzchołków.

Mam wersję, która działa, ale wydajność osiąga powolność po osiągnięciu ponad 500 000 polys. Moja wersja przechodzi przez każdą twarz i dodaje posortowane wierzchołki każdej krawędzi do stl :: set. Mój zestaw danych będzie przede wszystkim polem trójkąta i kwadratu, a większość krawędzi zostanie udostępniona.

Czy istnieje mądrzejszy algorytm do tego?

Answer 1

Tak
Użyj podwójnej mapy mieszania.
Każda krawędź ma dwa indeksy A, B. powiedzmy, że A> B.
Pierwsza mapa map hash na najwyższym poziomie A do innej mapy hash, która z kolei odwzorowuje B na pewną wartość, która reprezentuje informacje, które chcesz o każdej krawędzi. (lub po prostu bool, jeśli nie potrzebujesz zachować informacji o krawędziach).
Zasadniczo tworzy to dwupoziomowe drzewo złożone z map skrótów.

Aby znaleźć krawędź w tej strukturze, należy wziąć większy indeks, wyszukać go na najwyższym poziomie i skończyć z mapą skrótu. następnie weź mniejszy indeks i sprawdź go w tej drugiej mapie skrótów.

Answer 2

Właśnie w celu wyjaśnienia, chcesz, aby uzyskać listę wielokąta jak ten:

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

Wtedy zamiast krawędzi tak:

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

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

następnie chcesz usunąć duplikaty B - C vs .C - B krawędzi i dzielić się nim?

Jakie problemy z wydajnością występują w przypadku korzystania z algorytmu? Powiedziałbym, że zestaw, który ma rozsądną implementację skrótu, powinien wyglądać całkiem dobrze. Z drugiej strony, jeśli twój hash nie jest optymalny dla danych, będziesz mieć wiele kolizji, które mogą źle wpłynąć na wydajność.

Answer 3

Oboje jesteście poprawni. Korzystanie z dobrego hashitu osiągnęło wydajność znacznie przekraczającą wymagane poziomy. Skończyłem przetaczając mój własny mały zestaw haszyszu.

Łączna liczba krawędzi wynosi od N/2 do N. N oznacza liczbę unikalnych wierzchołków w siatce. Wszystkie wspólne krawędzie będą miały wartość N/2, a wszystkie unikalne krawędzie będą mieć wartość N. Z tego miejsca przydzielam bufor uint64 i pakuję moje indeksy do tych wartości. Używając niewielkiego zestawu unikatowych stołów mogę szybko znaleźć unikalne krawędzie!

Answer 4

Najpierw należy się upewnić, że wierzchołki są unikatowe. To znaczy, jeśli chcesz mieć tylko jedną krawędź w określonej pozycji. Następnie używać to struktura danych

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

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

krawędź zawiera indeksy wierzchołków, które tworzą przewagę w posortowanych. Stąd, jeśli sampleEdge jest krawędzią złożoną z wierzchołków o indeksach 12 i 5, sampleEdge.first = 5 i sampleEdge.12

Następnie można po prostu zrobić

uniqueEdges[sampleEdge] = true;

na wszystkich krawędziach. uniqueEdges pomieści wszystkie unikalne krawędzie.

Answer 5

Oto implementacja wcięcia krawędziowego zastosowana w Blenderze dokładnie w celu szybkiego tworzenia krawędzi od twarzy, może dać wskazówki innym, aby mogli zrobić własne.

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

używa 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