Comment détecter des plans d'eau connectés (mais logiquement distincts) sur une carte 2D?

J'ai une carte de grille hexagonale 2D. Chaque cellule hexadécimale a une valeur de hauteur utilisée pour déterminer s'il s'agit d'eau ou d'océan. J'essaie de trouver un bon moyen de déterminer et d'étiqueter les plans d'eau. Les océans et les mers intérieures sont faciles (en utilisant un algorithme de remplissage des crues).

Mais qu'en est-il des plans d'eau comme la Méditerranée ? Plans d'eau attachés à des plans d'eau plus grands (où «mers» et «golfes» ne diffèrent que par la taille de l'ouverture)?

Voici un exemple de ce que j'essaie de détecter (la masse d'eau bleue au milieu de l'image, qui devrait être étiquetée différemment de la plus grande masse océanique à gauche, malgré sa connexion technique):

Des idées?

Ce que vous décrivez est le problème de segmentation . Je suis désolé de dire que c'est en fait un problème non résolu. Mais une méthode que je recommanderais pour cela est un algorithme basé sur Graph-Cut . Graph-Cut représente l'image sous forme de graphique de nœuds connectés localement. Il subdivise récursivement les composants connectés du graphique de telle sorte que la frontière entre les deux sous-composants est de longueur minimale en utilisant le théorème Max-flow-min-cut et le Ford Fulkerson algorithme de .

Essentiellement, vous connectez toutes les tuiles d'eau dans un graphique. Attribuez des poids aux bords du graphique qui correspondent aux différences entre les tuiles d'eau adjacentes. Je pense que dans votre cas, tous les poids pourraient être 1. Vous devrez jouer avec différents schémas de pondération pour obtenir un résultat souhaitable. Vous devrez peut-être ajouter un poids qui inclut la contiguïté aux côtes, par exemple.

Ensuite, trouvez tous les composants connectés du graphique. Ce sont des mers / lacs évidents et ainsi de suite.

Enfin, pour chaque composant connecté, subdivisez récursivement le composant de sorte que les bords reliant les deux nouveaux sous-composants aient un poids minimal . Continuez à subdiviser récursivement jusqu'à ce que tous les sous-composants atteignent une taille minimale (c'est-à-dire comme la taille maximale d'une mer), ou si les bords coupant les deux composants ont un poids trop élevé. Enfin, étiquetez tous les composants connectés qui restent.

Dans la pratique, cela se traduira par une séparation des mers les uns des autres dans les chenaux, mais pas sur de grandes étendues d'océans.

Le voici en pseudocode:

function SegmentGraphCut(Map worldMap, int minimumSeaSize, int maximumCutSize)
    Graph graph = new Graph();
    // First, build the graph from the world map.
    foreach Cell cell in worldMap:
        // The graph only contains water nodes
        if not cell.IsWater():
            continue;

        graph.AddNode(cell);

        // Connect every water node to its neighbors
        foreach Cell neighbor in cell.neighbors:
            if not neighbor.IsWater():
                continue;
            else:  
                // The weight of an edge between water nodes should be related 
                // to how "similar" the waters are. What that means is up to you. 
                // The point is to avoid dividing bodies of water that are "similar"
                graph.AddEdge(cell, neighbor, ComputeWeight(cell, neighbor));

   // Now, subdivide all of the connected components recursively:
   List<Graph> components = graph.GetConnectedComponents();

   // The seas will be added to this list
   List<Graph> seas = new List<Graph>();
   foreach Graph component in components:
       GraphCutRecursive(component, minimumSeaSize, maximumCutSize, seas);


// Recursively subdivides a component using graph cut until all subcomponents are smaller 
// than a minimum size, or all cuts are greater than a maximum cut size
function GraphCutRecursive(Graph component, int minimumSeaSize, int maximumCutSize, List<Graph> seas):
    // If the component is too small, we're done. This corresponds to a small lake,
    // or a small sea or bay
    if(component.size() <= minimumSeaSize):
        seas.Add(component);
        return;

    // Divide the component into two subgraphs with a minimum border cut between them
    // probably using the Ford-Fulkerson algorithm
    [Graph subpartA, Graph subpartB, List<Edge> cut] = GetMinimumCut(component);

    // If the cut is too large, we're done. This corresponds to a huge, bulky ocean
    // that can't be further subdivided
    if (GetTotalWeight(cut) > maximumCutSize):
        seas.Add(component);
        return;
    else:
        // Subdivide each of the new subcomponents
        GraphCutRecursive(subpartA, minimumSeaSize, maximumCutSize);
        GraphCutRecursive(subpartB, minimumSeaSize, maximumCutSize);

EDIT : Soit dit en passant, voici ce que l'algorithme ferait avec votre exemple avec une taille de mer minimale définie à environ 40, avec une taille de coupe maximale de 1, si tous les poids des bords sont 1:

En jouant avec les paramètres, vous pouvez obtenir des résultats différents. Une taille de coupe maximale de 3, par exemple, entraînerait la création de nombreuses baies dans les mers principales, et la mer n ° 1 se diviserait en deux moitiés nord et sud. Une taille de mer minimale de 20 entraînerait également la division de la mer centrale en deux.

Un moyen rapide et sale d'identifier un plan d'eau séparé mais connecté serait de rétrécir tous les plans d'eau et de voir si des lacunes apparaissent.

Dans l'exemple ci-dessus, je pense que la suppression de toutes les tuiles d'eau qui ont 2 tuiles d'eau ou moins connectées (marquées en rouge) vous fournirait le résultat souhaité plus un peu de bruit de bord. Après avoir étiqueté les corps, vous pouvez "faire couler" l'eau à son état d'origine et récupérer les tuiles retirées pour les corps désormais séparés.

Encore une fois, c'est une solution rapide et sale, elle n'est peut-être pas assez bonne pour les étapes ultérieures de la production, mais il suffira de "faire fonctionner cela pour l'instant" et de passer à une autre fonctionnalité.

Voici un algorithme complet qui, je pense, devrait produire de bons résultats.

1. Effectuer une érosion morphologique sur la zone d'eau - c'est-à-dire faire une copie de la carte sur laquelle chaque tuile est considérée comme de l'eau uniquement si elle et tous ses voisins (ou une zone plus grande, si vous avez des rivières plus larges qu'une tuile) sont de l'eau . Cela entraînera la disparition complète de toutes les rivières.

   (Cela considérera l'eau insulaire dans la partie gauche de votre mer intérieure comme des rivières. Si c'est un problème, vous pouvez utiliser une règle différente telle que celle proposée par la réponse de vrinek à la place; les étapes suivantes fonctionneront toujours tant que vous avoir une sorte d'étape «supprimer les rivières» ici.)

2. Trouvez les composants d'eau connectés de la carte érodée et attribuez à chacun une étiquette unique . (Je suppose que vous savez déjà comment faire cela.) Cela marque maintenant tout sauf les rivières et les eaux de rivage (où l'érosion a eu un effet).

3. Pour chaque tuile eau dans la carte d' origine , trouvez les étiquettes présentes sur les tuiles eau voisines dans la carte érodée puis:

   • Si la tuile elle-même a une étiquette sur la carte érodée, alors c'est de l'eau du milieu de la mer; donnez-lui cette étiquette dans la carte d'origine.
   • Si vous ne trouvez qu'une seule étiquette voisine distincte, il s'agit de la rive ou de l'embouchure de la rivière; donnez-lui cette étiquette.
   • Si vous ne trouvez pas d'étiquettes, alors c'est une rivière; laisser seul.
   • Si vous trouvez plusieurs étiquettes, il s'agit d'un goulot d'étranglement court entre deux corps plus grands; vous voudrez peut-être le considérer comme une rivière, ou combiner les deux corps sous une seule étiquette.

   (Notez que pour cette étape, vous devez conserver des grilles distinctes d'étiquettes (ou avoir deux champs d'étiquette dans une structure) pour la carte érodée (que vous lisez) et l'original (que vous écrivez), ou il y aura une itération- erreurs liées à la commande.)

4. Si vous souhaitez également étiqueter individuellement chaque rivière, après les étapes ci-dessus, recherchez tous les composants connectés restants de l'eau non étiquetée et étiquetez-les.

Suivant l'idée de vrinek, que diriez-vous de cultiver la terre (ou de rétrécir l'eau) afin que les parties que vous seriez à l'origine connectées soient déconnectées après la croissance de la terre?

Cela pourrait se faire comme suit:

1. Définissez combien vous voulez faire pousser le terrain: 1 hex? 2 hexs? Cette valeur estn

2. Visitez tous les nœuds terrestres et définissez tous leurs voisins jusqu'à la profondeur ndes nœuds terrestres (écrivez sur une copie, pour ne pas obtenir une boucle infinie)

3. Exécutez à nouveau votre algorithme de remplissage d'origine pour déterminer ce qui est maintenant connecté et ce qui ne l'est pas.

Avez-vous une idée approximative de l'endroit où se trouve le golfe? Si tel est le cas, vous pouvez modifier votre remplissage d'inondation pour suivre le nombre de cellules voisines mais inexplorées (ainsi qu'une liste des cellules visitées). Il commence par 6 dans une carte hexadécimale et chaque fois que cette valeur tombe en dessous d'un certain point, alors vous savez que vous frappez une "ouverture".