Algoritma untuk menghitung cakupan + tumpang tindih dari satu set busur

10

Saya memiliki busur berisi shapefile yang mewakili jalur yang dilalui oleh truk yang menyebarkan pupuk ke pertanian.

Katakanlah saya tahu lebar selebar 30m, yaitu truk bisa menaburkan pupuk 15m di kedua sisi kendaraan.

Saya ingin membuat satu set poligon, yang menunjukkan:
1) Total area yang menerima pupuk
2) Area tumpang tindih, yaitu di mana dua lintasan terpisah terlalu berdekatan, sehingga beberapa bagian kebun menerima dua kali dosis "yang benar" "pupuk.

Pendekatan naif adalah dengan hanya membuat poligon cakupan sebagai buffer di sekitar busur. Ini berfungsi dalam kasus khusus di mana garis spread berbeda satu sama lain. Namun, truk itu dapat berjalan mengelilingi pertanian dalam spiral yang terus berkurang, dan penyangga sederhana akan gagal menunjukkan tumpang tindih di mana dua lintasan spiral terlalu berdekatan (jika spiral adalah busur tunggal, saya akan berakhir dengan poligon tunggal tanpa bagian yang tumpang tindih).

Jika itu relevan, saya menggunakan TatukGIS VCL DK, tapi saya benar-benar mencari algoritma daripada solusi spesifik.

Beberapa klarifikasi dalam menanggapi diskusi sejauh ini:

1) Saya tidak bisa mengandalkan data vektor yang memiliki metadata tertentu (mis. GPS log atau spread rate). Saya mengizinkan pengguna untuk memilih layer dan menentukan lebar spread, lalu laporan berjalan.

2) Tujuan dari laporan ini adalah untuk menunjukkan kepada pengguna seberapa "terampil" operator kendaraan itu, di mana "terampil" berarti "mencapai cakupan tertinggi dengan tumpang tindih terendah".

3) Saya lebih nyaman di tanah vektor daripada tanah raster, jadi saya lebih suka solusi berbasis vektor.

Terima kasih,

Darren.

dbruning
sumber
1
Saya ingin tahu apakah ini akan mirip dengan metode yang memprediksi curah hujan kumulatif berdasarkan perkiraan jalur badai.
Kirk Kuykendall

Jawaban:

3

Mungkin solusi paling sederhana adalah memecah geometri tunggal menjadi segmen-segmen, dan menyangga segmen-segmen individual tersebut: dalam kasus spiral Anda, Anda akan buffer setiap busur, lalu memotong busur individu untuk menghasilkan hitungan. Berhati-hatilah untuk menghindari tumpang tindih palsu dengan tidak melindungi ujung segmen, hanya ke kiri dan kanan segmen itu sendiri.

Pendekatan lain adalah dengan overlay grid poligon pada data, dan kemudian di dalam setiap sel grid, buffer setiap segmen garis yang berpotongan secara terpisah. Agar akurat dalam hal ini, Anda ingin mengambil sel grid di bawah analisis, buffer itu, lalu kumpulkan segmen yang berpotongan, dan buffer itu, melakukan analisis Anda dalam jendela sel asli.

Salah satu dari opsi ini harus memberi Anda perkiraan yang tumpang tindih, saya bisa memikirkan beberapa pendekatan yang lebih akurat tetapi mereka perlu mengetahui sesuatu tentang data.

scw
sumber
Terima kasih. Saya sedang berpikir di sepanjang garis saran pertama Anda - memecah geometri menjadi segmen & buffering mereka. Saya pikir saya akan perlu juga menyangga ujung segmen, sehingga saya mendapatkan ujung membulat di sudut-sudut. Memikirkan kasus di mana saya mulai dengan garis sudut kanan - jika saya tidak menahan ujungnya, saya akan berakhir dengan dua persegi panjang yang tumpang tindih dengan sebuah persegi yang hilang di bagian luar sudut (sulit untuk diungkapkan sebagai teks!)
dbruning
Saya pikir saya akan perlu juga menyangga ujung segmen, sehingga saya mendapatkan ujung membulat di sudut-sudut. Saya berpikir lebih jauh untuk memotong buffer untuk setiap segmen dengan buffer untuk segmen sebelumnya, dan kemudian mengakumulasikan hanya bagian "baru" dari setiap buffer ke buffer utama. Idenya adalah untuk mengabaikan tumpang tindih dengan segmen sebelumnya tetapi pengambilan tumpang tindih dengan segmen yang lebih tua.
dbruning
2

Tidak ada solusi, tetapi beberapa input:

Masalah ini tampaknya mirip dengan masalah pendeteksian koalesensi garis dalam generalisasi peta . Itu terjadi ketika gaya besar diterapkan pada garis berliku-liku (simbol self-overlaps):

masukkan deskripsi gambar di sini

Dokumen ini hal. 176 hingga 180 (dalam bahasa Perancis ... maaf) memberikan algoritma untuk mendeteksi bagian yang berpotongan sendiri. Prinsipnya adalah, seperti yang diusulkan oleh scw , untuk menggunakan buffer sisi tunggal dari setiap segmen yang terdiri dari segmen ditambah 0, 1 atau 2 lingkaran lingkaran. JTS berisi implementasi buffer sisi tunggal ini yang mungkin berguna.

Julien
sumber
Mengapa Anda khawatir tentang mendeteksi persimpangan diri? Dan mengapa Anda mengusulkan buffer "satu sisi"? Tampaknya tidak ada hubungannya dengan masalah.
whuber
Tujuannya adalah untuk mendeteksi di mana truk menaburkan pupuk beberapa kali, yaitu di mana area penyebaran berpotongan sendiri.
julien
2

Solusi vektor akan melewatkan variabel yang berpotensi kritis : waktu, dan melaluinya, tingkat penyebaran. Ketika traktor bergerak lebih cepat, lebih sedikit pupuk yang tersebar per unit area dan ketika ia bergerak lebih lambat (melambat menjadi berbelok dan berakselerasi keluar satu) akan menyebarkan lebih banyak pupuk per unit area. Selain itu, jika traktor menyebarkan material saat berputar, material akan lebih terkonsentrasi ke bagian dalam belokan dan kurang terkonsentrasi ke arah luar.

Data waktu akan tersedia dalam catatan GPS tentang kemajuan traktor. Lereng (jarak yang ditempuh dibagi dengan waktu yang berlalu) akan memperkirakan kecepatan di setiap titik. Atau, seseorang mungkin (sebagai perkiraan) mengasumsikan kecepatan konstan dalam interior suatu bidang dan kecepatan lebih lambat dalam buffer internal yang wajar dari batas bidang.

Representasi raster dapat menangani masalah ini. Rasterkan jalur traktor. Ini mengatur semua sel yang tidak dilintasi oleh traktor ke nilai NoData (atau ke nol). Jika traktor bergerak pada kecepatan standar dan konstan, cukuplah untuk memberikan nilai konstan pada setiap sel data. Sekarang, misalnya, jika traktor bergerak dua kali kecepatan ini, (mungkin) laju aplikasinya akan dikurangi setengahnya, dan ini dapat direpresentasikan dengan mengurangi separuh nilai dalam sel.

Secara umum, nilai untuk dimasukkan ke dalam sel apa pun adalah tingkat aplikasi per satuan luas . Jika traktor secara merata menyebarkan x Kg pupuk per detik hingga 15 m di setiap sisi saat bepergian dengan kecepatan y m / detik, maka itu menyebar x / y Kg / detik / [m / detik] / (2 * 15 m) = x / (30 y ) Kg / m ^ 2 pupuk. Jadi, x / (30 y ) adalah nilai yang dimasukkan ke dalam setiap sel. x diberikan dan y dihitung dari data GPS.

Persimpangan diri pada prinsipnya tidak ada masalah . Jika jalur traktor menyilang dengan sendirinya, tambahkan kontribusi setiap kali ia mengambil kembali sel. Mungkin diperlukan beberapa pemrosesan khusus untuk mencapai hal ini, tergantung pada bagaimana grid dibuat dan pada kemampuan perangkat lunak GIS.

Setelah melakukan persiapan itu, sisanya cepat dan mudah: jumlah fokus dari grid ini, menggunakan lingkungan melingkar dengan radius 15 m, menemukan penyebaran jumlah kumulatif per unit area di setiap sel.

whuber
sumber
1
+1 sepertinya jika Anda memiliki alat yang memungkinkan kernel (mewakili traktor) untuk bergerak di sepanjang jalur (alih-alih di setiap baris) masalah ini akan lebih mudah dikelola.
Kirk Kuykendall
@Kirk Tidak perlu mengikuti path atau baris atau apa pun dengan kernel. Sangat penting untuk menghargai perubahan sudut pandang yang menyertai jumlah fokus: alih-alih melihat masalah sebagai salah satu dari penyebaran materi dari jalur poin, lihat itu sebagai salah satu perhitungan berapa banyak bahan yang menumpuk di setiap titik di lapangan. . Jelas itu masalah yang sama dengan solusi yang sama. Pendekatan kernel bergerak (dan pendekatan buffering yang diusulkan) mengambil sudut pandang pertama; jumlah fokus, yang kedua. Tetapi alat focal sum tersedia; perhitungan kernel yang bergerak tidak.
whuber
Saya pikir pendekatan raster yang Anda buat akan menjadi metode terbaik jika kami tahu kecepatan dan tingkat penyebaran. Sayangnya dalam skenario khusus ini kita tidak tahu. Pengguna akhir kami dapat memilih lapisan apa pun sebagai masukan untuk laporan cakupan ini, dan kami tidak dapat mengandalkan geometri yang memiliki metadata tertentu.
dbruning
@ debun Pendekatan ini tampaknya tidak membutuhkan kecepatan / spread rate yang diketahui; itu hanya memungkinkan untuk mereka (+ model realitas yang lebih akurat) jika Anda memilikinya. Namun, itu juga akan lebih membutuhkan beberapa ambang + penghitungan sel untuk mendapatkan metrik yang Anda inginkan (cakupan area total; area-of-overlap) dari sistem, dan ada trade-off akurasi yang tercampur di sana juga.
Dan S.
@ debun Jika Anda tidak tahu nilai spread, Anda akan mendapatkan nilai spread relatif. Jika Anda tidak tahu kecepatan, Anda masih tahu (atau harus tahu) bagaimana orang mengendarai traktor dan harus bisa mendapatkan perkiraan yang wajar dari kecepatan relatif. Jika Anda mengasumsikan kecepatan konstan dan laju spread konstan Anda masih akan mendapatkan jawaban yang masuk akal; mereka akan setuju dengan jawaban berbasis penyangga atas bagian lurus dari rute traktor; dan mereka cenderung lebih realistis di bagian melengkung.
Whuber
2

Saya tidak 100% yakin pada protokol StackExchange jadi saya memposting ini sebagai jawaban untuk pertanyaan saya. Itu adalah jawaban yang akhirnya saya gunakan.

Algoritma dasarnya adalah:
1. Memecah geometri pada lapisan menjadi segmen tidak lebih dari 1/2 lebar spread.
2. Untuk setiap segmen:
- Buat "rolling buffer" dengan melihat ke belakang di sepanjang bentuk, dan buffering semua segmen sebelumnya di mana panjang kumulatif segmen tersebut kurang dari lebar sebaran (jari-jari buffer = 1/2 lebar sebaran)
- Buat "buffer segmen berikutnya" dari segmen berikutnya (radius buffer = 1/2 lebar spread)
- Kurangi "rolling buffer" dari "buffer segmen berikutnya" untuk mendapatkan "buffer baru"
- gabungkan semua "buffer baru" poligon bersama untuk mendapatkan satu poligon per bentuk.

Pada dasarnya ini memungkinkan pengemudi kendaraan penyebar melakukan tikungan sudut kanan (atau lebih lebar) tanpa penalti yang tumpang tindih, tetapi jika mereka berputar terlalu tajam sehingga menyebar di "tanah lama", kita mulai mendapatkan tumpang tindih.

Tumpang tindih dengan warna biru

Spiral sepertinya saya ingin:

spiral

dbruning
sumber