Carreaux irréguliers à la surface des planètes générées de manière procédurale

Ici, nous considérerons une méthode pour diviser la surface sphérique d'une planète générée de façon procédurale avec des tuiles irrégulières, et, par conséquent, diviser l'océan et les continents en sections (secteurs) séparées. Nous supposons que la structure des zones terrestres a déjà été définie à la surface de la planète à l'aide de SIG et qu'il est possible d'exporter des données vectorielles vers des fichiers de formes ESRI ou directement vers une base de données PostgreSQL avec l'extension PostGIS . Le processus de création de secteurs s'effectue à l'aide de PostGIS.

Voir le lien vers le script avec le code SQL en bas de l'article, ici l'explication sera plus sur le doigt. L'explication fournit les fonctions de base du script, et suppose également la disponibilité des données pour les continents et les fleuves de planètes générées de manière procédurale prises sur forgedmaps.com .

Le choix de tuiles irrégulières nous permet de subdiviser avec précision la surface de la planète
en secteurs, ne mélangeant généralement pas les territoires de l'océan et de la terre n'importe où. Lacs et mers intérieures
nous le considérons comme faisant partie du territoire. Nous verrons également comment les rivières peuvent être utilisées comme limites naturelles des secteurs. Les secteurs eux-mêmes seront construits sur la base d'une division de base de la sphère par des polygones.

Quand il s'agit de diviser une région plate, ils ont généralement recours au diagramme de Voronoi pour obtenir des tuiles irrégulières. En utilisant également l'algorithme de Lloyd , nous pouvons arriver à une forme visuellement attrayante de polygones convexes qui ne sont pas très différents en taille (tessellation Centroidal Voronoi). L'essence de l'algorithme de Lloyd est de répéter la construction du diagramme de Voronoi, à chaque itération suivante, en prenant comme point de départ les centres des polygones obtenus à l'itération précédente.

Nous imposerons certaines exigences à la division de base par des polygones d'une sphère:
la convexité des polygones sphériques et leurs écarts peu importants par rapport à une taille moyenne donnée.

Le secteur du nom est utilisé à la place d'une tuile, car la tuile a généralement une signification élémentaire, par exemple, en tant que partie unitaire des cartes de tuiles des jeux stratégiques, ou en tant que partie unitaire d'une certaine surface. À l'intérieur du secteur, il y a une structure interne: le relief et divers objets géographiques. Les secteurs, à leur tour, peuvent également servir de tuiles élémentaires: la construction d'un graphique des transitions possibles entre les secteurs sert à cet effet.

La division de base de la sphère et des segments des océans.

PostGIS a une fonction ST_VoronoiPolygons , qui construit un diagramme de Voronoi dans une zone carrée. Voyons comment nous pouvons l'utiliser à nos fins.

Que se passe-t-il si vous essayez d'utiliser une approche simple? Une projection rectangulaire de la planète peut être convertie en carré par des coordonnées, y construire des polygones et effectuer la transformation inverse des coordonnées. Mais, les rectangles ainsi construits seront étirés dans une direction, ce qui ne serait pas souhaitable. Et, si vous essayez d'appliquer l'algorithme de Lloyd, les rectangles proches des pôles de la sphère seront beaucoup plus petits en surface (sur la sphère) que proches de l'équateur.

Essayons d'adapter cette méthode en éliminant les inconvénients. Les points de départ aléatoires du diagramme de Voronoi sont choisis de manière à être uniformément répartis sur la sphère. Dans la projection de Mercator, cela signifie que pour les pôles, ils devraient apparaître moins souvent avec une probabilité proportionnelle au cosinus de latitude. Nous construisons le diagramme de Voronoi dans le polygone «monde» - c'est soit la projection rectangulaire entière de la planète ou seulement une partie de celle-ci. La fonction ST_VoronoiPolygons complète elle-même le rectangle en carré, il suffit de recadrer le diagramme résultant en fonction du polygone "monde".

Nous regardons l'image des polygones de Voronoï obtenus de manière adaptée. Voici une partie de la carte de la planète test de l'équateur au bord supérieur à 73 degrés de latitude sud au bord inférieur. (Ici, le terrain a déjà été coupé des décharges.)



Comme on peut le voir sur la projection de Mercator, les polygones sont généralement plus grands à l'approche des pôles, mais ils seront répartis de manière approximativement égale sur la sphère en termes de taille de zone. Voilà ce dont nous avons besoin. Mais, on voit également que les polygones ont une très grande étendue de zones et l'image globale est plutôt disgracieuse.

Essayons d'appliquer plusieurs itérations de l'algorithme de Lloyd. Comme nouveaux points
pour les itérations ultérieures du diagramme de Voronoi, nous choisirons les centres des éléments déjà coupés
Polygone "monde" Polygones de Voronoi. Et pour éviter une trop grande réduction de la zone des polygones près des pôles, nous ne faisons qu'un petit nombre d'itérations (environ 3).

Pour obtenir des segments océaniques, la zone occupée est exclue des décharges obtenues. En conséquence, de petits polygones peuvent être formés, qu'il est souhaitable d'attacher aux voisins. De plus, de petits polygones peuvent se trouver près de la frontière du polygone «mondial». Nous connectons les polygones de manière à sélectionner le voisin «le plus proche» et à ne pas gâcher la situation dans son ensemble.

Après avoir appliqué un tel algorithme modifié, nous obtenons l'image suivante, qui peut déjà être acceptable. Les segments rouges de la figure indiquent la fusion souhaitée des polygones.



La sélection des polygones à fusionner peut se faire de différentes manières. Dans le script mentionné, 2 méthodes sont implémentées: sur la bordure la plus longue et sur le centre le plus proche. La figure suivante montre le résultat de la fusion de la deuxième manière.



En général, nous avons réalisé ce que l'on peut souhaiter des secteurs océaniques. Leur aire est approximativement la même (sur la sphère), et elles sont soit convexes soit avec de petites déviations par rapport à la convexité.

La fonction principale pour générer des secteurs océaniques:

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

world - un terrain d'entraînement «mondial» servant de frontières au monde.
avg_vp_areaKM - la superficie moyenne (km ² ) de polygones à partir de laquelle les secteurs océaniques sont créés.
merging_ratio - part de avg_vp_areaKM , de sorte que si la zone de secteur est inférieure à celle-ci, elle sera attachée à la zone voisine.
merging_method - méthode de fusion ('1' ou '2').

Un exemple. Nous construisons des secteurs dans une décharge «mondiale» donnée avec une superficie moyenne de décharges de base de 1 000 000 km ² . Les secteurs dont la superficie est inférieure à la moitié de cette taille seront joints à d'autres. La deuxième méthode de fusion est utilisée - au centre le plus proche.

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

Segments des continents.

Sur le continent, vous pouvez entrer dans une division plus intéressante, basée, d'une part, sur la totalité des petites chaînes de base, et d'autre part, sur des objets naturels tels que les rivières et les bassins versants. La structure ainsi obtenue est très similaire à la carte des États et des provinces qui s'y trouvent. Autrement dit, il s'agit du processus de génération procédurale de la carte politique du monde .

Contrairement aux segments océaniques, le renflement devient complètement facultatif.

Il n'y a pas encore de bassin versant sur forgedmaps.com, mais il y a déjà des rivières. L'utilisation de rivières dans un script nécessite leur représentation dans un MultiLineString . Ils ont cette idée dans le shapefile de riversz . Lors de l'importation dans la base de données, vous pouvez immédiatement vous débarrasser de l'excès de coordonnée z dans ce processus. D'autres données requises, à savoir les limites des zones terrestres, se trouvent dans le fichier de formes des terres . Chaque zone terrestre a un identifiant d' aid (ID de zone) et peut être constituée du continent et des îles les plus proches, ou uniquement de petites îles situées à proximité.

Pour notre exemple, nous choisissons la taille moyenne du secteur de 40 000 km ² et la taille moyenne du polygone de base de 5 000 km ² . Il s'agit d'une taille assez grande, choisie à des fins d'illustration uniquement. Des tailles plus petites sont également acceptables (jusqu'à quelques m ² ), mais gardez une trace du temps de calcul et utilisez la configuration de base de données appropriée.

Dans cette image, un exemple de l'apparence des polygones de base à l'intérieur de la zone terrestre.



L'étape suivante consiste à combiner les polygones de base en secteurs. Pour ce faire, sélectionnez au hasard dans les polygones de base autant de secteurs que nous voulons créer et attachez progressivement les polygones voisins aux secteurs accumulés.



Il est maintenant temps de prendre en compte la rivière. Nous les utilisons pour diviser les secteurs en
séparer les pièces par la fonction ST_Split . Une telle division peut être effectuée en fonction de certaines conditions: le débit final de la rivière ou la superficie de la partie séparée.

Maintenant, nous pouvons voir comment certaines frontières longent les rivières.



Nous connectons de petites parties de secteurs à de grands secteurs. Mais nous devons essayer
Ne fixez pas de pièces aux mêmes secteurs dont elles ont été coupées.



Avec de grandes surfaces, nous avons réussi, mais toujours de petites îles. Nous faisons de ceux d'entre eux qui ont une superficie proche de la superficie moyenne du secteur des secteurs distincts à la fois. Mais avec ceux dont la superficie est beaucoup plus petite que le secteur moyen, nous faisons deux choses.

1. Si ces îles sont situées relativement loin des secteurs existants, nous en faisons des secteurs séparés. L '«éloignement» dépend ici de la superficie moyenne donnée du secteur: plus cette zone est petite, plus il est probable que l'île deviendra un secteur distinct.

2. Si l'île est proche d'autres secteurs déjà créés, elle est combinée avec l'un d'eux. À savoir, avec celui qui a la plus grande surface dans un certain polygone obtenu en utilisant ST_Buffer de cette île.



Ici, quatre îles se divisent en deux secteurs différents. Si vous augmentez la zone de secteur moyenne définie, tôt ou tard toutes les îles tomberont dans un seul secteur.

La fonction principale pour générer des secteurs sur terre:

 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 - identifiant du terrain.
avg_vp_areaKM - la superficie moyenne (km ² ) des polygones de base.
avg_sector_areaKM - superficie moyenne (km ² ) des secteurs.
max_sector_cut_area_ratio - la part de avg_sector_areaKM , qui détermine la zone maximale qui peut être coupée par la rivière.
pref_min_island_area_ratio - la part de avg_sector_areaKM , qui détermine la superficie minimale, sur laquelle l'île devient immédiatement un secteur distinct.
streamflow - si la rivière a un débit final d'au moins cette valeur, alors elle participe aux secteurs de coupe.

Dans l'exemple suivant, l'utilisation de la fonction créera des secteurs sur une parcelle de terrain avec aide = 5. Dans ce cas, des polygones de base d'une superficie moyenne de 5 000 km ² seront utilisés pour créer des secteurs d'une superficie moyenne de 40 000 km ² . De plus, en même temps, le territoire maximal coupé par les rivières sera de 0,125 * 40 000 km ² , et 0,25 * 40 000 km ² est la superficie minimale à laquelle les îles deviennent immédiatement des secteurs. Pour couper les secteurs par les rivières, des rivières avec un ruissellement final minimum de 2 sont utilisées.

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

Les références

Le code de script SQL est disponible qui fait tout le travail, y compris la création de secteurs et la construction de graphiques de transition entre les secteurs voisins. Les données SIG des planètes générées de manière procédurale peuvent être extraites de forgedmaps.com . Vous pouvez utiliser les données SIG de la Terre , les menant à une structure similaire. Vous pouvez également, à l'aide de tout SIG moderne , créer des données manuellement à partir de zéro ou obtenir de nouvelles données en convertissant les données reçues de toute autre source. Des instructions plus complètes pour le script peuvent être trouvées dans le manuel .