Comment déterminer les baies et les détroits dans une carte générée par procédure?

40

J'ai une carte générée de manière procédurale à l'aide de cellules de Voronoï, avec un niveau de mer défini et une carte de hauteur crédible.

Courant

Jusqu'à présent, j'ai réussi à étiqueter certaines entités géographiques: terres, océans, lacs, rivières, estuaires, confluences, montagnes et biomes. Les biomes comprennent la toundra, la forêt boréale, les prairies et les forêts tempérées. Il existe également quelques biomes, mais ils ne sont pas importants pour le moment.

J'aimerais maintenant étiqueter les baies et les détroits, mais je ne sais pas comment faire cela correctement. Une baie est un plan d'eau côtier encastré qui se connecte directement à l'océan.

Un détroit est une voie navigable étroite naturellement formée qui relie deux parties de l'océan. En gros, deux terres se touchent presque et il y a un océan des deux côtés. Aussi appelé "canal".

Pour déterminer les fonctionnalités, je peux parcourir n'importe quelle fonctionnalité par type, comme ceci:

for each (var feature:Object in geography.getFeaturesByType(Geography.LAND))
  // loop through lands
  for each (var cell:Cell in feature.cells)
  // loop through cells
    for each (var neighbor:Cell in cell.neighbors)
    // loop through a cell's neighbors
      trace(neighbor.hasFeatureType(Geography.LAND));
Olin Kirkland
la source
8
Je recommande un classificateur bayésien.
Accumulation du
1
@ Accumulation Est-ce un jeu de mots sur "bay" ou est-ce une suggestion sérieuse? Si ce dernier, vous devriez écrire une réponse appropriée à ce sujet.
Philipp
Je suis comme à 99% sûr qu'il fait une blague.
Olin Kirkland

Réponses:

29

La manière dont Dragons Abound identifie les baies consiste à marcher le long du littoral et à trouver deux points sur le littoral où la distance en ligne droite entre les points est inférieure à la distance le long du littoral entre les points. C'est la sinuosité de la côte entre les deux points. En sélectionnant une limite de sinuosité et des limites pour la distance en ligne droite entre les points, vous pouvez identifier des baies profondes et profondes, des baies larges et peu profondes, etc.

Sur cette image, les points rouges et violets indiquent les deux points candidats et la ligne verte représente le trait de côte entre les points. La sinuosité est le rapport de ces deux longueurs:

Exemple d'une baie

Vous pouvez également sélectionner deux points de la côte et créer un polygone en reliant les deux points et la ligne de côte entre les deux points (c.-à-d. Reliez la ligne verte ci-dessus du point rouge au point violet). Mesurer l'aire de ce polygone. Une baie aura une plus grande surface qu'un non-baie.

D'après mon expérience, une combinaison de ces deux mesures était la meilleure solution pour identifier de manière fiable ce que les gens considèrent comme des baies.

Notez que cela détectera également des points. Pour ne trouver que des baies, vous devez vérifier que "l'intérieur" de la baie contient de l'eau et non de la terre. Un moyen simple et rapide de procéder consiste à vérifier le point milieu de la ligne entre les deux points pour voir s’il s’agit d’eau. (Cela peut être dupe mais est généralement suffisant.)

Un problème connexe consiste à identifier "l'embouchure" de la baie - c'est-à-dire le meilleur choix pour les deux points marquant l'ouverture de la baie. En règle générale, vous aurez un groupe de candidats pour la "bouche". Dans l'exemple de carte ci-dessus, vous pouvez placer l'embouchure de la baie plus loin ou plus loin. En règle générale, cela n’a sans doute pas beaucoup d’importance, mais une heuristique qui fonctionne assez bien consiste à minimiser la distance en ligne droite à travers la bouche.

Je n'ai pas encore fait de détroits, mais mon intuition est de vérifier les points le long de la côte pour trouver le point le plus proche de toute autre côte; si c'est sous une certaine limite, c'est un détroit.

Dr. Pain
la source
3
J'aurais dû savoir que Dragons Abound aurait les réponses dont j'ai besoin.
Olin Kirkland le
48

Voici une idée approximative utilisant des transformations de traitement d'image pour isoler les caractéristiques d'intérêt:

  1. Appliquez un remplissage d'inondation à partir d'une cellule océanique pour faire un masque de toutes les cellules océaniques. Selon la configuration de vos rivières, vous aurez peut-être besoin d'un critère d'élévation ou de dégagement supplémentaire pour empêcher le masque océanique de couler à l'intérieur des terres. ;)

    Masque d'océan

  2. Appliquez un lissage local sur le bord de ce masque, en conservant la même connectivité / topologie, mais en lissant les petites caractéristiques côtières bruyantes pouvant être gênantes. Cela nous permet de nous concentrer sur les grandes baies au-dessus de petites criques. Vous pouvez utiliser la largeur de votre filtre kernal / nombre d'itérations pour contrôler avec précision l'échelle des entités que vous conservez.

    Ici, j'ai appliqué un filtre médian à quelques reprises. Les automates cellulaires sont un autre moyen populaire d’éroder des formes lisses d’une entrée bruyante.

    Littoral lissé

  3. Tournez le masque dans un champ de distance, où chaque cellule stocke sa distance depuis le littoral lissé.

    Champ de distance

Nous voyons maintenant quelques fonctionnalités prometteuses. Dans un champ de distance signé, les baies et les détroits apparaissent comme des arêtes vives, avec une distance tombant sur les côtés. Nous pouvons utiliser un filtre de détection des contours pour éliminer ces arêtes:

Ridges en surbrillance

Vous pouvez ensuite distinguer les baies et les détroits en suivant la crête pour déterminer sa connectivité. Une baie est une crête qui court vers la côte, devenant de moins en moins profonde (au loin) jusqu'à ce qu'elle se termine en pointe. Un détroit est une crête qui relie une région très éloignée à une autre région très éloignée, en passant par une région plus éloignée.

Une autre solution consiste à attribuer à chaque île un ID (recherche de composant connecté), puis, lorsque vous créez votre champ de distance, propagez "ID d’île le plus proche" le long de la frontière. Une baie ou une crique est alors une crête dans l'eau adjacente à la même masse continentale des deux côtés, tandis qu'un canal est une crête qui sépare les eaux adjacentes à deux masses continentales différentes.

Vous pouvez définir des contraintes de distance minimale et maximale entre la côte et la longueur de la crête pour contrôler les entités à étiqueter, si vous devez par exemple exclure des détroits trop étroits / larges.

DMGregory
la source
9
Cela a l'air vraiment cool, et pourrait probablement être accéléré considérablement en utilisant directement la structure de la cellule pour appliquer les différentes étapes plutôt que la représentation graphique!
Quentin
7
La deuxième approche (attribuer un identifiant à chaque masse terrestre distincte et distinguer selon qu’il s’agit de la même masse continentale des deux côtés de la masse d’eau) semble être la chose la plus facile à faire ..
Monty Harder
De toute façon, le "ID de masse terrestre" est une bonne idée, car vous en aurez également besoin dans l'étiquetage de carte pour générer des noms d'île.
MSalters
6

Fondamentalement, vous devez réfléchir à ce que vous entendez précisément par une baie ou un détroit et pourquoi vous souhaitez les différencier (est-ce pour les calculs de l'IA, ou pour étiqueter des points de repère, ou autre chose?). Jouez avec quelques définitions pour trouver celle qui vous convient le mieux. Ensuite, formulez des conditions pour vérifier vos cellules de Voronoï. Quelques suggestions:

baie

  • Toute cellule océanique ne se connectant qu’à une seule autre cellule océanique
  • OU: Toute cellule océanique connectée à plus de terre que les cellules océaniques, avec toutes les cellules océaniques côte à côte
  • OU: Idem que ci-dessus, mais avec un critère basé sur la longueur de la frontière (par exemple, deux fois plus de terre que de frontière maritime)

Détroit

  • Toute cellule océanique qui se connecte à exactement deux cellules océaniques qui ne sont pas côte à côte
  • OU: Toute cellule océanique connectée à deux cellules terrestres n'appartenant pas à la même masse continentale (vous devez savoir quelles cellules terrestres sont connectées en premier et attribuer des identifiants à chaque masse continentale).
  • OU: Marchez autour de la frontière et comptez les transitions terre / eau et eau / terre. Vous avez besoin d'au moins deux de chaque.
  • En fonction de votre méthode et de ce que vous voulez faire avec les catégories, vous voudrez peut-être éliminer les détroits qui mènent uniquement à une baie, ou les étiqueter en tant que baie.
Autolykos
la source
2
Lorsqu'un détroit mène à une baie, ces deux ensembles peuvent être qualifiés de fjord.
Philipp
1
Si les cellules sont petites par rapport à la taille d'une baie / détroit, vous devrez peut-être le propager pour examiner les cellules au-delà des voisins immédiatement adjacents.
DMGregory
Oui, la mise à l'échelle est un problème et aura une incidence sur la façon dont vous définissez les choses et déclarez les «cellules». Examinez une carte du Canada et comparez ce qui suit: baie d'Hudson, baie James, golfe du Saint-Laurent et baie de Fundy. Comment appliquez-vous de manière fiable ces règles pour obtenir les noms associés souhaités? - Y a-t-il une "ligne droite" entre Terre-Neuve et la Nouvelle-Écosse?
TheLuckless