Poin dalam algoritma poligon untuk beberapa poligon

Saya punya peta Google dengan banyak poligon di atasnya.

Inilah masalah yang saya minati: Diberikan titik lat, lng, apa cara terbaik untuk menentukan semua poligon yang ada di titik ini?

Cara yang jelas adalah menjalankan algoritma "point in polygon" secara iteratif untuk setiap poligon, tapi saya bertanya-tanya apakah ada algoritma yang efisien untuk menjawab pertanyaan seperti itu terutama jika Anda memiliki ribuan poligon.

Seperti dengan hampir semua pertanyaan seperti itu, pendekatan optimal tergantung pada "kasus penggunaan" dan bagaimana fitur diwakili. Kasus penggunaan biasanya dibedakan oleh (a) apakah ada banyak atau beberapa objek di setiap lapisan dan (b) apakah salah satu (atau keduanya) lapisan memungkinkan untuk mengkomputasi beberapa struktur data; yaitu, apakah salah satu atau keduanya cukup statis dan tidak berubah untuk membuat investasi dalam perhitungan bermanfaat.

Dalam kasus ini, ini menghasilkan skenario berikut. Biasanya poinnya dinamis: artinya, mereka tidak diberikan sebelumnya. (Jika tersedia di muka, atau dalam kelompok yang sangat besar, beberapa optimasi berdasarkan pengurutannya akan tersedia.) Misalkan Q adalah jumlah titik kueri dan P menjadi jumlah simpul poligon .

Data poligon vektor

(1) Beberapa poin, beberapa simpul poligon di toto . Gunakan prosedur brute-force, seperti algoritma penikaman garis klasik . Untuk setiap metode yang layak, biayanya adalah O (P * Q), karena biayanya O (1) waktu untuk membandingkan titik ke tepi poligon dan semua perbandingan harus dibuat.

(2) Mungkin banyak simpul poligon, tetapi mereka dinamis: setiap kali sebuah titik digunakan dalam kueri, semua poligon mungkin telah berubah. Sekali lagi gunakan algoritma brute-force. Biayanya masih O (P * Q), yang akan besar karena P akan besar, tetapi tidak ada yang membantu itu. Jika perubahannya kecil atau terkendali ( misalnya , poligon sedikit berubah bentuk atau hanya bergerak lambat), Anda mungkin dapat menggunakan versi solusi berikutnya dan menemukan cara yang efisien untuk memperbarui struktur data ketika poligon berubah. Itu mungkin akan menjadi masalah bagi penelitian asli.

(3) Banyak simpul poligon dan poligon statis (yaitu, lapisan poligon jarang berubah). Precompute struktur data untuk mendukung pencarian (yang dapat didasarkan pada penyapuan garis atau algoritma quadtree ). Biaya perhitungan untuk algoritma ini adalah O (P * log (P)), tetapi biaya permintaan menjadi O (Q * log (P)), sehingga total biaya adalah O ((P + Q) * log ( P)).

Beberapa perbaikan tersedia dalam kasus khusus , seperti

(A) Semua poligon cembung ( preprocessing poligon dapat dilakukan lebih cepat ),

(B) Semua interior poligon terpisah , dalam hal ini Anda dapat menganggap penyatuan mereka sebagai poligon tunggal (yang memungkinkan untuk algoritma efisien langsung, seperti yang didasarkan pada triangulasi, dan

(c) Kebanyakan poligon tidak terlalu berliku - artinya, mereka menempati sebagian besar kotak pembatas mereka - dalam hal ini Anda dapat melakukan tes awal hanya berdasarkan kotak pembatas dan kemudian memperbaiki solusi itu. Ini adalah pengoptimalan yang populer.

(D) Jumlah poin besar. Mengurutkannya mungkin meningkatkan pengaturan waktu. Misalnya, ketika menerapkan algoritma sapuan point-in-polygon garis kiri-ke-kanan, Anda akan mengurutkan poin pada koordinat pertama mereka, memungkinkan Anda untuk menyapu titik-titik pada saat yang sama Anda menyapu tepi poligon. Saya tidak mengetahui bahwa optimasi seperti itu telah dipublikasikan. Namun, salah satu yang telah diterbitkan adalah melakukan triangulasi terkendala dari penyatuan semua titik dan simpul poligon: begitu triangulasi selesai, mengidentifikasi titik-titik interior harus cepat. Biaya komputasi akan diukur sebagai O (Q * log (Q) + (P + Q) * log (P + Q)).

Data poligon raster

Ini sangat mudah: melihat layer poligon sebagai raster indikator biner (1 = di dalam poligon, 0 = di luar). (Ini bisa memerlukan tabel pencarian untuk mengonversi nilai raster ke indikator di dalam / luar.) Setiap probe titik sekarang membutuhkan upaya O (1) untuk mengindeks sel raster dan membaca nilainya. Upaya total adalah O (Q).

Secara umum

Solusi hybrid yang bagusdalam kasus banyak poligon vektor statis (kasus vektor 3 di atas) awalnya untuk meraster poligon, mungkin bahkan dengan resolusi kasar, kali ini membedakan sel mana pun yang memotong bagian mana pun dari batas poligon (beri nilai 2, katakanlah) . Menggunakan probe raster (biaya: O (1)) biasanya menghasilkan jawaban yang pasti (titik diketahui berada di dalam atau di luar), tetapi kadang-kadang menghasilkan jawaban yang tidak terbatas (titik jatuh dalam sel di mana setidaknya satu tepi lolos), dalam hal ini kueri vektor O (log (P)) yang lebih mahal dibuat. Metode ini menimbulkan beberapa biaya penyimpanan tambahan untuk raster, tetapi dalam banyak kasus bahkan raster kecil (satu MB akan memungkinkan untuk raster 2000 oleh 2000 yang menyimpan nilai-nilai {0,1,2, null}) dapat memberikan keuntungan besar dalam waktu komputasi . Tanpa gejala,

Jika Anda memiliki kotak pembatas poligon disimpan di sesuatu seperti pohon quad maka Anda dapat menggunakannya untuk dengan cepat menentukan poligon mana yang akan diperiksa. Paling tidak Anda hanya bisa melihat apakah titik berada di dalam setiap kotak pembatas poligon sebagai lawan melakukan titik penuh dalam poligon untuk setiap poligon. Secara pribadi saya akan menyiapkan layanan web yang akan men-cache poligon dalam memori dan menggunakan sesuatu seperti JTS atau NetTopology suite untuk melakukan kueri persimpangan untuk saya.

Dalam postgis, ST_Intersects menggunakan indeks untuk pertama-tama menemukan apakah titik berada di dalam kotak pembatas poligon dan kemudian melakukan pengecekan ulang untuk melihat apakah benar-benar ada di dalam poligon. Itu cepat, seringkali sangat cepat.

Jika Anda telah menyimpan data Anda di PostGIS seharusnya tidak ada keraguan bahwa database adalah tempat yang tepat untuk melakukan perhitungan. Dalam kasus lain, Anda harus mengirim poligon ke program menengah atau klien. Itu, dengan sendirinya akan memakan waktu lebih banyak daripada melakukan perhitungan dan hanya mendapatkan poligon yang relevan.

/ Nicklas