Konvertieren indexierter Polygone in nicht indizierte Polygone. Mehrere Probleme sind aufgetaucht

Question

Noch einmal habe ich einige Fragen zu Polygon-Algorithmen.

Ich werde versuchen, mein Problem zu erklären:

Ich bin eine Teilmenge eines Dritten Bibliothek namens Geometrische Werkzeuge (GT) mit Boolesche Operationen auf meine Polygone auszuführen. Um dies zu erreichen, muss ich mein internes Polygonformat in das von GT verwendete Format konvertieren.

Unser internes Polygon-Format besteht aus einem Vertex-Array, während das GT-Polygon aus einem indizierten Vertex-Array besteht, bei dem jede Kante durch ein Paar Indizes dargestellt wird.

Beispiel eines Quadrates zur Klärung:

Internes Format:

vertices[0] = Vertex2D(1,0) -> start 
vertices[1] = Vertex2D(1,1) 
vertices[2] = Vertex2D(0,1) 
vertices[3] = Vertex2D(0,0) 
vertices[4] = Vertex2D(1,0) -> end 

Außenformat:

vertices[0] = Vertex2D(1,0) 
vertices[1] = Vertex2D(1,1) 
vertices[2] = Vertex2D(0,1) 
vertices[3] = Vertex2D(0,0) 

edges[0] = std::pair<int,int>(0,1) 
edges[1] = std::pair<int,int>(1,2) 
edges[2] = std::pair<int,int>(2,3) 
edges[3] = std::pair<int,int>(3,0) 

//There is also a BSP tree of the polygon which I don't care to depict here. 

Nun, ich schrieb einen Algorithmus, der in den meisten Fällen funktioniert, aber Abstürze und brennt, wenn zwei Kanten den gleichen Startknoten haben. Lassen Sie mich zunächst erklären, wie mein aktueller Algorithmus funktioniert.

Erstellen Sie eine std :: map, wobei der Schlüssel eine Ganzzahl ist, die den Vertex-Index darstellt. Der Wert gibt an, wo im Edge-Array eine Kante mit dem Schlüsselindex als Startindex vorhanden ist.

Mockup Beispiel:

std::vector< std::pair< int, int > > edge_array; 

edge_array.push_back(std::pair< int, int >(0, 1)); 
edge_array.push_back(std::pair< int, int >(2, 3)); 
edge_array.push_back(std::pair< int, int >(1, 2)); 
edge_array.push_back(std::pair< int, int >(3, 0)); 

std::map< int, int > edge_starts; 
for (int i = 0 ; i < edge_array.size(); ++i) { 
    edge_starts[ edge_array[i].first ] = i; 
} 

von der richtigen Kante springen Kante zu korrigieren jetzt gehen Sie wie folgt ich kann nur das Innere einer while-Schleife:

while (current_placed_index = first_index_in_polygon) { 
    int index_to_next_edge_to_be_traversed = edge_starts[ current_edge.second ]; 
} 

Innerhalb dieser Schleife wird eine Optimierung durchgeführt, und Vertex-Indizes werden zu einem Array hinzugefügt.

Jedes Mal, wenn ein Polygon geschlossen ist, finde ich die erste nicht versetzte Kante und beginne ein weiteres Polygon zu machen. Ich mache das solange weiter, bis im GTPolygon keine Kanten mehr vorhanden sind.

So kann jedes GTPolygon mehrere Polygon (interne) Objekte ergeben.

Der Fehler in diesem Algorithmus ist offensichtlich, wenn zwei Kanten denselben Scheitelpunkt wie ein Startscheitelpunkt haben. Beispiel:

<1,2> 
<1,3> 
<1,5> 

Wenn meine Kanten durchlaufen, wie werde ich welche diese Kanten weiß, gehört zu dem Polygon ich derzeit durchlaufen? Ich könnte versuchen, die Kanten zurück zu überqueren, wenn eine solche doppelte Situation auftritt. Das Problem wäre dann die Möglichkeit, dass die Überquerung unendlich oft vor und zurück geht, wenn beim Rückwärtsfahren ein anderes Duplikat gefunden wird.

Meine Frage ist, wie kann ich das lösen? Ist es überhaupt lösbar? Kann ich den BSP-Baum verwenden, um das Problem zu lösen? Die Menge an Ecken Fällen ist ein bisschen entmutigend.

Jede Hilfe wird sehr geschätzt, da 5 Monate Arbeit von dieser Arbeit abhängen.

Edit:

Zur Klarstellung: ich aus der indexierten Darstellung eines Polygons konvertieren möchten, die Geometrie Werkzeuge mit unserem internen Polygonformat arbeitet, die nur eine Reihe von miteinander verbundenen Knoten in einer Liste ist.

Answer 1

Sie versuchen effektiv, alle cycles in einem undirectedgraph zu finden, wobei jeder Zyklus die Kanten eines eindeutigen Polygons darstellt. This paper schlägt eine depth-first search (DFS) Lösung vor.

Answer 2

Warum speichern Sie Polygone nicht explizit als eine geordnete Sammlung von Kanten? Das würde sicherstellen, dass Sie immer ein Polygon kennen, dessen Kanten Sie berücksichtigen sollten.

Answer 3

Haha, ok Leute. Es scheint, als wäre der ganze Hub für nichts gewesen. Ich habe herausgefunden, dass Geometry Tools eine eigene Klasse hat, um mit solchen Problemen umzugehen.

Beispiel gefunden here.