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ół.
