Seleksi Tetangga Terdekat Terdekat di QGIS

14

Saya memiliki daftar yang berisi lebih dari 100.000 poin dalam format lat / long yang telah saya impor ke qgis.

Sekarang, apa yang saya coba lakukan di sini adalah mengelompokkan semua poin ini ke dalam kelompok kotak dan maksud saya adalah bahwa saya ingin membagi peta menjadi kotak pembatas.

Persyaratan saya adalah sebagai berikut:

  • tidak ada grup kotak yang memiliki KURANG DARI 100 dan TIDAK LEBIH DARI 200 poin
  • tidak boleh ada titik terletak di lebih dari satu kelompok
  • semua poin harus didasarkan pada tetangga terdekat mereka

Bagaimana saya bisa mencapai ini melalui qgis?

Saya berasumsi bahwa seseorang dapat melewati beberapa kode kueri khusus dan menyimpan hasil atau kotak yang dibuat sebagai shapefile benar? Bisakah seseorang tolong jelaskan bagaimana ini bisa dilakukan dan seperti apa kode itu?

Seperti yang disebutkan, tujuan saya adalah untuk memiliki sekelompok kotak persegi ditampilkan sebagai lapisan shapefile di mana dalam setiap kotak ada tidak kurang dari 100 properti dan tidak lebih dari 200.

NetConstructor.com
sumber
6
Untuk semua orang yang menandai pertanyaan ini sebagai "favorit": Mengapa tidak membatalkannya juga? Orang akan berpikir bahwa pertanyaan favorit Anda harus menjadi pertanyaan yang bagus.
underdark
1
Mengapa Anda perlu tinju? Jika Anda membuat kotak berdasarkan hitungan, ukurannya akan berbeda-beda, jadi ubin tidak sesuai dengan pertanyaan. Mungkin lebih mudah untuk dikelompokkan menjadi poligon (yaitu convex hull).
diciu
@diciu terima kasih atas tanggapannya. Ya saya kira lambung cembung akan baik-baik saja karena saya bisa mengubahnya menjadi kotak setelahnya. Kode apa yang harus saya gunakan untuk melakukannya menggunakan pendekatan cembung cembung?
NetConstructor.com
2
Jika Anda menggunakan convex hulls, kotak pembatas Anda (melampirkan lambung) akan tumpang tindih dan persyaratan Anda untuk satu titik berada dalam satu BBOX tidak lagi puas. Convex hulls tidak berfungsi sebagai langkah perantara menuju BBOX melainkan sebagai pengganti. Dan bahkan kemudian, menciptakan solusi generik akan agak terlibat.
diciu

Jawaban:

13

Saya dapat membuat Anda menjadi bagian dari perjalanan ke sana dengan mengasumsikan Anda telah menemukan cara untuk meminta (a) setengah dari serangkaian poin paling timur dan (b) setengah dari serangkaian poin paling utara. Dari sini Anda tentu saja dapat dengan mudah memperoleh (c) setengah bagian barat atau (d) bagian paling selatan. (Saya tidak tahu QGIS, tetapi satu cara untuk melakukan (a) secara umum adalah meminta median koordinat x dan kemudian mengambil semua poin yang koordinat xnya melebihi itu. Solusi untuk (b) - (d) serupa .)

Dengan menggunakan kemampuan ini, solusi diperoleh dengan rekursi yang mudah. Untuk menggambarkannya, mari kita asumsikan ada prosedur Half, mengimplementasikan operasi sebelumnya, yang mengambil dua argumen: yang pertama adalah seperangkat poin dan yang kedua adalah kode yang sama dengan trueketika partisi timur-barat diinginkan dan sama dengan yang falselainnya. Ini mengembalikan dua himpunan bagian dari inputnya yang mempartisi itu seperti yang diminta.

Procedure Box(P: set of points, i: boolean, n: integer)
Begin
    If (Count(P) > 2*n) then
        {R,S} = Half(P,i)
        Q = Box(R,!i,n) + Box(S,!i,n)
    Else
        Q = {P}
    Endif
    Return Q
End

Dalam pseudocode ini, R dan S partisi P; Kotak (R,! I, n) adalah partisi R dalam arah ortogonal , Kotak (S,! I, n) adalah partisi S dalam arah ortogonal, "+" berarti membentuk kesatuan set-theoretik, dan {} menunjuk satu set. (Bergantian arah membelah menciptakan kotak daripada strip.) Parameter n menentukan ukuran minimum grup di partisi; ukuran maksimum adalah 2 n .

Contoh

Di sini, sebagai ilustrasi, adalah himpunan P dari 12.891 titik acak yang dipartisi Box(P,true,100)ke dalam kelompok-kelompok dengan ukuran antara 100 dan 200. Algoritma menciptakan 128 kotak yang 37 memiliki 100 poin dan 91 memiliki 101 poin.

whuber
sumber
2
Algoritma ini efisien. Berjalan pada satu inti, itu diproses sepuluh kali lebih banyak poin (128.910) dalam 18 detik. Ini berskala sebagai O (n log (n) log (n)) untuk n poin. (Ini dapat ditingkatkan untuk menghilangkan salah satu faktor log (n), tetapi upaya ini tidak mungkin bermanfaat.)
whuber
1
@ W, apakah Anda menggunakan semacam lexicographical untuk memfasilitasi partisi titik koordinat?
2
@whuber ini luar biasa
dassouki
1
@Dan Semacam leksikal akan membantu tetapi tidak perlu. Perhatikan bahwa median nilai n dapat ditemukan dalam waktu O (n) waktu (bukan O (n log (n))), sehingga pembagian titik menjadi separuh timur-barat atau separuh utara-selatan secara asimptotik merupakan O (n ) perhitungan.
whuber