Temukan Algoritma Poligon Gandakan

8

Saya memiliki sekelompok poligon. Tujuan saya adalah menemukan duplikat poligon dari kelompok poligon ini.

Menggunakan NetTopologySuite (A c # port JTS), dimungkinkan untuk membandingkan dua geometri dan memeriksa apakah keduanya sama. Metode brute-force (memeriksa setiap poligon terhadap setiap poligon lainnya) adalah satu-satunya ide yang muncul di benak saya tetapi tidak dapat digunakan jika ada sejumlah besar poligon. Apakah ada algoritma yang lebih baik dari kekuatan kasar dalam kasus ini?

Saya menemukan skrip ini yang tampaknya berisi ide-ide untuk apa yang saya cari (komentar menunjukkan pendekatan membagi dan menaklukkan..tapi tidak banyak detail dalam komentar). Tapi saya harus mengakui bahwa saya tidak bisa mendapatkan apa-apa dari itu :) .. Itu dilakukan untuk ArcView, yang saya tidak kenal.

Catatan: Saya tidak mencari solusi PostGIS / database seperti dalam pertanyaan ini . Saya mencari sesuatu yang dapat diintegrasikan ke AutoCAD, Quantum GIS atau produk GIS desktop semacam itu melalui penyesuaian (c #, c ++, python dll.)

Vinayan
sumber
1
Saya membayangkan modifikasi menggunakan sesuatu seperti toblerity.github.com/rtree akan sangat membantu. Bangun indeks spasial dan periksa duplikat saat membangun indeks
Peter Smith
@PeterSmith - Saya pikir ini ide yang bagus! ..mengapa kamu tidak menambahkan ini sebagai jawaban .. Saya pikir NetTopologySuite memiliki Rtree built-in .. harus menggali ..
vinayan

Jawaban:

4

Jika poligon benar-benar identik, dan jika Anda memiliki cara mudah untuk menghitung luasnya, hitung saja luas setiap poligon, kemudian urutkan berdasarkan luas, dan hanya periksa poligon dengan area yang cocok. Varian dari ide ini adalah untuk menyortir poligon pada koordinat titik paling utara mereka (memutuskan hubungan dengan memilih sebagian besar titik terikat di timur). Hanya periksa poligon yang titik paling utaranya cocok. Jika poligon cukup bervariasi, cukup urutkan berdasarkan jumlah poin.

Saya bisa terus berjalan, tetapi Anda mendapatkan idenya.

Llaves
sumber
Llaves, ide ini terlihat sangat sederhana dan mudah, bahkan tanpa memiliki perangkat lunak GIS atau api lainnya.
vadivelan
1

Jika objek geometri yang Anda periksa identik, bagaimana dengan membuat kamus geometri dengan kunci menjadi geometri dan nilainya menjadi pengidentifikasi objek.

Anda melewati daftar sekali, menambahkan nilai ke kamus untuk setiap objek. Periksa apakah kunci ada sebelum menambahkan, dan Anda akan diberi tahu jika Anda memiliki geometri duplikat. Pada titik itu, selami loop untuk memperbaiki masalah. Ini akan memberi Anda satu kali melewati objek.

mcole
sumber
Ini terlihat sangat menarik..tapi saya tidak yakin itu akan berhasil .. Saya akan mencobanya dan kembali ..
vinayan
0

Setelah banyak membaca, saya sampai pada kesimpulan bahwa indeks spasial adalah apa yang diperlukan. Komentar oleh @Peter Smith membuat saya melihat ke dalam Rtree .

Definisi wiki untuk RTree,

R-tree adalah struktur data pohon yang digunakan untuk metode akses spasial, yaitu, untuk mengindeks informasi multi-dimensi seperti koordinat geografis, persegi panjang atau poligon

Jadi saya membuat indeks di NetTopologySuite dan menanyakan Indeks menggunakan amplop masing-masing fitur. Perbandingan itu terbatas pada fitur yang sangat sedikit.

Bagaimana itu dilakukan dengan menggunakan NTS dijelaskan dalam jawaban ini .

Vinayan
sumber