Algorithmus für featured Kanten von Polygonnetz

StackOverflow https://stackoverflow.com/questions/207744

Frage

Ich bin auf der Suche nach einem guten Algorithmus, den mir die einzigartigen Kanten aus einem Satz von Polygondaten geben kann. In diesem Fall sind die Polygone von zwei Arrays definiert. Ein Array ist die Anzahl der Punkte pro Polygon, und das andere Array ist eine Liste von Vertex-Indizes.

Ich habe eine Version, die funktioniert, aber die Leistung wird langsam, wenn mehr als 500.000 Polys zu erreichen. Meine Version geht über jedes Gesicht und fügt den Kanten jedes sortierten Scheitelpunkte auf einer stl :: gesetzt. Mein Datensatz wird in erster Linie für Dreieck und Quad-Polys und die meisten Kanten geteilt werden.

Gibt es einen intelligenten Algorithmus für das?

War es hilfreich?

Lösung

Ja
Verwenden Sie eine doppelte Haschisch-Karte.
Jede Kante hat zwei Indizes A, B. können sagen, dass A> B.
Die erste, die Top-Level-Hash-Karte Karten A auf einen anderen Hash-Karte, die wiederum Karten B bis zu einem gewissen Wert, der die Informationen repräsentiert, die Sie über jede Kante wollen. (Oder auch nur ein Bool, wenn Sie brauchen keine Informationen zu Kanten halten).
Im Wesentlichen das schafft einen Zwei-Ebenen-Baum von Hash-Karten zusammen.

Um eine Kante in dieser Struktur nehmen Sie den größeren Index zu sehen, schauen Sie in der obersten Ebene und mit einer Hash-Karte am Ende. nehmen Sie den kleineren Index dann und schauen sie in dieser zweiten Hash-Karte auf.

Andere Tipps

Nur um zu klären, die Sie wollen, für eine Polygonliste wie folgt aus: 

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

Dann statt Kanten wie folgt aus: 

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

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

dann wollen Sie das Duplikat B entfernen - C gegen C - B Rand und teilen

Welche Art von Performance-Problem sehen Sie mit Ihrem Algorithmus? Ich würde einen Satz sagen, dass eine vernünftige Hash-Implementierung hat sollte ziemlich ok ausführen. Auf der anderen Seite, wenn Ihr Hash nicht optimal für die Daten vorhanden sind, werden Sie viele Kollisionen haben, die Leistung schlecht beeinflussen könnten.

Sie sind beide richtig. eine gute Hashset Mit hat die Leistung weit über erforderliches Niveau bekommen. Ich landete mein eigenes kleines Hash-Set rollen.

Die Gesamtzahl der Kanten wird zwischen N / 2 und N. N die Anzahl der eindeutigen Scheitelpunkte in dem Netz zu sein. Alle gemeinsamen Kanten werden N / 2, und alle einzigartigen Kanten N. sein Von dort habe ich einen Puffer von uint64 des zuteilen und meine Indizes in diese Werte packen. Mit einem kleinen Satz von eindeutigen Tabellen kann ich die einzigartigen Kanten schnell finden!

Zuerst müssen Sie sicherstellen, dass Ihre Eckpunkte sind einzigartig. Das ist, wenn Sie nur eine Kante an einer bestimmten Position wollen. Dann habe ich diese Datenstruktur verwenden

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

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Rand enthält den Vertex-Indizes, die den Rand in sortierter Reihenfolge bilden. Daher, wenn sampleEdge eine Kante von Eckpunkten mit Indexnummern 12 geschminkt und 5, sampleEdge.first = 5 und sampleEdge.12

Dann können Sie einfach tun

uniqueEdges[sampleEdge] = true;

für alle Kanten. uniqueEdges hält alle einzigartigen Kanten.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top