Noch einmal habe ich einige Fragen zu Polygon-Algorithmen.Konvertieren indexierter Polygone in nicht indizierte Polygone. Mehrere Probleme sind aufgetaucht
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.
Können Sie Ihre Polygone tessellieren, so dass sie immer 3 Kanten haben? –
Wie Sie sehen können, ist unsere interne Darstellung von Polygonen ein Vertex-Array. Dies bedeutet, dass eine Tesselation keinen Sinn ergibt, da alle Polygone nur Umrisse sind. Ich nehme an, das GTPolygon könnte tesselated sein. Du müsstest erklären, warum das helfen würde, da ich kein Experte auf diesem Gebiet bin. – Nailer
Nun, es würde bestimmen, wann ein Polygon beginnt/aufhört zu zählen bis zu 3 Kanten ... es sei denn, ich missverstehe Sie Fragen. –