Generieren Sie Polygone aus einer Reihe sich überschneidender Linien

10

Dies ist eine einfache und recht häufige Frage, die bereits für verschiedene Zwecke gestellt wurde (siehe diesen Link und dies auch zum Beispiel). Hier suchen wir jedoch nicht nach einem Softwarepaket, sondern nach Algorithmen , die wir beispielsweise implementieren könnten Python .

Wie unten gezeigt, wird eine Reihe von Linien zugeordnet (sie sind übrigens bereits zugeschnitten).
Algorithmen / Ideen zur Erzeugung von Polygonen (wie rot gezeigt) ?

Geben Sie hier die Bildbeschreibung ein

algorithm polygonize geometry-conversion Entwickler
quelle
Ist die äußere quadratische Grenze bekannt oder soll diese auch aus den Eingabezeilen gelesen werden?
Devdatta Tengshe

Antworten:

5

Nun, wir geben hier eine Antwort, die keine vollständige Antwort auf unsere Frage ist, dh die Frage bleibt " offen für Antworten ". Es ist jedoch eine Lösung für das Problem in der Frage. Hier ist der Trick, den wir verwendet haben:

Lassen Sie uns zuerst die Ergebnisse sehen :
Geben Sie hier die Bildbeschreibung ein

Also die angegebenen Linien in den leftgebauten Polygonen in der middle. Sie sind echte Polygone, wie in der Abbildung gezeigt right;)

Für den unten angegebenen Algorithmus haben wir das ShapelyPaket in Python verwendet .

  • Linien ==> MultiLineString {:: M}
  • füge ein kleines hinzu buffer, sag eps{:: MB}
  • region ==> Polygon {:: P} (region hier ist ein Quadrat)
  • P.difference(MB) {resultierende Polygone}

Beachten Sie, dass es im Betrieb sehr schnell ist. Der fehlende Punkt ist jedoch, dass der Algorithmus keine ursprüngliche Methode zum Erstellen von Polygonen aus Linien ist . Trotzdem funktionierte es perfekt für das Problem, das wir in der Hand hatten.

Entwickler
quelle
4

Die JTS Topology Suite verfügt über eine Polygonizer-Klasse, die dies ziemlich genau tut.

Sie können sich den hier verfügbaren Quellcode ansehen und ihn in Python konvertieren.

Devdatta Tengshe
quelle
Wie die Codebeschreibung besagt, funktioniert es nicht wie vom Frageautor erwartet: "Kanten müssen korrekt geknotet sein, dh sie dürfen sich nur an ihren Endpunkten treffen. Der Polygonizer wird bei falsch geknoteten Eingaben ausgeführt, bildet jedoch keine Polygone aus non -noded Kanten "
Pablo
1
In JTS gibt es eine Operation zum korrekten Teilen der Linien an Eckpunkten. Vielleicht könnte sich das OP das auch ansehen.
Devdatta Tengshe
3

Sie können sich das Python Shapely-Paket ansehen, insbesondere polygonize ()

Dave
quelle
Ein kurzer Hinweis, dass Polygonize in Shapely ( from shapely.ops import polygonize) GEOS.Polygonize von GEOS verwendet . Dies ist also ein Link, über den ein Link zu einem Link besteht ...: |
Entwickler
Unsere Versuche mit polygonizewaren überhaupt nicht erfolgreich. Vielen Dank jedoch, dass Sie uns daran erinnert haben, Shapelymit welcher Lösung wir eine Lösung finden können (eigentlich ein Trick).
Entwickler
2

Hier ist eine andere Lösung, die wir finden könnten.

Mit können DCELwir Blöcke aus berührenden Linien machen.

Für Python gibt es ein Paket {hier} . Es ist eine winzige Implementierung mit einigen Fehlern. Trotzdem kann es mit etwas Aufwand für dieses Problem eingesetzt werden. Beachten Sie auch die folgenden Schritte:

Eine Vorverarbeitungsstufe, in der alle Schnittpunkte zwischen Linien gefunden werden. Dementsprechend werden dann alle Linien an den Interaktionspunkten in Segmente unterteilt. Eine Liste der Schnittpunkte und eine Liste der zugehörigen Kanten werden für DCEL benötigt.

Entwickler
quelle
Da diese Methode eine originelle Lösung ist und eine viel bessere Leistung bietet als die andere Methode, bei der der differenceBetrieb verwendet wird.
Entwickler