Unregelmäßige Kacheln auf der Oberfläche von prozedural erzeugten Planeten

Hier betrachten wir eine Methode zur Aufteilung der sphärischen Oberfläche eines prozedural erzeugten Planeten durch unregelmäßige Kacheln und infolgedessen die Aufteilung des Ozeans und der Kontinente in separate Abschnitte (Sektoren). Wir gehen davon aus, dass die Struktur von Landgebieten bereits mithilfe von GIS auf der Oberfläche des Planeten festgelegt wurde und es möglich ist, Vektordaten in ESRI-Shapefiles oder direkt in eine PostgreSQL-Datenbank mit der PostGIS- Erweiterung zu exportieren. Das Erstellen von Sektoren erfolgt mit PostGIS.

Siehe den Link zum Skript mit SQL-Code am Ende des Beitrags. Hier wird die Erklärung näher erläutert. Die Erklärung enthält die Grundfunktionen des Skripts und setzt auch die Verfügbarkeit von Daten für Kontinente und Flüsse prozedural erzeugter Planeten voraus, die von forgedmaps.com stammen .

Die Wahl unregelmäßiger Kacheln ermöglicht es uns, die Oberfläche des Planeten genau zu unterteilen
in Sektoren, in der Regel nicht die Gebiete des Ozeans und Land irgendwo mischen. Seen und Binnenmeere
Wir betrachten es als Teil des Landes. Wir werden auch sehen, wie Flüsse als natürliche Grenzen von Sektoren genutzt werden können. Die Sektoren selbst werden auf der Grundlage einer grundlegenden Unterteilung der Kugel durch Polygone aufgebaut.

Wenn es darum geht, einen flachen Bereich zu teilen, greifen sie normalerweise auf das Voronoi-Diagramm zurück , um unregelmäßige Kacheln zu erhalten. Wenn wir auch den Lloyd-Algorithmus anwenden, können wir zu einer visuell attraktiven Form konvexer Polygone kommen, deren Größe nicht sehr unterschiedlich ist (Centroidal Voronoi-Tessellation). Das Wesentliche des Lloyd's-Algorithmus besteht darin, die Konstruktion des Voronoi-Diagramms bei jeder nachfolgenden Iteration zu wiederholen und die Zentren der bei der vorherigen Iteration erhaltenen Polygone als Erzeugungspunkte zu verwenden.

Wir werden bestimmte Anforderungen an die Grundteilung einer Kugel durch Polygone stellen:
die Konvexität von sphärischen Polygonen und ihre nicht sehr großen Abweichungen von einer gegebenen Durchschnittsgröße.

Der Namenssektor wird anstelle eines Plättchens verwendet , da das Plättchen normalerweise eine elementare Bedeutung hat, beispielsweise als Einheitsteil der Plättchenkarten strategischer Spiele oder als Einheitsteil einer bestimmten Oberfläche. Innerhalb des Sektors gibt es eine interne Struktur: das Relief und verschiedene geografische Objekte darin. Sektoren können wiederum auch als Elementarkacheln dienen: Die Erstellung eines Diagramms möglicher Übergänge zwischen Sektoren dient diesem Zweck.

Die grundlegende Aufteilung der Kugel und der Segmente der Ozeane.

PostGIS hat eine Funktion ST_VoronoiPolygons , die ein Voronoi-Diagramm in einem quadratischen Bereich erstellt. Mal sehen, wie wir es für unsere Zwecke nutzen können.

Was passiert, wenn Sie versuchen, einen einfachen Ansatz zu verwenden? Eine rechteckige Projektion des Planeten kann durch Koordinaten in ein Quadrat umgewandelt werden, dort Polygone bilden und die inverse Transformation von Koordinaten durchführen. Die auf diese Weise konstruierten Rechtecke werden jedoch in eine Richtung gedehnt, was unerwünscht wäre. Wenn Sie versuchen, den Lloyd's-Algorithmus anzuwenden, sind die Rechtecke in der Nähe der Pole der Kugel in der Fläche (auf der Kugel) erheblich kleiner als in der Nähe des Äquators.

Versuchen wir, diese Methode so anzupassen, dass Nachteile beseitigt werden. Die zufälligen Startpunkte des Voronoi-Diagramms werden so gewählt, dass sie gleichmäßig auf der Kugel verteilt sind. In der Mercator-Projektion bedeutet dies, dass sie an den Polen seltener mit einer Wahrscheinlichkeit erscheinen sollten, die proportional zum Kosinus des Breitengrads ist. Wir bauen das Voronoi-Diagramm im Polygon „Welt“ - dies ist entweder die gesamte rechteckige Projektion des Planeten oder nur ein Teil davon. Die ST_VoronoiPolygons Funktion selbst vervollständigt das Rechteck zu einem Quadrat. Wir müssen das resultierende Diagramm nur gemäß dem "Welt" ST_VoronoiPolygons .

Wir betrachten das Bild von Voronoi-Polygonen, die auf angepasste Weise erhalten wurden. Hier ist ein Teil der Testplanetenkarte vom Äquator am oberen Rand bis zu 73 Grad südlicher Breite am unteren Rand. (Hier wurde die Landfläche bereits aus Deponien herausgeschnitten.)



Wie auf der Mercator-Projektion zu sehen ist, sind Polygone normalerweise größer, wenn sie sich den Polen nähern, aber sie sind in Bezug auf die Flächengröße ungefähr gleichmäßig über die Kugel verteilt. Das brauchen wir. Es ist jedoch auch zu sehen, dass die Polygone eine sehr große Flächenverteilung aufweisen und das Gesamtbild eher unansehnlich ist.

Versuchen wir, mehrere Iterationen des Lloyd-Algorithmus anzuwenden. Als neue Punkte
Für nachfolgende Iterationen des Voronoi-Diagramms wählen wir die Zentren des bereits getrimmten
"Welt" -Polygon Voronoi-Polygone. Und um zu verhindern, dass die Fläche der Polygone in der Nähe der Pole zu stark verkleinert wird, führen wir nur eine geringe Anzahl von Iterationen durch (etwa 3).

Um Ozeansegmente zu erhalten, wird die besetzte Fläche von den erhaltenen Deponien ausgeschlossen. Infolgedessen können kleine Polygone gebildet werden, die an benachbarte gebunden werden sollen. Außerdem können sich kleine Polygone nahe der Grenze des "Welt" -Polygons befinden. Wir verbinden die Polygone so, dass der „nächste“ Nachbar ausgewählt wird und das Gesamtbild nicht beeinträchtigt wird.

Nach Anwendung eines solchen modifizierten Algorithmus erhalten wir das folgende Bild, das möglicherweise bereits akzeptabel ist. Rote Segmente in der Abbildung zeigen die gewünschte Zusammenführung der Polygone an.



Die Auswahl der Polygone zum Zusammenführen kann auf verschiedene Arten erfolgen. In dem erwähnten Skript werden 2 Methoden implementiert: am längsten Rand und in der nächsten Mitte. Die folgende Abbildung zeigt das Ergebnis der Fusion auf die zweite Weise.



Im Allgemeinen haben wir erreicht, was von den Ozeansektoren gewünscht werden kann. Ihre Fläche ist ungefähr gleich (auf der Kugel) und sie sind entweder konvex oder weisen kleine Abweichungen von der Konvexität auf.

Die Hauptfunktion zur Erzeugung von Ozeansektoren:

 map.makeOceanSectors( world Geometry, avg_vp_areaKM Double Precision, merging_ratio Double Precision, merging_method Int ) RETURNS Void 

world - ein „Welt“ -Trainingsplatz, der als Grenzen der Welt dient.
avg_vp_areaKM - die durchschnittliche Fläche (km ² ) von Polygonen, aus denen die avg_vp_areaKM bestehen.
merging_ratio - Anteil von avg_vp_areaKM , sodass der Sektorbereich, wenn er kleiner als er ist, an den benachbarten angehängt wird.
merging_method - Zusammenführungsmethode ('1' oder '2').

Ein Beispiel. Wir bauen Sektoren auf einer bestimmten Weltdeponie mit einer durchschnittlichen Grundflächendeponie von 1.000.000 km ² . Sektoren, deren Fläche kleiner als die Hälfte dieser Größe ist, werden mit anderen verbunden. Die zweite Methode zum Zusammenführen wird verwendet - in der nächsten Mitte.

 SELECT * FROM map.makeOceanSectors( ST_GeomFromText( 'POLYGON((-75 -85, 75 -85, 75 85, -75 85, -75 -85))', 4326 ), 1000000, 0.5, 2 ); 

Segmente der Kontinente.

Auf dem Festland können Sie eine interessantere Unterteilung vornehmen, die einerseits auf der Gesamtheit der kleinen Basisbereiche und andererseits auf natürlichen Objekten wie Flüssen und Wassereinzugsgebieten basiert. Die so erhaltene Struktur ist der Karte der Staaten und Provinzen in ihnen sehr ähnlich. Das heißt, dies ist der Prozess der prozeduralen Erstellung der politischen Weltkarte .

Im Gegensatz zu Ozeansegmenten ist die Ausbuchtung völlig optional.

Bei forgedmaps.com gibt es noch keine Wassereinzugsgebiete, aber es gibt bereits Flüsse. Die Verwendung von Flüssen in einem Skript erfordert deren Darstellung in einem MultiLineString . Sie haben diese Idee im Shapefile des Flusses . Beim Import in die Datenbank können Sie die überschüssige Z-Koordinate in diesem Prozess sofort entfernen. Andere erforderliche Daten, nämlich die Grenzen von Landgebieten, befinden sich im Shapefile des Landes . Jedes Landgebiet hat eine aid (Gebiets-ID) und kann aus dem Kontinent und den nächstgelegenen Inseln oder nur kleinen Inseln in der Nähe bestehen.

In unserem Beispiel wählen wir die durchschnittliche Sektorgröße von 40.000 km ² und die durchschnittliche Größe des Basispolygons von 5.000 km ² . Dies ist eine ziemlich große Größe, die nur zur Veranschaulichung ausgewählt wurde. Kleinere Größen sind ebenfalls akzeptabel (bis zu einigen m ² ), behalten Sie jedoch die Berechnungszeit im Auge und verwenden Sie die entsprechende Datenbankkonfiguration.

In diesem Bild ein Beispiel dafür, wie die Basispolygone innerhalb der Landfläche aussehen.



Der nächste Schritt besteht darin, die Basispolygone zu Sektoren zu kombinieren. Wählen Sie dazu zufällig aus den Basispolygonen so viele Sektoren aus, wie wir erstellen möchten, und fügen Sie nach und nach benachbarte Polygone den akkumulierenden Sektoren hinzu.



Jetzt ist die Zeit gekommen, den Fluss zu berücksichtigen. Wir verwenden sie, um Sektoren in zu unterteilen
Teile durch die ST_Split Funktion ST_Split . Eine solche Aufteilung kann in Abhängigkeit von bestimmten Bedingungen durchgeführt werden: dem endgültigen Flussfluss oder der Fläche des abgetrennten Teils.

Jetzt können wir sehen, wie einige Grenzen entlang der Flüsse verlaufen.



Wir verbinden kleine Teile von Sektoren mit großen Sektoren. Aber wir müssen es versuchen
Befestigen Sie keine Teile an denselben Sektoren, von denen sie abgeschnitten wurden.



Mit großen Landflächen haben wir es geschafft, aber immer noch kleine Inseln. Wir machen diejenigen von ihnen, die eine Fläche nahe der durchschnittlichen Fläche des Sektors haben, gleichzeitig zu getrennten Sektoren. Aber mit denen, deren Fläche viel kleiner als der durchschnittliche Sektor ist, machen wir zwei Dinge.

1. Wenn solche Inseln relativ weit von bestehenden Sektoren entfernt sind, machen wir sie zu getrennten Sektoren. „Farness“ hängt hier von der gegebenen durchschnittlichen Fläche des Sektors ab: Je kleiner diese Fläche ist, desto wahrscheinlicher ist es, dass die Insel zu einem separaten Sektor wird.

2. Befindet sich die Insel in der Nähe anderer bereits erstellter Sektoren, wird sie mit einem dieser Sektoren kombiniert. Mit demjenigen, der die größte Fläche in einem bestimmten Polygon hat, das mit ST_Buffer von dieser Insel erhalten wurde.



Hier fielen vier Inseln in zwei verschiedene Sektoren. Wenn Sie die festgelegte durchschnittliche Sektorfläche erhöhen, fallen früher oder später alle Inseln in einen einzigen Sektor.

Die Hauptfunktion zur Erzeugung von Sektoren an Land:

 map.makeLandSectors( aid BigInt, avg_vp_areaKM Double Precision, avg_sector_areaKM Double Precision, max_sector_cut_area_ratio Float, pref_min_island_area_ratio Float, min_streamflow Int ) RETURNS Void 

aid - Kennung des Grundstücks.
avg_vp_areaKM - die durchschnittliche Fläche (km ² ) der Basispolygone.
avg_sector_areaKM - durchschnittliche Fläche (km ² ) der Sektoren.
max_sector_cut_area_ratio - Der Anteil von avg_sector_areaKM , der die maximale Fläche bestimmt, die vom Fluss abgeschnitten werden kann.
pref_min_island_area_ratio - der Anteil von avg_sector_areaKM , der die Mindestfläche bestimmt, mit der die Insel sofort zu einem separaten Sektor wird.
streamflow - Wenn der Fluss einen streamflow von mindestens diesem Wert hat, nimmt er an Schnittsektoren teil.

Im folgenden Beispiel werden mit der Funktion Sektoren auf einem Grundstück mit Hilfe = 5 erstellt. In diesem Fall werden Basispolygone mit einer durchschnittlichen Fläche von 5.000 km ² verwendet, um Sektoren mit einer durchschnittlichen Fläche von 40.000 km ² zu erstellen. Gleichzeitig beträgt das maximale Gebiet, das von Flüssen abgeschnitten wird, 0,125 * 40.000 km ² , und 0,25 * 40.000 km ² ist das Mindestgebiet, auf dem die Inseln sofort zu Sektoren werden. Um Sektoren nach Flüssen zu schneiden, werden Flüsse mit einem Mindestabfluss von 2 verwendet.

 SELECT * FROM map.makeLandSectors(5, 5000, 40000, 0.125, 0.25, 2); 

Referenzen

Es ist SQL-Skriptcode verfügbar, der die gesamte Arbeit erledigt, einschließlich der Erstellung von Sektoren und der Erstellung von Übergangsgraphen zwischen benachbarten Sektoren. GIS-Daten von prozedural generierten Planeten können von forgedmaps.com abgerufen werden . Sie können GIS-Erddaten verwenden , die zu einer ähnlichen Struktur führen. Sie können mit jedem modernen GIS auch Daten manuell von Grund auf neu erstellen oder neue Daten erhalten, indem Sie Daten konvertieren, die von einer anderen Quelle empfangen wurden. Ausführlichere Anweisungen für das Skript finden Sie im Handbuch .