Menemukan poligon yang dilintasi garis menggunakan OGR?

8

Saya mencoba menemukan semua poligon yang dilintasi oleh satu baris (trek GPS). Saya menggunakan perpustakaan OGR (dari python) untuk menghitung ini, tetapi saat ini agak 'kasar' (dan lambat). Untuk setiap titik lintasan saya, saya memanggil metode intersect dengan semua poligon. Optimalisasi yang jelas adalah dengan memeriksa hanya dengan poligon yang berdekatan. Tapi saya rasa ini adalah masalah klasik, dengan solusi yang sudah diketahui (yang saya tidak dapat menemukan ...).

Saya ingin menghindari menggunakan database khusus karena saya mencoba menulis perangkat lunak mandiri (spasial adalah pilihan jika DB adalah cara untuk pergi).

(FYI, kode sumber saat ini tersedia di sini: https://github.com/dkm/airspace-checker )

python ogr intersection optimization Marc
sumber

Jawaban:

7

Untuk solusi Python, Anda mungkin ingin melihat Shapely http://gispython.org/shapely/docs/1.2/ dan RTree http://pypi.python.org/pypi/Rtree/

Rtree akan membantu Anda membuat indeks spasial.

DavidF
sumber
Saya sudah melihat rupawan, tetapi tidak tahu tentang rtree! Terima kasih!
Marc
Ok, saya sudah bisa (akhirnya) menguji rtree. Ini berfungsi dengan baik karena saya dapat mengurangi set tes dari 1096 ke 19 :). Saya sedang berpikir untuk menggunakan rupawan, tetapi saya harus memahami apa yang tersirat (rupawan tidak menangani proyeksi, saya tidak ingin kehilangan apa pun dalam proses).
Marc
5

Alih-alih berpotongan ekspansif , Anda dapat melakukan pra-pemilihan poligon berdasarkan perbandingan kotak pembatas. Dengan kata lain, cari semua poligon yang tumpang tindih / berdekatan dengan MBR segmen trek Anda. Kemudian lakukan pengujian terperinci pada subset poligon.

mloskot
sumber
3

Proposal mloskot dan Nicklas untuk membandingkan kotak pembatas memang benar.

Jika Anda menggunakan shapefile Anda juga dapat mempertimbangkan untuk memanggil modul saga ini: http://www.saga-gis.org/saga_modules_doc/shapes_transect/index.html

johanvdw
sumber
Saya pikir saya akan memeriksa solusi dengan BBoxes. Data saya tidak acak: trek adalah penerbangan paraglider / hangglider dan poligon adalah wilayah udara. Saya akan melihat apakah saya bisa membuat filter sederhana di bbox. Saya tidak secara langsung menggunakan shapefile tetapi saya telah menulis sebuah skrip yang membaca format OpenAIR (deskriptor ruang udara "standar") ke OGR (dari mana saya dapat langsung mengekspor ke shp)
Marc
2

Apa yang dilakukan database seperti PostGIS untuk mempercepat ini adalah pertama-tama melakukan indeks, membandingkan kotak. Pertama-tama ia menemukan semua poligon yang memiliki kotak pengikat saling berhubungan dengan kotak pengikat garis. Masalah dalam kasus Anda mungkin adalah linestring yang panjang dan akan memiliki kotak pembatas yang sangat besar memotong banyak poligon yang tidak menarik.

Jika garis sangat panjang Anda mungkin harus bekerja dengan fungsi geodetik yang jauh lebih kompleks dan lambat daripada fungsi planar.

Mungkin cukup rumit untuk membuat segalanya berjalan mulus.

Mengapa Anda tidak ingin mengandalkan database? Itu tidak akan menyelesaikan semua masalah Anda, tetapi ada banyak optimisasi bawaan di PostGIS misalnya. Di sana Anda juga memiliki perhitungan geodetik persimpangan jika Anda membutuhkannya.

Pembaruan: Saya membaca pertanyaan Anda lagi dan menyadari bahwa Anda tidak menggunakan linestring bentuk trac tetapi setiap titik.

Saya pikir Anda berada di trac yang salah;)
Keduanya karena Anda tidak memeriksa untuk memeriksa apakah ujung antara titik sudut memotong poligon dan karena Anda memindahkan iterasi antara titik titik ke python daripada beberapa implementasi C yang menurut saya jauh lebih cepat . Maka Anda memiliki masalah dengan indeks. Untuk membuat segalanya lebih cepat, Anda harus membangun dan menangani semacam indeks spasial.

Di sisi lain, jika Anda melakukan banyak pekerjaan dalam kode Anda sendiri, mengapa Anda tidak melakukan tes persimpangan juga. Tes itu hanya titik dalam tes poligon jika Anda berurusan dengan titik titik. Google untuk "titik dalam poligon" dan Anda akan menemukan beberapa algoritma.

Tapi, saya akan menggunakan pendekatan berbasis data. Itu akan memberi Anda kemungkinan untuk menggunakan indeks spasial.

/ Nicklas

Nicklas Avén
sumber
Saya memikirkan hal yang sama di linestring. Saya tidak begitu akrab dengan GIS & python, tetapi harus ada cara untuk membangun indeks spasial dalam memori (saya tahu berbagai ada berbagai opsi .net untuk melakukan ini). Ini mungkin pertanyaan bagus untuk gis.se.
Jay Cummins
Terima kasih atas jawabannya. Saya tidak menggunakan DB untuk kesederhanaan pengaturan. Tetapi jika menghindari DB menyiratkan terlalu banyak kompleksitas kode, maka saya akan berubah pikiran :). Adapun "indeks spasial", saya harus sedikit google untuk memahami apa itu.
Marc
Adapun "Saya membaca pertanyaan Anda lagi dan menyadari bahwa Anda tidak menggunakan linestring bentuk trac tetapi setiap titik." Saya kira saya juga bisa menguji persimpangan dari objek linestring, tapi kemudian saya perlu mengekstrak bagian berpotongan. Tapi itu mungkin lebih cepat, Anda memang benar!
Marc
Tentang indeks spasial Anda harus indeks google intis dan multidimensi. Idenya adalah untuk membangun indeks multidimensi dari kotak pembatas. Dalam db-evironment, perencana kemudian memutuskan apakah perlu upaya untuk mencari indeks terlebih dahulu untuk menemukan kotak pembatas yang bersilangan sebelum melakukan tes simpang sungguhan.
Nicklas Avén