Jak mogę wykryć połączone (ale logicznie odrębne) zbiorniki wodne na mapie 2D?

Mam mapę siatki sześciokątnej 2D. Każda komórka szesnastkowa ma wartość wysokości używaną do ustalenia, czy jest to woda, czy ocean. Próbuję wymyślić dobry sposób na określenie i oznakowanie zbiorników wodnych. Oceany i morza śródlądowe są łatwe (przy użyciu algorytmu wypełniania powodzi).

Ale co z akwenami takimi jak Morze Śródziemne ? Zbiorniki wodne, które są przymocowane do większych (gdzie „morza” i „zatoki” różnią się tylko wielkością otworu)?

Oto przykład tego, co próbuję wykryć (niebieski zbiornik wodny na środku obrazu, który powinien być oznaczony inaczej niż większy zbiornik oceanu po lewej stronie, mimo że jest technicznie połączony):

Jakieś pomysły?

Co ty opisujesz jest segmentacja problem . Przykro mi to mówić, że to w rzeczywistości nierozwiązany problem. Ale jedna metoda Polecam za to Graph-Cut algorytm oparty. Graph-Cut reprezentuje obraz jako wykres lokalnie połączonych węzłów. Podział połączonych elementów wykresu dzieli się rekurencyjnie tak, że granica między dwoma podskładnikami ma minimalną długość przy użyciu twierdzenia Max-flow-min-cut i algorytmu Forda Fulkersona .

Zasadniczo łączysz wszystkie płytki wodne w wykres. Przypisz wagi do krawędzi na wykresie, które odpowiadają różnicom między sąsiadującymi płytkami wodnymi. Myślę, że w twoim przypadku wszystkie wagi mogą wynosić 1. Będziesz musiał grać z różnymi schematami ważenia, aby uzyskać pożądany wynik. Może być konieczne dodanie dodatkowej wagi, na przykład przyleganie do wybrzeży.

Następnie znajdź wszystkie połączone elementy wykresu. Są to oczywiste morza / jeziora i tak dalej.

Na koniec, dla każdego podłączonego komponentu, rekurencyjnie podziel ten komponent tak, aby krawędzie łączące dwa nowe komponenty miały minimalną wagę . Kontynuuj rekurencyjne dzielenie, aż wszystkie podskładniki osiągną minimalny rozmiar (tj. Jak maksymalny rozmiar morza) lub jeśli krawędzie przecinające oba składniki będą miały zbyt duży ciężar. Na koniec oznacz wszystkie pozostałe podłączone elementy.

W praktyce zrobi to odcięcie mórz od siebie w kanałach, ale nie w poprzek dużych oceanów.

Oto pseudokod:

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

EDYCJA : Przy okazji, oto co algorytm zrobiłby z twoim przykładem z minimalnym rozmiarem morza ustawionym na około 40, z maksymalnym rozmiarem cięcia 1, jeśli wszystkie grubości krawędzi wynoszą 1:

Grając z parametrami, możesz uzyskać różne wyniki. Na przykład maksymalny rozmiar cięcia wynoszący 3 spowodowałby wycięcie o wiele więcej zatok z głównych mórz, a morze nr 1 podzieliłoby się na pół na północ i południe. Minimalna wielkość morza wynosząca 20 spowodowałaby podział morza środkowego również na pół.

Szybkim i brudnym sposobem zidentyfikowania oddzielnego, ale połączonego akwenu byłoby zmniejszenie wszystkich jednolitych części wód i sprawdzenie, czy pojawią się luki.

W powyższym przykładzie myślę, że usunięcie wszystkich kafelków wody, które są połączone z 2 lub mniej kafelkami wody (zaznaczone na czerwono), zapewni pożądany efekt plus pewien szum krawędzi. Po oznaczeniu ciał możesz „przepłynąć” wodą do jej pierwotnego stanu i odzyskać usunięte płytki dla już oddzielnych ciał.

Ponownie, jest to szybkie i brudne rozwiązanie, może nie być wystarczające na późniejszych etapach produkcji, ale wystarczy „uruchomić na razie” i przejść do innej funkcji.

Oto kompletny algorytm, który moim zdaniem powinien dać dobre wyniki.

1. Wykonaj erozję morfologiczną na obszarze wodnym - to znaczy wykonaj kopię mapy, na której każdy kafelek jest uważany za wodę tylko wtedy, gdy on i wszyscy jego sąsiedzi (lub większy obszar, jeśli masz rzeki szersze niż jeden kafelek) są wodą . Spowoduje to całkowite zniknięcie wszystkich rzek.

   (Będzie to traktować wody wyspowe w lewej części twojego śródlądowego morza jako rzeki. Jeśli jest to problem, możesz użyć innej reguły, takiej jak ta, którą proponuje odpowiedź vrinek ; kolejne kroki będą nadal działać, dopóki będziesz wykonaj tutaj krok „usuń rzeki”).

2. Znajdź połączone elementy wodne erodowanej mapy i nadaj każdemu z nich unikalną etykietę. (Zakładam, że już wiesz, jak to zrobić.) To teraz oznacza wszystko oprócz rzek i wód przybrzeżnych (gdzie erozja miała wpływ).

3. Dla każdej płytki wodnej w oryginale mapie znajdź etykiety znajdujące się na sąsiadujących kafelkach wody na zniszczonej mapie, a następnie:

   • Jeśli sam kafelek ma etykietę na zniszczonej mapie, oznacza to wodę w środkowej części morza; nadaj mu tę etykietę na oryginalnej mapie.
   • Jeśli znajdziesz tylko jedną wyraźną sąsiednią etykietę, oznacza to ujście brzegu lub rzeki; nadaj mu tę etykietę.
   • Jeśli nie znajdziesz żadnych etykiet, oznacza to rzekę; Zostaw to w spokoju.
   • Jeśli znajdziesz wiele etykiet, oznacza to krótkie wąskie gardło między dwoma większymi ciałami; możesz rozważyć to jako rzekę lub połączyć dwa ciała pod jedną etykietą.

   (Pamiętaj, że dla tego kroku musisz zachować osobne siatki etykiet (lub mieć dwa pola etykiet w jednej strukturze) dla mapy erodowanej (z której czytasz) i oryginalnej (do której piszesz), w przeciwnym razie nastąpi iteracja błędy zależne od zamówienia).

4. Jeśli chcesz także w unikalny sposób oznaczyć poszczególne rzeki, po powyższych krokach znajdź wszystkie pozostałe połączone elementy nieoznakowanej wody i oznacz je.

Idąc za pomysłem vrinka, co powiesz na uprawę ziemi (lub zmniejszenie wody), aby części, które pierwotnie byłyby połączone, zostały rozłączone po uprawie ziemi?

Można to zrobić w następujący sposób:

1. Określ, ile chcesz uprawiać ziemię: 1 hex? 2 heksy? Ta wartość ton

2. Odwiedź wszystkie węzły lądowe i ustaw wszystkich sąsiadów na głębokość, naby węzły lądowe (napisz do kopii, aby nie uzyskać nieskończonej pętli)

3. Uruchom ponownie oryginalny algorytm wypełniania, aby ustalić, co jest teraz połączone, a co nie

Czy masz ogólne pojęcie, gdzie jest zatoka? Jeśli tak, możesz zmodyfikować wypełnienie zalewowe, aby śledzić liczbę sąsiednich, ale niezbadanych komórek (wraz z listą odwiedzonych komórek). Zaczyna się od 6 na mapie heksadecymalnej i za każdym razem, gdy wartość spada poniżej pewnego punktu, wiesz, że trafiasz w „otwarcie”.