Wie kann ich zusammenhängende (aber logisch getrennte) Gewässer in einer 2D-Karte erkennen?

Ich habe eine hexagonale 2D-Gitterkarte. Jede hexadezimale Zelle hat einen Höhenwert, mit dem bestimmt wird, ob es sich um Wasser oder Ozean handelt. Ich versuche, eine gute Methode zu finden, um Gewässer zu bestimmen und zu kennzeichnen. Ozeane und Binnenmeere sind einfach (mithilfe eines Flutfüllungsalgorithmus).

Aber was ist mit Gewässern wie dem Mittelmeer ? Gewässer, die an größere Gewässer gebunden sind (wobei sich "Meere" und "Golf" nur durch die Größe der Öffnung unterscheiden)?

Hier ist ein Beispiel für das, was ich zu erkennen versuche (das blaue Gewässer in der Mitte des Bildes, das trotz technischer Verbindung anders als das größere Gewässer auf der linken Seite beschriftet werden sollte):

Irgendwelche Ideen?

Was Sie beschreiben, ist das Segmentierungsproblem . Es tut mir leid zu sagen, dass es sich tatsächlich um ein ungelöstes Problem handelt. Eine Methode, die ich dafür empfehlen würde, ist ein Graph-Cut- basierter Algorithmus. Graph-Cut repräsentiert das Bild als Graph lokal verbundener Knoten. Es unterteilt zusammenhängende Komponenten des Graphen rekursiv so, dass die Grenze zwischen den beiden Unterkomponenten unter Verwendung des Max-Flow-Min-Cut-Theorems und des Ford-Fulkerson- Algorithmus von minimaler Länge ist .

Im Wesentlichen verbinden Sie alle Wasserplättchen zu einem Diagramm. Weisen Sie den Kanten in der Grafik Gewichte zu, die den Unterschieden zwischen den benachbarten Wasserplättchen entsprechen. Ich denke, in Ihrem Fall könnten alle Gewichte 1 sein. Sie müssen mit verschiedenen Gewichtungsschemata spielen, um ein wünschenswertes Ergebnis zu erzielen. Möglicherweise müssen Sie ein Gewicht hinzufügen, das beispielsweise die Nähe zu Küsten umfasst.

Suchen Sie dann alle verbundenen Komponenten des Diagramms. Dies sind offensichtliche Meere / Seen und so weiter.

Teilen Sie die Komponente schließlich für jede verbundene Komponente rekursiv so auf, dass die Kanten, die die beiden neuen Unterkomponenten verbinden, ein Mindestgewicht haben . Untergliedern Sie weiter rekursiv, bis alle Unterkomponenten eine minimale Größe erreicht haben (dh wie die maximale Größe eines Meeres), oder wenn die Kanten, die die beiden Komponenten schneiden, ein zu hohes Gewicht haben. Beschriften Sie abschließend alle angeschlossenen Komponenten, die noch vorhanden sind.

In der Praxis wird dies dazu führen, dass die Meere an Kanälen voneinander getrennt werden, jedoch nicht über große Ozeane hinweg.

Hier ist es im 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 : Übrigens, hier ist, was der Algorithmus mit Ihrem Beispiel mit einer minimalen Meeresgröße von ungefähr 40 und einer maximalen Schnittgröße von 1 machen würde, wenn alle Kantengewichte 1 sind:

Indem Sie mit den Parametern spielen, können Sie unterschiedliche Ergebnisse erzielen. Eine maximale Schnittgröße von 3 würde zum Beispiel dazu führen, dass viel mehr Buchten aus den Hauptmeeren herausgearbeitet werden, und das Meer Nr. 1 würde in die Hälften Nord und Süd unterteilt. Eine minimale Meeresgröße von 20 würde dazu führen, dass das Zentralmeer ebenfalls in zwei Hälften geteilt wird.

Eine schnelle und schmutzige Möglichkeit, ein separates, aber zusammenhängendes Gewässer zu identifizieren, besteht darin, alle Gewässer zu verkleinern und zu prüfen, ob Lücken auftreten.

Im obigen Beispiel denke ich, dass das Entfernen aller Wasserplättchen, mit denen 2 oder weniger Wasserplättchen verbunden sind (rot markiert), das gewünschte Ergebnis plus etwas Kantenrauschen liefert. Nachdem Sie die Körper markiert haben, können Sie das Wasser in seinen ursprünglichen Zustand "fließen lassen" und die entfernten Kacheln für die nun getrennten Körper zurückfordern.

Auch dies ist eine schnelle und schmutzige Lösung, die für die späteren Produktionsphasen möglicherweise nicht gut genug ist, aber es wird ausreichen, "dies erst einmal zum Laufen zu bringen" und sich einer anderen Funktion zuzuwenden.

Hier ist ein vollständiger Algorithmus, der meiner Meinung nach gute Ergebnisse liefern sollte.

1. Führen Sie eine morphologische Erosion auf dem Wassergebiet durch. Erstellen Sie also eine Kopie der Karte, auf der jedes Feld nur dann als Wasser gilt , wenn es und alle seine Nachbarn (oder ein größeres Gebiet, wenn Sie Flüsse haben, die breiter als ein Feld sind) Wasser sind . Dies führt dazu, dass alle Flüsse vollständig verschwinden.

   (Dies wird das Inselwasser im linken Teil Ihres Binnenmeeres als Flüsse betrachten. Wenn dies ein Problem ist, können Sie eine andere Regel verwenden, wie sie die Antwort von vrinek vorschlägt . Die folgenden Schritte funktionieren immer noch, solange Sie dies tun habe hier eine Art "Flüsse löschen" -Schritt.)

2. Finden Sie die angeschlossenen Wasserkomponenten der erodierten Karte und geben Sie jedem eine eindeutige Bezeichnung. (Ich nehme an, Sie wissen bereits, wie man das macht.) Dies kennzeichnet jetzt alles außer Flüssen und Uferwasser (wo die Erosion eine Auswirkung hatte).

3. Suchen Sie für jedes Wasserplättchen in der Originalkarte die Beschriftungen auf den benachbarten Wasserplättchen in der erodierten Karte und führen Sie dann folgende Schritte aus:

   • Wenn die Kachel selbst ein Etikett in der erodierten Karte hat, handelt es sich um Meerwasser. Gib ihm das Etikett in der Originalkarte.
   • Wenn Sie nur ein bestimmtes benachbartes Etikett finden, handelt es sich um die Ufer- oder Flussmündung. Gib ihm das Etikett.
   • Wenn Sie keine Etiketten finden, dann ist es ein Fluss; lass es in Ruhe.
   • Wenn Sie mehrere Bezeichnungen finden, ist dies ein kurzer Engpass zwischen zwei größeren Körpern. Vielleicht möchten Sie ihn entweder als Fluss betrachten oder die beiden Körper unter einer einzigen Bezeichnung zusammenfassen.

   (Beachten Sie, dass Sie für diesen Schritt separate Etikettengitter (oder zwei Etikettenfelder in einer Struktur) für die erodierte Karte (von der Sie lesen) und das Original (auf das Sie schreiben) aufbewahren müssen. Andernfalls wird es zu einer Iteration kommen.) auftragsabhängige Fehler.)

4. Wenn Sie einzelne Flüsse auch eindeutig kennzeichnen möchten, suchen Sie nach den obigen Schritten alle verbleibenden angeschlossenen Komponenten des nicht gekennzeichneten Wassers und kennzeichnen Sie sie.

Wie wäre es, wenn Sie, der Idee von vrinek folgend, das Land anbauen (oder das Wasser schrumpfen lassen), sodass Teile, mit denen Sie ursprünglich verbunden waren, nach dem Anbau des Landes nicht mehr verbunden sind?

Das könnte so gemacht werden:

1. Bestimmen Sie, wie viel Sie das Land anbauen möchten: 1 Feld? 2 Verhexungen? Dieser Wert istn

2. Besuche alle Landknoten und setze alle Nachbarn auf die Tiefe n, um Knoten zu landen (schreibe in eine Kopie, um keine Endlosschleife zu erhalten)

3. Führen Sie den ursprünglichen Floodfill-Algorithmus erneut aus, um festzustellen, was jetzt verbunden ist und was nicht

Haben Sie eine ungefähre Vorstellung davon, wo sich der Golf befindet? In diesem Fall können Sie Ihre Überflutungsfüllung ändern, um die Anzahl der benachbarten, aber nicht erkundeten Zellen (zusammen mit einer Liste der besuchten Zellen) zu verfolgen. Es beginnt mit 6 in einer Hex-Karte und wenn dieser Wert unter einen bestimmten Punkt fällt, dann wissen Sie, dass Sie eine "Öffnung" treffen.