Bagaimana saya bisa mendeteksi badan air yang terhubung (tapi berbeda secara logis) dalam peta 2D?

Saya memiliki peta grid heksagonal 2D. Setiap sel hex memiliki nilai ketinggian yang digunakan untuk menentukan apakah itu air atau laut. Saya mencoba memikirkan cara yang baik untuk menentukan dan memberi label badan air. Lautan dan laut pedalaman mudah (menggunakan algoritma pengisian banjir).

Tapi bagaimana dengan perairan seperti Mediterania ? Perairan yang melekat pada yang lebih besar (di mana "laut" dan "jurang" berbeda hanya dengan ukuran pembukaan)?

Berikut adalah contoh dari apa yang saya coba deteksi (badan air biru di tengah gambar, yang harus diberi label berbeda dari badan lautan yang lebih besar di sebelah kiri, meskipun secara teknis terhubung):

Ada ide?

Apa yang Anda gambarkan adalah Masalah Segmentasi . Saya minta maaf untuk mengatakan bahwa itu sebenarnya masalah yang belum terpecahkan. Tapi satu metode yang saya sarankan untuk ini adalah algoritma berbasis Graph-Cut . Graph-Cut mewakili gambar sebagai grafik dari node yang terhubung secara lokal. Ini membagi komponen yang terhubung dari grafik secara rekursif sehingga perbatasan antara dua sub-komponen memiliki panjang minimal menggunakan teorema Max-flow-min-cut dan algoritma Ford Fulkerson .

Intinya, Anda menghubungkan semua ubin air ke dalam grafik. Tetapkan bobot ke tepi pada grafik yang sesuai dengan perbedaan antara ubin air yang berdekatan. Saya pikir dalam kasus Anda, semua bobot bisa 1. Anda harus bermain dengan skema pembobotan yang berbeda untuk mendapatkan hasil yang diinginkan. Anda mungkin harus menambahkan beberapa bobot yang mencakup kedekatan dengan pantai, misalnya.

Kemudian, cari semua komponen grafik yang terhubung. Ini jelas laut / danau dan sebagainya.

Akhirnya, untuk setiap komponen yang terhubung, membagi komponen secara rekursif sedemikian rupa sehingga ujung-ujung yang menghubungkan dua sub-komponen baru memiliki bobot minimum . Teruslah membagi secara rekursif sampai semua sub-komponen mencapai ukuran minimum (yaitu seperti ukuran maksimum laut), atau jika tepian yang memotong kedua komponen memiliki bobot terlalu tinggi. Terakhir, beri label semua komponen yang terhubung yang tersisa.

Apa yang akan dilakukan dalam praktik ini adalah memotong laut dari satu sama lain di saluran, tetapi tidak melintasi samudera besar.

Ini dia dalam 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 : Omong-omong, inilah yang akan dilakukan algoritme dengan contoh Anda dengan ukuran laut minimum yang ditetapkan menjadi sekitar 40, dengan ukuran potong maksimum 1, jika semua bobot tepi adalah 1:

Dengan bermain dengan parameter, Anda bisa mendapatkan hasil yang berbeda. Ukuran potongan maksimum 3, misalnya, akan menghasilkan lebih banyak teluk yang diukir dari laut utama, dan laut # 1 akan dibagi menjadi dua bagian utara dan selatan. Ukuran laut minimum 20 akan menghasilkan laut tengah terbelah dua juga.

Cara cepat dan kotor untuk mengidentifikasi badan air yang terpisah tetapi terhubung adalah dengan menyusutkan semua badan air dan melihat apakah ada celah.

Dalam contoh di atas saya pikir bahwa menghapus semua ubin air yang memiliki 2 atau kurang ubin air yang terhubung dengannya (ditandai merah) akan memberi Anda hasil yang diinginkan ditambah beberapa kebisingan tepi. Setelah Anda memberi label tubuh, Anda dapat "mengalirkan" air ke kondisi semula dan mendapatkan kembali ubin yang telah dilepas untuk badan yang sekarang terpisah.

Sekali lagi, ini adalah solusi cepat dan kotor, mungkin tidak cukup baik untuk tahap produksi selanjutnya tetapi cukup untuk "membuat ini berfungsi sekarang" dan beralih ke beberapa fitur lainnya.

Berikut ini adalah algoritma lengkap yang menurut saya harus memberikan hasil yang baik.

1. Lakukan erosi morfologis pada area air - yaitu, buat salinan peta di mana setiap ubin dianggap air hanya jika itu dan semua tetangganya (atau area yang lebih besar, jika Anda memiliki sungai lebih lebar dari satu ubin) adalah air . Ini akan menyebabkan semua sungai hilang sama sekali.

   (Ini akan mempertimbangkan air kepulauan di bagian kiri laut pedalaman Anda menjadi sungai. Jika ini merupakan masalah, Anda dapat menggunakan aturan yang berbeda seperti yang diajukan oleh satu jawaban vrinek ; langkah-langkah berikut akan tetap berlaku selama Anda ada beberapa langkah "hapus sungai" di sini.)

2. Temukan komponen air yang terhubung dari peta yang tererosi dan beri masing-masing label yang unik . (Saya berasumsi Anda sudah tahu bagaimana melakukan ini.) Ini sekarang memberi label segalanya kecuali sungai dan air pantai (tempat erosi berpengaruh)

3. Untuk setiap ubin air di peta asli , temukan label yang ada di ubin air tetangga di peta yang terkikis dan kemudian:

   • Jika ubin itu sendiri memiliki label di peta yang tererosi, maka itu adalah air di tengah laut; berikan label itu di peta asli.
   • Jika Anda hanya menemukan satu label tetangga yang berbeda, maka itu adalah pantai atau mulut sungai; berikan label itu.
   • Jika Anda tidak menemukan label, maka itu adalah sungai; tinggalkan itu.
   • Jika Anda menemukan beberapa label, maka itu adalah hambatan pendek antara dua badan yang lebih besar; Anda mungkin ingin menganggapnya seperti sungai, atau menggabungkan kedua badan di bawah satu label.

   (Perhatikan bahwa untuk langkah ini Anda harus menyimpan kisi-kisi label yang terpisah (atau memiliki dua bidang label dalam satu struktur) untuk peta yang terkikis (yang Anda baca) dan yang asli (yang Anda tuliskan), atau akan ada iterasi- kesalahan tergantung pesanan.)

4. Jika Anda ingin memberi label pada masing-masing sungai secara unik juga, maka setelah langkah-langkah di atas, temukan semua komponen air yang tidak berlabel yang tersisa dan beri label.

Mengikuti gagasan vrinek, bagaimana dengan menumbuhkan tanah (atau mengecilkan air) sehingga bagian-bagian yang semula Anda sambungkan akan terputus setelah tanah tersebut ditumbuhkan?

Ini bisa dilakukan seperti ini:

1. Tentukan berapa banyak yang Anda inginkan untuk menumbuhkan tanah: 1 hex? 2 heks? Nilai inin

2. Kunjungi semua node daratan, dan tetapkan semua tetangganya hingga kedalaman nke node daratan (tulis ke salinan, agar tidak mendapatkan loop tak terhingga)

3. Jalankan algoritme pengurasan banjir asli Anda lagi untuk menentukan apa yang sekarang terhubung dan apa yang tidak

Apakah Anda memiliki gambaran kasar tentang di mana jurang itu? Jika demikian, Anda dapat memodifikasi isi banjir Anda untuk melacak jumlah sel tetangga tetapi belum dijelajahi (bersama dengan daftar sel yang dikunjungi). Ini dimulai dengan 6 di hex map dan kapan pun nilai itu turun di bawah titik tertentu, maka Anda tahu Anda menekan "pembukaan".