Mengoptimalkan perhitungan tetangga terdekat menggunakan PostGIS

13

Saya menggunakan PostGIS untuk menghitung tetangga terdekat poligon. Yang ingin saya hitung adalah jarak minimum dari setiap poligon, ke poligon terdekat.

Sejauh ini saya mendapat banyak bantuan dari jawaban Mike Toews (yang saya kutip dengan perubahan kecil) di sini:

SELECT 
  a.hgt AS a_hgt,
  b.hgt AS b_hgt,
  ST_Distance(a.the_geom, b.the_geom) AS distance_between_a_and_b
FROM 
  public."TestArea" AS a, public."TestArea" AS b
WHERE
  a.hgt !=  b.hgt AND ST_Distance(a.the_geom, b.the_geom) < 400

Lalu saya menghitung minimum:

SELECT a_hgt, MIN(distance_between_a_and_b)
FROM public."lon_TestArea"
GROUP BY a_hgt

Namun, tantangan saya adalah menghitung ini untuk sejumlah besar poligon (1.000.000). Karena perhitungan di atas membandingkan setiap poligon dengan setiap poligon lain, saya bertanya-tanya bagaimana saya bisa meningkatkan perhitungan sehingga saya tidak harus melakukan perhitungan 10 ^ 12.

Satu pemikiran yang saya miliki adalah untuk buffer setiap poligon, dan kemudian menghitung tetangga terdekat dari semua nilai dalam buffer untuk poligon itu, dan mencatat minimum. Saya tidak yakin apakah itu pendekatan terbaik, atau apakah ada fungsi di PostGIS yang harus saya gunakan.


EDIT: Menggunakan salah satu saran Nicklas, saya bereksperimen dengan ST_Dwithin():

CREATE TABLE mytable_withinRange AS SELECT 
  a.hgt AS a_hgt,
  b.hgt AS b_hgt,
  ST_DWithin(a.the_geom, b.the_geom, 400)
FROM 
  public."lon_TestArea" AS a, public."lon_TestArea" AS b

masukkan deskripsi gambar di sini

Ini mengembalikan tabel ID dari setiap poligon, dan apakah itu dalam jarak tertentu atau tidak. Apakah mungkin untuk membangun IF/ELSEpernyataan tipe menggunakan SQL? (Saya membaca tentang menggunakan CASEkondisi) Atau haruskah saya mencoba bergabung dengan tabel yang saya hasilkan ke tabel asli dan kemudian menjalankan kueri lagi menggunakan ST_Distance?

djq
sumber
lihat contoh kedua di tautan boston gis dalam jawaban saya. Anda harus menggunakan st_dwithin di bagian permintaan mana.
Nicklas Avén

Jawaban:

7

Ada bagian besar "Tetangga Terdekat" di halaman BostonGIS .


EDIT:

Bagaimana tentang

CREATE TABLE mytable_withinRange AS SELECT 
 a.hgt AS a_hgt,
 b.hgt AS b_hgt
FROM 
 public."lon_TestArea" AS a, public."lon_TestArea" AS b
WHERE 
 ST_DWithin(a.the_geom, b.the_geom, 400)

Mengenai pernyataan CASE :

SELECT a,
   CASE WHEN a=1 THEN 'one'
        WHEN a=2 THEN 'two'
        ELSE 'other'
   END
FROM test;
underdark
sumber
Apakah Anda tahu jika garis WHERE ST_DWithin(a.the_geom, b.the_geom, 400)akan mencegah jarak yang lebih besar 400dari yang akan dihitung atau baru direkam? Juga, dapatkah pernyataan kasus digunakan untuk perhitungan numerik? misalnya:CASE WHEN ST_DWithin(a.the_geom, b.the_geom, 400) == TRUE THEN ST_DWithin(a.the_geom, b.the_geom)
djq
1
@celenius Jika jarak lebih dari 400 m, tidak ada bagian pilih yang akan dihitung. Saya tidak mengerti mengapa Anda ingin menempatkan kasing ke dalam campuran.
Nicklas Avén
@Nicklas ok - Saya mengerti. Saya pikir itu mungkin berarti bahwa hanya jarak kurang dari 400 yang disimpan; ini membuatnya jauh lebih mudah daripada saya. Terima kasih!
djq
3

Halo

Ada beberapa hal yang perlu dipertimbangkan untuk membuat hal-hal bergerak lebih cepat, dan beberapa hal yang mungkin terjadi di masa depan.

Pertama , Anda menyebutkan bahwa Anda mempertimbangkan untuk menggunakan buffer untuk menemukan poligon dalam kisaran minimum untuk menghindari penghitungan semua kombinasi.

Sebagaimana dibahas dalam tautan lain dari Boston gis cara yang tepat untuk melakukannya di PostGIS adalah menggunakan ST_Dwithin . ST_Dwithin menggunakan indeks untuk menemukan tetangga dalam rentang tertentu.

Itu tergantung pada dataset tentu saja apakah itu cukup untuk hanya menggunakan nilai tetap untuk st_DWithin untuk semua poligon atau jika Anda perlu melakukan sesuatu seperti underdark dan wildintellect sedang mendiskusikan.

Hal kedua adalah menggunakan PostGIS 1.5+ di sini. Itu karena perhitungan poligon ke poligon jauh lebih cepat sejak 1,5 jika kotak pembatasnya tidak berpotongan. Anda dapat membaca lebih lanjut tentang itu di sini. .

Hal ketiga untuk disebutkan adalah masa depan.

Dalam PostgreSQL 9.1 akan ada sesuatu yang disebut knn-gist. Itu adalah indeks yang tidak bisa hanya menjawab ya atau tidak tetapi juga mengembalikan hasil yang dipesan langsung dari indeks. Anda dapat membaca tentang itu di sini .

Tetapi masih ada banyak pekerjaan yang harus dilakukan di pihak PostGIS sebelum knn intis akan membantu untuk hal-hal seperti ini. Ada tiket untuk itu di sini.

Salam

Nicklas

Nicklas Avén
sumber
Terima kasih atas sarannya Nicklas; karena saya merasa sulit untuk menjalankan pgAdmin / PostGIS dan saya pikir saya akan menghindari penggunaan 1.5 saat ini. Sepertinya ST_Dwithin () adalah cara untuk menyelesaikan ini.
djq
2
menginstal 1.5 tidak akan mempengaruhi hubungan antara postgresql dan pgadmin. Anda dapat memiliki lebih dari satu versi postgis di server database dan kemudian Anda memuat salah satunya di dalam database. sehingga Anda dapat memiliki satu database 1.4 dan satu 1.5 satu server database yang sama.
Nicklas Avén
1

Halaman-halaman berikut yang berhubungan dengan pekerjaan master Nathan Kerr memberikan beberapa wawasan yang baik tentang masalah langsung ini. Rekan kerja saya mencoba metode Bostongis di sini dan di sini , tetapi ada beberapa masalah yang membuatnya berfungsi dengan benar.

Pendekatan lain untuk berpikir tentang yang mirip dengan buffer adalah dengan melakukan perluasan / kontrak persegi panjang. Pada dasarnya, lewati 1 lakukan kotak pembatas (ini adalah unit + x lurus ke kotak poligon asli Anda) berpotongan yang menurut Anda akan menangkap setidaknya satu perpotongan. Untuk data yang mendapat titik potong lakukan sub kueri yang menguji kecocokan itu untuk yang terdekat. Untuk data yang gagal cocok perluas kotak pembatas dan ulangi.

Ini jelas masalah pemrograman rekursif, dan mungkin lebih baik dilakukan dengan Python dengan Shapely daripada 100% langsung di postgis.

kecerdasan liar
sumber