Netzgenerierung für prozeduralen Stadtgenerator

Ich habe ein Programmierproblem im Zusammenhang mit der Netzgenerierung für Stadtnetze. Ich habe kürzlich einen Stadtnetzgenerator erstellt und bin so weit gekommen, das Straßennetz für das von meinem System ausgespuckte Netz zuverlässig zu generieren. Jetzt bin ich jedoch nicht mehr in der Lage, eine Methode zu finden, um die Grundstücke und Zwischenräume zwischen den Straßen zu erzeugen. Schließlich möchte ich, dass das Stadtgitter Höhenänderungen aufweist, und dafür muss ich in der Lage sein, die Zwischenräume zwischen den Straßen auszufüllen.

Hier ist ein Beispiel für das, was ich habe:

Ich habe mich mit Triangulationsmethoden wie Delauney Triangulation befasst, aber die Ausgabe ist unzuverlässig (möglicherweise aufgrund der Art und Weise, wie ich sie verwende). Hier ist ein weiteres Beispiel, das das Problem zeigt (die schwarzen Linien sind das Straßennetz, die magentafarbenen sind die Delauney-Ausgabe):

Zum größten Teil folgt die Delauney-Ausgabe dem Netz, wenn ich es nur mit den Eckpunkten präsentiere, aus denen die Schnittpunkte bestehen. Manchmal überlappen sich die Delauney-Dreiecke jedoch mit denen des Straßennetzes (wie bei der breiten Straße in der Bildmitte). Ich verwende einen Port von as2Delauney für Unity und erstelle einfach eine Liste aller Eckpunkte, aus denen die Schnittpunkte bestehen, und übergebe sie dann an die Delauney-Funktion. Ich frage mich, ob ich etwas berücksichtigen muss, bevor ich eine Reihe von Punkten und übergebe Lassen Sie die Funktion es aussortieren.

Gibt es spezielle Überlegungen, die ich bei der Verwendung von Delauney für diese Art der Triangulation berücksichtigen muss, oder gibt es andere Methoden, mit denen ich die Füllungen für das Straßennetz erstellen kann?

Ich habe darüber nachgedacht, eine Funktion zu erstellen, die versucht, den Kreuzungen im oder gegen den Uhrzeigersinn zu folgen, bis sie wieder zum Start zurückkehrt. Dies würde jedoch zu Endlosschleifen führen, da einige Straßen Sackgassen sind.

Im Moment bin ich mir nicht sicher, wonach ich suchen soll, da mir die Terminologie fehlt und Google keine Ergebnisse hinsichtlich der Methoden geliefert hat, mit denen ich die Füllungen für das Straßennetz generieren könnte (es gibt einige gute Informationen zur Stadterzeugung, jedoch nicht auf dem Maschenteil).

Hat jemand irgendwelche Erfahrungen damit?

Bearbeiten: So funktioniert mein System:

Grundsätzlich verwende ich eine offene Liste von Leitungen, um mein Netzwerk zu erweitern, und überprüfe die Leitungen anhand einer Reihe von Einschränkungen. Dann gehe ich jede Linie durch und generiere Schnittpunkte für jeden Start- und Endpunkt. Wenn das Ende / der Start bereits in meiner Liste enthalten ist, füge ich den anderen Punkt als Ziel für die aktuelle Kreuzung hinzu.

Am Ende habe ich eine Liste von benutzerdefinierten Objekten, die ihren eigenen Positionsvektor und alle Positionsvektoren der Schnittpunkte enthalten, mit denen sie verbunden sind. Damit erstelle ich dann die Netzpunkte für den Schnittpunkt, indem ich die Schnittpunkte der Linien überprüfe, aus denen die Seiten der Straßen bestehen. Ich habe diese Punkte zur Verfügung und verwende sie, um die Dreiecke für mein Netz zu erstellen.

Jetzt muss ich nur noch wissen, wie man sie organisiert, um die Füllungen zu erstellen, die sich über mehrere Schnittpunkte erstrecken.

Es gibt eine Variante der Delaunay-Triangulation: Mit der eingeschränkten Delaunay-Triangulation können Sie festlegen, welche Kanten niemals umgedreht werden sollen, z. B. in Ihrem Anwendungsfall die Kanten, die zu Straßen gehören.

Leider kann ich für Bibliotheken, die eine eingeschränkte Verzögerung implementieren, nur CGAL erwähnen, das C ++ ist und unter der GPL veröffentlicht wird: http://doc.cgal.org/Manual/3.3/doc_html/cgal_manual/Triangulation_2_ref/Class_Constrained_Delaunay_triangulation_2. html

Auf diese Weise können Sie die Zwischenräume zwischen Straßen richtig triangulieren, ohne die Straßenpolygone zu beschädigen. Sie könnten dann so etwas wie die in "Prozedurale Erzeugung von Paketen in der Stadtmodellierung" von P. Cignoni und T. Ertl ( https://www.cs.purdue.edu/cgvlab/papers/aliaga/eg2012.pdf ) beschriebenen Methoden verwenden. die resultierenden Stadtblöcke in Parzellen zu teilen.

TL; DR: Einer der einfacheren Algorithmen, die in diesem Artikel vorgestellt werden, sieht folgendermaßen aus:

Für jeden Abstand zwischen Straßen: Generieren Sie den orientierten Begrenzungsrahmen (OBB), teilen Sie das Polygon entlang der längsten Achse und wiederholen Sie den Vorgang für die resultierenden kleineren OBBs, bis sie erfüllt sind. Dann platzieren Sie Gebäude nach Geschmack.

Problem

Sie benötigen Konsistenz in Ihren Systemen / Datenstrukturen. Aus Ihrem Bild geht hervor, dass Sie:

1. Generieren Sie die Grundlagen in einem regulären Raster / 2D-Array, in dem Sie mScheitelpunkte und nScheitelpunkte für ein m x nRaster haben. Dann haben Sie m-1Zwischenräume über und n-1Zwischenräume nach unten. (Dies berücksichtigt nur Kreuzungen, nicht die Aufteilung jeder Straße in zwei Segmente. Es werden auch keine Erweiterungen / Einschlüsse berücksichtigt - siehe "Hauptstraße" weiter unten.)
2. Teilen Sie jedes Straßensegment in 2 Bereiche / 4 Tris auf. Ich denke, um die kurvigen Straßen zu unterstützen (siehe nächster Schritt).
3. Stören Sie diese resultierenden Punkte oder wenden Sie auf andere Weise eine Transformation auf den gesamten Raum an. Dies gibt verschiedenen Stadtteilen subtile Krümmungen.
4. Versuchen Sie, das Netz der Lose (Zwischenräume) über den Rest zu legen.

Resultierende Probleme:

1. Sie verfolgen diese Teilungen in Schritt 2 in Ihrem Basisarray nicht. Durch Hinzufügen dieser Teilungen haben Sie die Anzahl der Punkte ungefähr verdoppelt, aber das Basisarray spiegelt nicht die neu erstellten Scheitelpunkte wider . In Schritt 4 oben stimmen Sie also nicht genau mit den Scheitelpunkten überein.
2. Es scheint, dass eine spezielle "Hauptstraße" durch die Stadt verläuft, die sich nicht in der ursprünglichen Datenstruktur widerspiegelt, die Sie zum Generieren des Los- / Zwischenraumnetzes verwenden.
3. Wenn Sie ein 2D-Array als Basisdaten verwenden, erhalten Sie Kreuzungen, bei denen Sie sie wahrscheinlich nicht möchten.

Zur weiteren Verdeutlichung habe ich einige Zwischenlinien über die Zwischenräume gelegt ( [0]s in Lösung, unten):

Lösung

Sie benötigen eine Zwischendatenstruktur, die Ihre Sonderfall-Ergänzungen enthalten kann (Aufteilung jedes Straßensegments in 2 Bereiche / 4 Tris und Erzeugung einer Hauptstraße nach der gesamten Netzgenerierung). Sie sollten einen verwenden Graph , in dem jeder Knoten nicht eine Straße darstellt Kreuzung , sondern jede Zeile nach unten, wo wir Straße geteilt Segmente , und wo jede Kante repräsentiert ein Segment der Straße, zum Beispiel

[I]--[0]--[I]--[0]--[0]--[0]--[I]->
 |Lot1     |Lot2               |
[0]       [0]                 [0]
 |         |                   |
[I]--[0]--[I]--[0]--[0]--[0]--[I]->
 |         |                   |
 V         V                   V

[0]= Teilungen in der Straße, das sind im Grunde Eckpunkte, an denen Sie jedes Straßensegment in zwei Rechtecke aufteilen. [I]= Kreuzungen. Beachten Sie, dass es oben und unten Lot24 Straßensegmente gibt, nicht nur 2. Dies soll veranschaulichen, wie Sie die durchlaufende Hauptstraße durch Ersetzen des Knotens hinzufügen können:

[I]--[0]--[I]--[0]--[I]--[0]--[I]->
 |Lot1     |Lot2     + Lot3    |
[0]       [0]       [0]       [0]
 |         |         +         |
[I]--[0]--[I]--[0]--[I]--[0]--[I]->
 |         |         +         |
 V         V         V         V

Oder man könnte hinzufügen , es in die bestehenden nodeset anstatt zu ersetzen :

[I]--[0]--[I]--[0]--[0]--[I]--[0]--[I]->
 |Lot1     |Lot2          + Lot3    |
[0]       [0]            [0]       [0]
 |         |              +         |
[I]--[0]--[I]--[0]--[0]--[I]--[0]--[I]->
 |         |              +         |
 V         V              V         V

Schließlich können Sie jeden dieser Knoten auf spezielle "Losknoten" in der Mitte verweisen lassen:

[I]--[0]--[I]
 | \     / |
[0]-[L1]--[0]
 | /     \ | 
[I]--[0]--[I]

Aus dem oben genannten Diagramm, das vollständig (einschließlich der Hauptstraße) generiert wurde, können Sie dann Ihre Netze generieren. Denken Sie daran: Aktualisieren Sie zuerst Daten / Modell (oben) und dann Ansichten (Netzinformationen). Wie Sie Ihre Ergänzungen in der letzten Phase triangulieren , unterscheidet sich grundlegend von den Problemen, mit denen Sie konfrontiert sind.

Schließlich möchten Sie wahrscheinlich wirklich, dass ein einziges Netz alles, viele Grundstücke und Straßen darstellt. Nur Gebäude würden wahrscheinlich getrennt gehalten.