Mencari algoritma untuk menempatkan jumlah titik maksimum dalam area terbatas pada jarak minimum?

17

Saya memiliki lapisan poligon yang menjelaskan batasan; Saya ingin menambahkan poin dalam area ini. Saya ingin menambahkan poin sebanyak mungkin, tetapi mereka harus memiliki jarak minimum di antara mereka. Apakah mungkin untuk melakukan ini dengan GIS?

Untuk memperjelas, akan lebih baik jika grid yang dipesan dapat dihasilkan, karena ini akan menjamin poin terbanyak. Namun kendala jarang akan memungkinkan ini, dan mungkin lebih baik untuk menghapus poin untuk memungkinkan offset lebih cocok dalam kendala.

algorithm point Matthew Snape
sumber
1. Ya. 2. Apakah Anda ingin acak atau dipesan (kisi)?
Brad Nesom
Tampaknya ada dua pertanyaan. Apakah Anda ingin algoritma melakukan ini di luar perangkat lunak? Atau Anda ingin tahu sistem GIS apa yang bisa melakukan ini?
Brad Nesom
1
Apakah titik dibatasi sehingga mereka harus> = jarak minimum dari batas poligon? Jika, maka pertanyaannya mungkin lebih jelas dinyatakan sebagai: Bagaimana saya bisa mengemas jumlah lingkaran maksimum ke dalam poligon?
Kirk Kuykendall
Entah bagaimana terkait: gis.stackexchange.com/q/4927/162
julien
1
@ qva Tidak ada, karena solusi tepat yang dapat ditemukan asimetris dan sulit diperoleh bahkan untuk bentuk sederhana seperti persegi panjang. Metode komputasi terbaik yang saya temukan didasarkan pada annealing simulasi spasial (dan mereka bekerja dengan sangat baik, meskipun mereka membutuhkan banyak perhitungan). Menggunakannya, saya telah melihat solusi untuk banyak poligon dari berbagai bentuk. Jelas bahwa batas poligon mengendalikan solusi yang dekat dengan batas; jauh di dalam interior mereka cenderung mendekati kemasan disk heksagonal.
Whuber

Jawaban:

5

Saya pikir ini bisa dianggap sebagai masalah "pengepakan".

Jika demikian, Anda mungkin ingin mencoba Algoritma Genetika, mungkin yang mirip dengan yang ada pada Algoritma Genetika untuk Pengemasan Poligon .

Kirk Kuykendall
sumber
Referensi yang menarik, terima kasih. Pandangan sekilas menunjukkan bahwa algoritma kertas membutuhkan poligon menjadi persegi panjang. Apakah Anda tahu apakah itu dapat digeneralisasi ke poligon yang sewenang-wenang?
whuber
9

Saya tidak tahu alat GIS untuk melakukan itu, tapi saya punya ide tentang algoritma.

Pertama, perkiraan angka titik maksimum dapat diperoleh dengan rumus ini:

Nb = 4.A / Pi.d^2

(di mana Aarea poligon dan djarak jarak minimum).

Kemudian, untuk mencoba menemukan titik-titik ini ke dalam poligon, pola terbaik bukanlah kotak persegi tetapi kotak heksagonal. Lihat:

kuadrat vs kisi heksagonal

Akhirnya, beberapa teknik optimasi menggunakan model kekuatan dapat digunakan untuk memperbaiki posisi relatif dari titik-titik.

NB: Ini adalah masalah yang dikenal dalam kristalografi .

Julien
sumber
alat gis untuk melakukan itu ... ian-ko.com geo-wizard titik acak dalam poligon.
Brad Nesom
1
Terima kasih! Tetapi pertanyaannya bukan tentang titik acak dalam poligon, kan?
julien
Sebagai perkiraan awal cepat dan kotor, pengemasan heksagonal berfungsi dengan baik. Namun, hampir tidak pernah optimal. Saya berharap peningkatan potensial sebanding dengan panjang perimeter poligon, jadi untuk poligon non-berliku dengan banyak titik ini bukan pendekatan yang buruk.
whuber
6

Lihat utas di /math/15624/distribute-a-fixed-number-of-points-uniformly-inside-a-polygon . Secara khusus, perhatikan referensi (dalam komentar) untuk "proses disk Poisson" dan lakukan pencarian Web. Koneksi dengan pertanyaan saat ini adalah bahwa ketika Anda dapat mendistribusikan sejumlah poin secara seragam, maka Anda dapat secara sistematis meningkatkan jumlah tersebut hingga tidak ada lagi poin yang dapat dimasukkan ke dalam poligon dan yang memecahkan masalah memaksimalkan jumlah titik yang dikenakan suatu persyaratan jarak minimum. (Secara teknis, kedua masalah adalah masalah optimasi ganda di mana tujuan dan kendala dipertukarkan.)

whuber
sumber
0

Solusinya harus segitiga sama sisi, http://en.wikipedia.org/wiki/Equilateral_triangle . Satu-satunya pertanyaan adalah panjang sisi dan "xy-offset" sehubungan dengan poligon Anda.

(sama seperti kisi heksagonal yang disebutkan di bawah)

Uffe Kousgaard
sumber
1
Ini benar hanya di dalam bidang yang tak terbatas. Batas dari poligon berhingga sangat membatasi konfigurasi. Ketika ada banyak poin, mereka kira - kira membentuk segitiga sama sisi.
whuber