Erkennen von Polygonen aus zufällig aufgeführten Kanten

Question

Ich habe eine Vektorzeichnung, die die Kanten vieler Polygone enthält. Jede Kante wird durch einen Start- und einen Endpunkt dargestellt. Verbindungen zwischen den Kanten sind nicht explizit angegeben. Ich muss die Polygone aus diesen Daten extrahieren. Der offensichtliche Weg, dies zu tun, besteht darin, einen Punkt jeder Kante zu nehmen, alle anderen Kanten nach einem übereinstimmenden Punkt zu durchsuchen und dies mit dem nächsten Punkt der so gefundenen Kante zu wiederholen, bis ich eine geschlossene Schleife habe. Aber das ist sehr ineffizient.

Welche guten Algorithmen gibt es, um Polygone zu extrahieren, wenn nur Start- und Endpunkte von Kanten in keiner bestimmten Reihenfolge gegeben sind?

Answer 1

Versuchen Sie etwas Ähnliches (Python-Pseudocode):

vertices = {} #map (x, y) coords to a list of all edges containing that vertex

for edge in edges:
    #add start & end vertices
    if edge.start not in vertices:
        vertices[edge.start] = []
    if edge.end not in vertices:
        vertices[edge.end] = []
    vertices[edge.start].append(edge)
    vertices[edge.end].append(edge)

Jetzt haben Sie alle Eckpunkte und alle Kanten, die aus jedem Eckpunkt herausführen. Jetzt können Sie die anfängliche Idee für Ihren Algorithmus umsetzen, aber anstatt alle Kanten nach einem übereinstimmenden Eckpunkt durchsuchen zu müssen, ist dieser Lookup sofort.

Answer 2

Eine einfache Möglichkeit, dies zu tun, wäre:

Sortieren Sie die Liste der Kanten nach Endpunkt. Nennen Sie dieses Array Kanten.
Erstellen Sie ein neues Array, Polygon, Größe ist num_edges 
EdgeIndex = 0
Kante von Kanten[0] nach Polygon[0] kopieren
Zählen = 1
während (Zählen < Anzahl_der_Kanten)
{
    Startpunkt = Kanten[EdgeIndex].Endpunkt
    // Führen Sie eine binäre Suche durch, um das Segment zu finden, das bei diesem Endpunkt der Kante beginnt.
    NeuerIndex = binäre Suche(Kanten, Startpunkt)
    Kante[NeuerIndex] nach Polygon[Zählen] kopieren
    ++Zählen
    EdgeIndex = NeuerIndex
}

Wenn Sie damit fertig sind, sollte das Polygon-Array die Kanten in der richtigen Reihenfolge enthalten.

Das obige nimmt an, dass die Kantenpunkte vernünftig ausgegeben werden. Das heißt, für ein Dreieck mit den Eckpunkten '[(0, 0), (10, 10), (10, 0)]' sind die Kanten gegeben als:

{(0, 0), (10, 10)}
{(10, 10), (10, 0)}
{(10, 0), (0, 0)}

Obwohl nicht unbedingt in dieser Reihenfolge. Wenn die zweite Kante als {(10, 0), (10, 10)} gegeben ist (d.h. Start und Ende sind vertauscht), dann ist das Problem etwas schwieriger.

Sie können dasselbe mit einer Hashtabelle und direkten Suchvorgängen tun, was schneller ist als die binäre Suche.

Beachten Sie auch, dass davon ausgegangen wird, dass Sie nicht mehr als zwei Kanten haben, die mit einem einzigen Punkt verbunden sind.