¿Cómo puedo detectar cuerpos de agua conectados (pero lógicamente distintos) en un mapa 2D?

Tengo un mapa de cuadrícula hexagonal 2D. Cada celda hexadecimal tiene un valor de altura utilizado para determinar si es agua u océano. Estoy tratando de pensar en una buena manera de determinar y etiquetar los cuerpos de agua. Los océanos y los mares interiores son fáciles (utilizando un algoritmo de relleno de inundación).

Pero ¿qué pasa con los cuerpos de agua como el Mediterráneo ? ¿Cuerpos de agua que están unidos a otros más grandes (donde los "mares" y los "abismos" difieren solo por el tamaño de la abertura)?

Aquí hay un ejemplo de lo que estoy tratando de detectar (el cuerpo de agua azul en el centro de la imagen, que debe etiquetarse de manera diferente al cuerpo de océano más grande a la izquierda, a pesar de estar técnicamente conectado):

¿Algunas ideas?

Lo que estás describiendo es el problema de segmentación . Lamento decir que en realidad es un problema sin resolver. Pero un método que recomendaría para esto es un algoritmo basado en Graph-Cut . Graph-Cut representa la imagen como un gráfico de nodos conectados localmente. Subdivide los componentes conectados del gráfico de forma recursiva de modo que el borde entre los dos subcomponentes tenga una longitud mínima utilizando el teorema de Max-flow-min-cut y el algoritmo de Ford Fulkerson .

Básicamente, conecta todas las baldosas de agua en un gráfico. Asigne pesos a los bordes en el gráfico que corresponden a las diferencias entre las baldosas de agua adyacentes. Creo que en su caso, todos los pesos podrían ser 1. Tendrá que jugar con diferentes esquemas de ponderación para obtener un resultado deseable. Es posible que tenga que agregar algo de peso que incluya adyacencia a las costas, por ejemplo.

Luego, encuentre todos los componentes conectados del gráfico. Estos son obvios mares / lagos, etc.

Finalmente, para cada componente conectado, subdividir recursivamente el componente de manera que los bordes que conectan los dos nuevos subcomponentes tengan un peso mínimo . Siga subdividiendo recursivamente hasta que todos los subcomponentes alcancen un tamaño mínimo (es decir, como el tamaño máximo de un mar), o si los bordes que cortan los dos componentes tienen un peso demasiado alto. Finalmente, etiquete todos los componentes conectados que quedan.

Lo que esto hará en la práctica es separar los mares entre sí en los canales, pero no a través de grandes extensiones de océanos.

Aquí está en pseudocódigo:

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);

EDITAR : Por cierto, esto es lo que haría el algoritmo con su ejemplo con un tamaño mínimo del mar establecido en alrededor de 40, con un tamaño de corte máximo de 1, si todos los pesos de borde son 1:

Al jugar con los parámetros, puede obtener resultados diferentes. Un tamaño de corte máximo de 3, por ejemplo, daría como resultado que muchas más bahías se separen de los mares principales, y el mar # 1 se subdividiría en la mitad norte y sur. Un tamaño mínimo del mar de 20 daría como resultado que el mar central también se dividiera por la mitad.

Una forma rápida y sucia de identificar un cuerpo de agua separado pero conectado sería reducir todos los cuerpos de agua y ver si aparecen huecos.

En el ejemplo anterior, creo que eliminar todas las baldosas de agua que tienen 2 o menos baldosas de agua conectadas (marcadas en rojo) le proporcionaría el resultado deseable más un poco de ruido de borde. Después de haber etiquetado los cuerpos, puede "hacer fluir" el agua a su estado original y reclamar las fichas eliminadas para los cuerpos ahora separados.

Una vez más, esta es una solución rápida y sucia, puede que no sea lo suficientemente buena para las etapas posteriores de producción, pero será suficiente para "hacer que esto funcione por ahora" y pasar a alguna otra característica.

Aquí hay un algoritmo completo que creo que debería producir buenos resultados.

1. Realice erosión morfológica en el área del agua, es decir, haga una copia del mapa en el que cada baldosa se considera agua solo si ella y todos sus vecinos (o un área más grande, si tiene ríos más anchos que una baldosa) son agua . Esto dará como resultado que todos los ríos desaparezcan por completo.

   (Esto considerará que el agua isleña en la parte izquierda de su mar interior es ríos. Si esto es un problema, podría usar una regla diferente como la que propone la respuesta de vrinek ; los siguientes pasos seguirán funcionando mientras usted tener algún tipo de paso "borrar ríos" aquí).

2. Encuentre los componentes de agua conectados del mapa erosionado y asigne a cada uno una etiqueta única . (Asumo que ya sabe cómo hacer esto). Esto ahora etiqueta todo menos los ríos y el agua de la costa (donde la erosión tuvo un efecto).

3. Para cada baldosa de agua en el mapa original , busque las etiquetas presentes en las baldosas de agua vecinas en el mapa erosionado y luego:

   • Si el mosaico en sí tiene una etiqueta en el mapa erosionado, entonces es agua del medio del mar; dale esa etiqueta en el mapa original.
   • Si solo encuentra una etiqueta vecina distinta, entonces es orilla o desembocadura del río; dale esa etiqueta.
   • Si no encuentra etiquetas, entonces es un río; déjalo.
   • Si encuentra varias etiquetas, entonces es un pequeño cuello de botella entre dos cuerpos más grandes; es posible que desee considerarlo como un río o combinar los dos cuerpos bajo una sola etiqueta.

   (Tenga en cuenta que para este paso debe mantener cuadrículas de etiquetas separadas (o tener dos campos de etiqueta en una estructura) para el mapa erosionado (que leyó) y el original (en el que escribe), o habrá iteración. errores dependientes del orden).

4. Si también desea etiquetar ríos individuales de manera única, luego de los pasos anteriores, encuentre todos los componentes conectados restantes de agua sin etiquetar y márquelos.

Siguiendo la idea de vrinek, ¿qué tal si se cultiva la tierra (o se encoge el agua) para que las partes que originalmente se conectarían se desconectarían después de que la tierra haya crecido?

Esto podría hacerse así:

1. Define cuánto quieres cultivar la tierra: 1 hex. 2 hexes? Este valor esn

2. Visite todos los nodos terrestres y configure todos sus vecinos en profundidad npara aterrizar nodos (escriba en una copia, para no obtener un bucle infinito)

3. Ejecute su algoritmo de relleno original nuevamente para determinar qué está conectado ahora y qué no

¿Tienes una idea aproximada de dónde está el golfo? Si es así, puede modificar su relleno de inundación para rastrear el número de celdas vecinas pero sin explorar (junto con una lista de celdas visitadas). Comienza con 6 en un mapa hexadecimal y cada vez que ese valor cae por debajo de un cierto punto, entonces sabes que estás golpeando una "apertura".