Mengingat beberapa poligon yang tumpang tindih dengan berbagai cara, saya ingin mengekspor dari fitur ini semua poligon yang tidak tumpang tindih dengan yang lain, secara iteratif.
Produk akan menjadi sejumlah fitur tanpa tumpang tindih yang, ketika dirangkum bersama, menjadi yang asli.
Produk kemudian dapat digunakan sebagai input ke Statistik Zonal, dan ini akan jauh lebih cepat daripada iterasi Statistik Zonal atas setiap poligon.
Saya telah mencoba kode ini di ArcPy tanpa hasil.
Apakah kode untuk melakukan ini sudah ada?
arcpy
algorithm
overlapping-features
ndimhypervol
sumber
sumber
Jawaban:
Ini adalah masalah pewarnaan grafik .
Ingatlah bahwa pewarnaan grafik adalah penugasan warna ke simpul grafik sedemikian rupa sehingga tidak ada dua simpul yang berbagi tepi juga akan memiliki warna yang sama. Secara khusus, simpul (abstrak) grafik adalah poligon. Dua simpul terhubung dengan tepi (tidak terarah) setiap kali mereka berpotongan (sebagai poligon). Jika kita mengambil solusi untuk masalah ini - yang merupakan urutan dari (katakanlah k ) koleksi poligon yang terpisah - dan berikan warna yang unik untuk setiap koleksi dalam urutan, maka kita akan mendapatkan k -warna grafik. . Sangat diinginkan untuk menemukan k kecil .
Masalah ini cukup sulit dan tetap tidak terpecahkan untuk grafik yang berubah-ubah. Pertimbangkan solusi perkiraan yang mudah dikodekan. Algoritma berurutan harus dilakukan. Algoritme Welsh-Powell adalah solusi serakah berdasarkan pada urutan menurun dari titik demi titik. Diterjemahkan ke bahasa poligon asli, pertama-tama urutkan poligon dalam urutan jumlah poligon lain yang tumpang tindih. Agar berhasil, beri poligon pertama warna awal. Pada setiap langkah berturut-turut, cobalah untuk mewarnai poligon berikutnya dengan warna yang ada: yaitu, pilih warna yang tidaksudah digunakan oleh semua tetangga poligon itu. (Ada banyak cara untuk memilih di antara warna yang tersedia; coba salah satu yang paling sedikit digunakan atau pilih salah satu secara acak.) Jika poligon berikutnya tidak dapat diwarnai dengan warna yang ada, buat warna baru dan warnai dengan itu.
Setelah Anda mencapai pewarnaan dengan sejumlah kecil warna, lakukan zonalstats warna dengan warna: dengan konstruksi, Anda dijamin tidak akan memiliki dua poligon warna yang tumpang tindih.
Berikut kode contoh di
R
. (Kode Python tidak akan jauh berbeda.) Pertama, kami menggambarkan tumpang tindih di antara tujuh poligon yang ditampilkan.Yaitu, poligon 1 dan 2 tumpang tindih, dan begitu juga poligon 2 dan 3, 3 dan 4, ..., 1 dan 7.
Urutkan simpul berdasarkan derajat menurun:
Algoritma pewarnaan berurutan (kasar) menggunakan warna paling awal yang tersedia yang belum digunakan oleh poligon yang tumpang tindih:
Inisialisasi struktur data (
colors
dancolor.next
) dan terapkan algoritma:Bagi poligon menjadi kelompok-kelompok sesuai dengan warna:
Output dalam contoh ini menggunakan empat warna:
Ini telah mempartisi poligon menjadi empat kelompok yang tidak tumpang tindih. Dalam hal ini solusinya tidak optimal ({{3,6,5}, {2,4}, {1,7}} adalah tiga warna untuk grafik ini). Secara umum solusi yang didapat seharusnya tidak terlalu buruk.
sumber
Metodologi yang direkomendasikan oleh #whuber mengilhami saya untuk mengambil arah baru, dan di sini adalah solusi sederhana saya, dalam dua fungsi. Yang pertama, disebut countOverlaps, membuat dua bidang, "tumpang tindih" dan "ovlpCount" untuk merekam setiap polis yang tumpang tindih dengannya, dan berapa banyak tumpang tindih yang terjadi. Fungsi kedua, explodeOverlaps, menciptakan bidang ketiga, "expl", yang memberikan bilangan bulat unik untuk setiap kelompok polis yang tidak tumpang tindih. Pengguna kemudian dapat mengekspor fc baru berdasarkan bidang ini. Proses ini dipecah menjadi dua fungsi karena saya pikir alat countOverlaps dapat terbukti berguna dengan sendirinya. Maafkan kecerobohan kode (dan konvensi penamaan yang ceroboh), karena ini cukup awal, tetapi berhasil. Juga pastikan bahwa "idName" bidang mewakili bidang dengan ID unik (hanya diuji dengan ID integer). Terima kasih Whuber untuk menyediakan saya dengan kerangka kerja yang diperlukan untuk mendekati masalah ini!
sumber
countOverlaps
berkorespondensi dengan dua barisnbrhoods <- sapply(vertices, neighbors); degrees <- sapply(nbrhoods, length)
dalam kode saya:degrees
adalah jumlah tumpang tindih. Tentu saja kode Anda lebih panjang karena mencerminkan sebagian besar analisis GIS yang diterima begitu saja dalam solusi saya: yaitu, bahwa Anda pertama kali mengidentifikasi poligon yang tumpang tindih, dan pada akhirnya Anda menggunakan solusi untuk menghasilkan kumpulan data poligon. Ini akan menjadi ide yang baik untuk merangkum perhitungan grafik-teori, jadi jika Anda pernah menemukan algoritma pewarnaan yang lebih baik, akan lebih mudah untuk dihubungkan.Sudah lama, tapi saya menggunakan kode ini untuk aplikasi saya sendiri dan sudah bekerja dengan baik - terima kasih. Saya menulis ulang sebagian untuk memperbaruinya, menerapkannya pada baris (dengan toleransi) dan mempercepatnya secara signifikan (di bawah - saya menjalankannya pada 50 juta buffer yang bersinggungan dan hanya membutuhkan beberapa jam).
sumber
Dalam hal ini saya biasanya menggunakan metode berikut:
Saya percaya hasilnya akan menjadi yang Anda inginkan, dan Anda bahkan dapat menghitung jumlah yang tumpang tindih. Tidak tahu apakah dalam hal kinerja akan lebih baik untuk Anda atau tidak.
sumber