Como posso detectar corpos de água conectados (mas logicamente distintos) em um mapa 2D?

Eu tenho um mapa de grade hexagonal 2D. Cada célula hexadecimal tem um valor de altura usado para determinar se é água ou oceano. Estou tentando pensar em uma boa maneira de determinar e rotular massas de água. Os oceanos e os mares interiores são fáceis (usando um algoritmo de preenchimento de inundação).

Mas e os corpos de água como o Mediterrâneo ? Corpos de água que estão presos aos maiores (onde "mares" e "golfos" diferem apenas pelo tamanho da abertura)?

Aqui está um exemplo do que estou tentando detectar (o corpo de água azul no meio da imagem, que deve ser rotulado diferentemente do corpo de oceano maior à esquerda, apesar de estar tecnicamente conectado):

Alguma ideia?

O que você está descrevendo é o problema de segmentação . Lamento dizer que é realmente um problema não resolvido. Mas um método que eu recomendaria para isso é um algoritmo baseado em Graph-Cut . Graph-Cut representa a imagem como um gráfico de nós conectados localmente. Ele subdivide os componentes conectados do gráfico de forma recursiva, de modo que a borda entre os dois subcomponentes seja de comprimento mínimo usando o teorema Max-flow-min-cut e o algoritmo Ford Fulkerson .

Essencialmente, você conecta todos os blocos de água em um gráfico. Atribua pesos às arestas no gráfico que correspondem às diferenças entre os ladrilhos de água adjacentes. Penso que no seu caso, todos os pesos podem ser 1. Você terá que jogar com diferentes esquemas de ponderação para obter um resultado desejável. Pode ser necessário adicionar um peso que inclua adjacência às costas, por exemplo.

Em seguida, encontre todos os componentes conectados do gráfico. São mares / lagos óbvios e assim por diante.

Finalmente, para cada componente conectado, subdividir recursivamente o componente de modo que as arestas que conectam os dois novos subcomponentes peso mínimo . Mantenha subdividir-se recursivamente até que todos os subcomponentes atinjam um tamanho mínimo (como o tamanho máximo de um mar) ou se as bordas que cortam os dois componentes tiverem um peso muito alto. Por fim, identifique todos os componentes conectados que permanecem.

O que isso fará na prática é cortar os mares um do outro nos canais, mas não em grandes extensões de oceanos.

Aqui está no 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);

EDIT : A propósito, aqui está o que o algoritmo faria com o seu exemplo com um tamanho mínimo do mar definido em torno de 40, com um tamanho máximo de corte de 1, se todos os pesos da borda forem 1:

Ao jogar com os parâmetros, você pode obter resultados diferentes. Um tamanho máximo de corte de 3, por exemplo, resultaria em muitas outras baías sendo escavadas nos mares principais, e o mar 1 seria subdividido na metade norte e sul. Um tamanho mínimo de 20 no mar resultaria na divisão do mar ao meio também.

Uma maneira rápida e suja de identificar um corpo de água separado, porém conectado, seria encolher todos os corpos de água e ver se apareceriam lacunas.

No exemplo acima, acho que a remoção de todos os ladrilhos de água que tenham 2 ou menos ladrilhos de água conectados a eles (marcados em vermelho) forneceria o resultado desejável, além de algum ruído na borda. Depois de rotular os corpos, você pode "fluir" a água ao seu estado original e recuperar os ladrilhos removidos para os corpos agora separados.

Novamente, essa é uma solução rápida e suja, pode não ser boa o suficiente para as fases posteriores da produção, mas será suficiente para "fazer com que isso funcione por enquanto" e passar para outro recurso.

Aqui está um algoritmo completo que acho que deve produzir bons resultados.

1. Realize erosão morfológica na área da água - ou seja, faça uma cópia do mapa no qual cada ladrilho é considerado apenas água se ele e todos os seus vizinhos (ou uma área maior, se você tiver rios mais largos que um ladrilho) são água . Isso resultará em todos os rios desaparecendo completamente.

   (Isso considerará a água da ilha na parte esquerda do mar interior como sendo rios. Se isso for um problema, você poderá usar uma regra diferente, como a que a resposta de vrinek propõe ; em vez disso, as etapas a seguir ainda funcionarão enquanto você faça algum tipo de "excluir rios" aqui.)

2. Encontre os componentes de água conectados no mapa erodido e dê a cada um um rótulo exclusivo . (Suponho que você já saiba como fazer isso.) Isso agora rotula tudo, exceto rios e água da costa (onde a erosão teve efeito).

3. Para cada ladrilho de água no mapa original , localize as etiquetas presentes nos ladrilhos de água vizinhos no mapa erodido e depois:

   • Se o ladrilho em si tiver uma etiqueta no mapa erodido, será água do meio do mar; dê esse rótulo no mapa original.
   • Se você encontrar apenas um rótulo vizinho distinto, é a margem ou a foz do rio; dê esse rótulo.
   • Se você não encontrar rótulos, é um rio; deixe em paz.
   • Se você encontrar vários rótulos, haverá um pequeno gargalo entre dois corpos maiores; convém considerá-lo como um rio ou combinar os dois corpos sob um único rótulo.

   (Observe que, para esta etapa, você deve manter grades separadas de rótulos (ou dois campos de rótulos em uma estrutura) para o mapa erodido (que você lê) e o original (que você escreve), ou haverá iteração- erros dependentes da ordem.)

4. Se você quiser rotular rios individuais de forma exclusiva também, depois das etapas acima, encontre todos os componentes restantes restantes de água sem rótulo e identifique-os.

Seguindo a idéia de vrinek, que tal cultivar a terra (ou encolher a água) para que partes com as quais você estaria originalmente conectado seriam desconectadas após o cultivo?

Isso pode ser feito da seguinte maneira:

1. Defina quanto você quer cultivar a terra: 1 hexadecimal? 2 hexágonos? Este valor én

2. Visite todos os nós de terra e defina todos os seus vizinhos em profundidade npara nós de terra (escreva em uma cópia, para não obter um loop infinito)

3. Execute seu algoritmo original de floodfill novamente para determinar o que agora está conectado e o que não está

Você tem uma idéia aproximada de onde está o golfo? Nesse caso, você pode modificar o preenchimento de inundação para rastrear o número de células vizinhas, mas inexploradas (junto com uma lista de células visitadas). Começa com 6 em um mapa hexadecimal e sempre que esse valor cai abaixo de um certo ponto, você sabe que está atingindo uma "abertura".