Linien zu Polygonen

11

Ich habe den "Namen" des Algorithmus nicht gefunden, mit dem man Linien in Polygone konvertieren kann. Da dieses Thema GIS und die Bereiche Computergeometrie und Informatik kreuzt. Ich bin mir nicht sicher, was ich noch zu der Mischung hinzufügen soll. Ich zögere es, eine Liste meiner Suchanfragen bereitzustellen, da ich auch gerne wissen möchte, welche anderen Personen ihre erste Wahl für Suchkriterien treffen würden.

Das Szenario ... Ich habe Linien (zwei Punkte werden benötigt, um eine Linie zu konstruieren) ... jede Linie ist mit mindestens einer anderen Linie verbunden. Der Zwischenraum zwischen den verbundenen Linien würde ein Polygon bilden. Das einfachste Szenario wäre ein Dreieck ... ein Rechteck ... und man könnte darüber hinaus zu mehrsegmentierten Features übergehen.

Entschuldigen Sie vage Beschreibungen, aber wie gesagt, ich möchte die möglichen Lösungen nicht auf einen Weg führen, den ich bereits besucht habe, da ich mich sowohl für den "ersten Gedanken" als auch für eine endgültige Lösung interessiere.

polygon algorithm geometry-conversion Germán Carrillo
quelle
Können Linien zusammenfallen? Können sich Linien kreuzen? (dh ist es sauber?) Wenn ja, hoffe ich, dass das Aufrufen dieses Prozesses Build nicht zu app-spezifisch wäre.
Kirk Kuykendall
Kirk Coincident-Linien und andere "Defekte" wären vor dem Erstellen der Polygone entfernt worden ... Ich versuche, den "Algorithmusnamen" zu finden, der sicher in verschiedenen GIS-Paketen (z. B. Arcgis) implementiert wurde. Kurz gesagt, denken Sie daran, dass alle entarteten Zustände behandelt wurden und Sie klare Linien (2 Punktlinien) haben, die an Knoten zusammenfallen, an denen Sie Polygone konstruieren können sollten. Der Schlüssel ist, dass die Linien existieren, es keine entarteten Bedingungen gibt und der dazwischenliegende Raum in Polygone umgewandelt werden muss. Danke
Befinden sich die Punkte auf einer Ebene oder auf einer Kugel?
Kirk Kuykendall
Kirk ... In einer Ebene metrische x-, y-Koordinaten, keine sphärischen Koordinaten. Angenommen, Sie haben die Liniensegmente, die ein Voronoi-Diagramm bilden würden, aber alles, was Sie haben, sind die Segmente, die es bilden, aber nicht die tatsächliche Datenstruktur, die dazu geführt hat. Kurz gesagt, jedes Segment ist verbunden und jedes Segment ist einzigartig.

Antworten:

4

Vielleicht "Flächenfüllung"? Sehen Sie hier und hier .

Bearbeiten

Eine andere Möglichkeit ist die eingeschränkte Triangulation . (Der Link führt zu einem Java-Applet, mit dem Sie ein Diagramm mit der Maus zeichnen und anschließend einen Ebenen-Sweep-Algorithmus zum Triangulieren veranschaulichen können.) Das Ergebnis einer solchen Triangulation, unabhängig davon, wie sie ausgeführt wird, kann problemlos verarbeitet werden Erstellen Sie die gewünschten Polygone: Führen Sie einfach alle benachbarten Dreiecke zusammen, die eine neu erstellte Kante gemeinsam haben.

Beispiel

Originalgrafik:

Originalgrafik

Triangulierter Graph:

Geben Sie hier die Bildbeschreibung ein

whuber
quelle
Bill Ich werde abstimmen, da ich nicht darauf gestoßen bin ... ich möchte andere Kommentare von Leuten aus verschiedenen Disziplinen nicht einschränken.
Obwohl es sich hauptsächlich um Rasterfüllungen handelt, ist dies die naheliegendste Antwort. Ich habe immer noch keinen Algorithmusnamen, es sei denn, er ist entweder an ein Raster oder einen Vektor angehängt, aber ein "Sweep" -Algorithmus könnte ausreichen, aber ich kann für mein Leben nicht herausfinden, warum Koordinaten eher nach Y als nach X sortiert werden ( was in den meisten Sprachen einfach zu implementieren ist).
@Dan Das Sortieren nach y oder x ist, wie Sie vorschlagen, unerheblich. Sie haben auch Recht, dass es sich um Ebenen- oder Linien-Sweep-Algorithmen handelt. Leider handelt es sich hierbei um eine allgemeine Technik, die fast alle Verfahren der rechnerischen Geometrie abdeckt. Daher ist dies kein geeigneter Begriff für die Suche speziell nach Ihrem Algorithmus. Beachten Sie, dass dieses spezielle Problem nicht rein graphentheoretisch ist, da es eine Einbettung des Polylinienkomplexes in eine Ebene (oder Kugel) beinhaltet und ein guter Algorithmus daher Informationen über die Einbettung beibehalten muss. Deshalb handelt es sich wirklich um ein Flächenfüllungsproblem von Herzen.
whuber
5

In der Graphentheorie wird diese Operation als Flächenberechnung bezeichnet . Es bezieht sich auf die Berechnung des Duals eines gegebenen Graphen.

In der GeOxygène- Java-Bibliothek verfügt beispielsweise ein Diagramm ( CarteTopo ) über eine Methode getFaces, mit der das Gesicht abgerufen werden kann .

Dies wird in JTS als Polygonisierung bezeichnet

julien
quelle
Gute Links. Sie alle gehen jedoch davon aus, dass das Problem von @ Dan bereits gelöst ist: Wenn Sie einen Graphen als "planar" bezeichnen können, haben Sie die polygonalen Flächen bereits identifiziert. Er möchte wissen, wie man überhaupt eine beliebige Sammlung von Bögen (in der Ebene) in einen ehrlichen planaren Graphen umwandelt. Dies erfordert die Erstellung einer Darstellung der "Topologie", z. B. einer DCEL.
whuber
Vielen Dank, du bist eine Quelle des Wissens! Ich frage mich, wie jemand so brillant sein kann.
Julien
4

Die RepRap-Hostsoftware konvertiert eine Liste von Liniensegmenten (in einer unbekannten zufälligen Reihenfolge) in eine Liste von Polygonen, die sich ähnlich anhört, wie Sie es versuchen.

Insbesondere behandelt der RepRap-Algorithmus "End Matching" eine Reihe von pathologischen Fällen.

Leider geht die RepRap-Software davon aus, dass jede Ecke eine gerade Anzahl von Kanten aufweist - 2 Linien, die zu einer Ecke eines normalen Objekts führen. 4 Linien gehen zusammen, wenn die Ecke eines Objekts die Ecke eines anderen Objekts berührt usw. Ich weiß nicht, wie schwierig es wäre, diesen Algorithmus für Voronoi-Diagramme anzupassen, bei denen normalerweise 3 Kanten zu jeder Ecke verlaufen.

David Cary
quelle
+1 Interessanter Fund! Achtung: Obwohl diese Software in der Lage zu sein scheint, viele Probleme im Zusammenhang mit dem Verbinden von Linien zu Polygonen zu lösen, kann sie zu viel bewirken: Es scheint, als würde sie auch versuchen, die Funktionen zu vereinfachen, was ein unerwünschter Nebeneffekt sein kann. (ZB kann es die topologische Integrität zerstören.)
whuber
3

Haben Sie die Codebasis von GRASS nach einer Lösung für Ihr Problem durchsucht? -> http://old.nabble.com/Polyline-to-Polygon-operation-td20257839.html

oeon
quelle
1
Vielen Dank ... aber ich bin nicht auf der Suche nach einer bestimmten "verpackten" Lösung, sondern nach dem zugrunde liegenden Algorithmus und / oder dessen Namen, der in den verschiedenen Bereichen von GIS, Comp Geom und / oder Comp Sci zu finden ist ... halten Sie die Ideen auf dem
Ich habe darüber nachgedacht, den Quellcode hinter den beiden in meinem Link genannten Prozessen genauer zu betrachten.
oeon
Ich denke, ich müsste die Software installieren, um den Code zu sehen, da ich auf diesen Seiten keine Auflistung sehe, es sei denn, mir fehlt etwas.
1
Sie können die GRASS-Quelle online durchsuchen: trac.osgeo.org/grass/browser
underdark
@underdark Danke für den Zeiger. Soweit ich aus main.cder v.typeQuelle ersehen kann, werden die Features lediglich als Grenzen umbenannt: Es findet keine tatsächliche Verarbeitung statt. Im Nachhinein ist dies nicht allzu überraschend: Wenn (ich weiß nicht genau) die Features mit vollständigen topologischen 2D-Informationen verwaltet werden, hat die gesamte Berechnung zur Identifizierung polygonaler Regionen automatisch während der Erstellung oder des Imports von Features stattgefunden und wird durchgehend beibehalten alle Geoverarbeitungsvorgänge.
whuber
3

Hallo

Ich glaube nicht, dass Sie nach einem bestimmten Algorithmus suchen. Die Aufgabe kann je nach Datensatz sehr schwierig oder sehr einfach sein.

Sie sollten das Problem in mindestens 2 Teile teilen. 1) ist eher ein Netzwerkproblem, wie man geschlossene Ringe von Linestrings findet. 2) Drücken Sie den geschlossenen Linienstreifen als Polygon aus

Der zweite Teil, der "Konvertieren von Linien in Polygone" ist, hängt mehr vom Format als von der Darstellung von Polygonen / Linien ab. Ich meine von:

LINESTRING (1 1, 2 2)
LINESTRING (2 2, 2 1)
LINESTRING (2 1, 1 1)

an:
POLYGON ((1 1,2 2,2 1,1 1))

konvertiert Linie in Polygon, ist aber nicht das, wovon Sie sprechen, denke ich. Der schwierigere Teil ist der erste. Wenn Sie eine Spaghetti von Linien haben, wie Sie sie als geschlossene Linien bestellen.

Ich denke, die Antwort auf diese Frage hängt stark vom Datensatz ab. Wie Kirk fragt, ist es viel größer, ob die Linien das Problem kreuzen können. Wenn Sie wissen, dass alle "Liniensammlungen" Teil eines geschlossenen Linestrings sind, wird es einfacher. Dann können Sie eine beliebige Linie greifen und sich um den Pfad herumbewegen, bis Sie wieder zurück sind, und dann mit Schritt zwei oben fortfahren.

Mein Punkt ist, dass der Zustand des Datensatzes alle Regeln dafür festlegt. Wenn Sie alle möglichen Polygone in einer Spaghetti von Linestrings finden möchten, müssen vermutlich viele verschiedene Algorithmen verwendet werden, um Scheitelpunkte in alle Kreuzungen einzufügen, alle möglichen Pfade zu durchsuchen und so weiter.

In PostGIS heißt die Funktion ST_Polygonize. Diese Funktion erstellt alle möglichen Polygone aus den von Ihnen angegebenen Linestrings.

Dies wird von GEOS durchgeführt, sodass Sie die dahinter stehenden Algorithmen sowohl im GEOS- als auch im JTS-Code finden können.

Nur ein paar Gedanken

/ Nicklas

Nicklas Avén
quelle
1

Sie könnten versuchen, nach dem "Forward Star" -Algorithmus zu suchen. Mir wurde gesagt, dass es generisch ist, aber die einzigen Diskussionen darüber, die ich jemals gelesen habe, bezogen sich immer auf Arcgis. Schauen Sie sich vielleicht die in diesen Vorlesungsunterlagen zitierten Referenzen für Forward Star an.

Kirk Kuykendall
quelle
1
Ich werde hier einen Kommentar abgeben, obwohl dieser Kommentar auch einige andere der vorgeschlagenen Lösungen anspricht: Das Problem kann nicht in einem Netzwerk (oder einer Grafik) dargestellt werden. Es erfordert Informationen darüber, wie die Linien innerhalb einer zweidimensionalen Oberfläche verbunden sind . Somit wären die Vorwärts- / Rückwärts-Sterndarstellungen von geringem Nutzen; ein DCEL oder ähnliches wird benötigt.
whuber
@whuber - Ich ging davon aus, dass Dans Kommentar, dass alle "Mängel" beseitigt worden waren, implizierte, dass die Linien sauber waren. Daher sollte es möglich sein, dies auf ein Diagrammdurchlaufproblem zu reduzieren, bei dem alle Zyklen in einem Diagramm gefunden werden. Zuerst dachte ich, Forward Star würde bei Algorithmen helfen, die um einen Graphen herumgehen und an jedem Knoten die schärfste Rechtskurve machen. Wenn man jedoch etwas genauer hinschaut, scheint es bessere Möglichkeiten zu geben. stackoverflow.com/questions/261573/… Dies setzt jedoch voraus, dass das Problem als Diagramm erneut angegeben werden kann.
Kirk Kuykendall
1
Das Finden von Zyklen in einem Diagramm ist nicht dasselbe wie das Finden von Gesichtern in einem planaren Diagramm. Betrachten Sie den abstrakten Graphen mit den Eckpunkten {a, b, c, d} und den Kanten {a, b}, {a, c}, {b, c}, {b, d}, {c, d}. Eine Basis für die Zyklen besteht aus a-> b-> d-> c-> a und a-> b-> c-> a. In der planaren Einbettung a -> (0,1), b -> (2,2), c -> (2,0), d -> (3,1) (wobei alle Kanten Liniensegmente sind) ist der Zyklus a-> b-> d-> c-> a ist nicht ein Gesicht, aber wenn wir zu (1,1) d zu verschieben, es ist ein Gesicht. Dies zeigt, warum das Konzept "Gesicht" erfordert, dass der Graph in die Ebene eingebettet wird, und warum Gesichter nicht nur aus der abstrakten Struktur des Graphen berechnet werden können.
whuber