Metode pengindeksan alternatif untuk operasi set point

17

Adalah umum untuk menggunakan indeks spasial kotak pembatas untuk meningkatkan kinerja ketika bekerja dengan sejumlah besar fitur. Di mana operasi dilakukan terhadap masing-masing geometri dengan sejumlah besar simpul, apakah ada strategi optimasi yang serupa?

Misalnya, apakah ada struktur data yang dapat mempercepat titik dalam poligon, atau operasi gabungan?

algorithm optimization indexing Matthew Snape
sumber
1
Di bawah tenda, GIS menggunakan banyak struktur data khusus, termasuk berbagai bentuk quadtrees, DCEL, dll., Yang dijelaskan dalam buku teks geometri komputasi. Apakah Anda bertanya tentang detail implementasi ini atau Anda bertanya tentang metode yang dapat digunakan oleh pengguna dalam bahasa scripting?
whuber
Terima kasih, saya pikir saya perlu membaca buku pelajaran. Poin dari pertanyaan saya adalah bagaimana struktur data tersebut dapat dihitung sebelumnya. Adakah implementasi pra-komputasi ada?
Matthew Snape
Matthew, itu pertanyaan yang bagus. GIS yang benar-benar berorientasi pada kinerja akan menawarkan opsi kepada pengguna untuk melakukan precompute struktur data untuk aplikasi berulang. Seperti berdiri, periklanan perangkat lunak itu sendiri sebagai "GIS" biasanya menawarkan perhitungan seperti itu hanya dalam bentuk "indeks spasial" sedangkan perangkat lunak tujuan lebih umum yang juga dapat melakukan analisis GIS, seperti Mathematica (atau sampai batas tertentu R) akan menawarkan pengguna jauh lebih banyak kontrol atas hal-hal seperti itu.
whuber
Saya pikir masalahnya didasarkan pada "sifat fraktal" dari objek 2d dan kepadatan informasi distribusi yang tidak pasti dan tidak seimbang.
huckfinn

Jawaban:

2

OK untuk Point in Polygon saja:

Saya pikir masalahnya didasarkan pada "sifat fraktal" dari objek 2d dan distribusi informasi spasial yang tidak pasti dan tidak seimbang. Jika Anda memiliki kisi-kisi biasa, mudah untuk menghitung posisi atau hubungan sel. Tetapi isoline model terrain mungkin memiliki bagian yang tidak rumit di sisi dan bagian yang rumit secara matematis di sisi lain (bagian yang secara morfologis aktif seperti bubungan, lembah ...).

Pengindeksan mencoba menangani dua hal:

  1. Rutin cepat yang memberi Anda satu set ember tempat Anda mengumpulkan objek yang dapat secara spasial membingungkan (ember!). Dan BBox mudah dihitung dan ditangani.

  2. Seperangkat relasi (tumpang tindih, sentuh) untuk membedakan atau menghubungkan hal-hal spasial (objek).

Sayangnya BBox tidak akan memberi Anda petunjuk, berapa banyak poin dalam setiap BBox, bagaimana objek dibentuk (lubang, cembung, ...) dan bagaimana info tersebut didistribusikan secara lokal (90% titik di sudut kiri atas jendela). BBox). Jadi, Anda dapat menemukan anggota operasi cepat pada tingkat objek dan kehilangan banyak waktu dalam membangun hubungan tes.

Untuk menggunakan pendekatan yang lebih tidak teratur, triangulasi IMO dalam kombinasi dengan dan quadtrees adalah salah satu strategi, di mana Anda dapat mendekatkan bucketing dan bagian building relasi dari indeks (bucket == building build).

Untuk contoh Point-in-Polygon-Test dimungkinkan untuk membuat cache tidak teratur dengan menggunakan:

  1. ! triangulasi delaunay terbatas pada penutup poli Anda, dengan titik-titik tepi perbatasan tambahan untuk deteksi penutup di luar
  2. memasukkan ini ke dalam skema pengindeksan quadtree dengan tidak lebih dari N segitiga per kotak (ember fraktal)
  3. temukan set segitiga yang merupakan titik - daun di quadtree
  4. temukan segitiga di mana titik terletak (bagian uji di atas maks. N segitiga)
  5. dan meminta ID poligon dari simpul segitiga
  6. jika ID unik, titik itu milik poligon, jika bukan di luar

Biaya untuk membangun timah dan quadtrees sangat tinggi dan sulit untuk dihitung dan quadtree harus menyeimbangkan segitiga besar dan kecil (segitiga yang tidak muat di kotak subtree yang lebih kecil).

Beberapa Alat dan Tautan:

Triangle - Membatasi triangulasi poligon

Quadtrees - Dengan contoh sumber

Stony Brook Repository - Struktur data dan geometri diskrit

huckfinn
sumber