it-swarm-id.com

Apakah ada algoritma yang efisien untuk menghasilkan lambung cekung 2D?

Memiliki satu set (2D) poin dari file GIS (peta kota), saya perlu membuat poligon yang mendefinisikan 'kontur' untuk peta itu (batasnya). Parameter inputnya adalah titik yang ditetapkan dan 'panjang tepi maksimum'. Kemudian akan menampilkan poligon yang sesuai (mungkin non-cembung).

Solusi terbaik yang saya temukan sejauh ini adalah untuk menghasilkan segitiga Delaunay dan kemudian menghapus tepi eksternal yang lebih panjang dari panjang Edge maksimum. Setelah semua tepi eksternal lebih pendek dari itu, saya cukup menghapus tepi internal dan mendapatkan poligon yang saya inginkan. Masalahnya adalah, ini sangat memakan waktu dan saya bertanya-tanya apakah ada cara yang lebih baik.

59
Fabio Ceconello

Makalah ini membahas tentang Pembentukan poligon sederhana yang efisien untuk mengkarakterisasi bentuk sekumpulan titik dalam bidang dan menyediakan algoritme. Ada juga applet Java yang memanfaatkan algoritma yang sama di sini .

2
Amirali

Salah satu mantan siswa di lab kami menggunakan beberapa teknik yang berlaku untuk tesis PhD-nya. Saya percaya salah satunya disebut "bentuk alfa" dan dirujuk dalam makalah berikut:

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

Makalah itu memberikan beberapa referensi lebih lanjut yang bisa Anda ikuti.

10
nsanders

Jawabannya mungkin masih menarik untuk orang lain: Seseorang dapat menerapkan a variasi dari algoritma marching square , diterapkan (1) dalam lambung cekung, dan (2) kemudian pada (mis. 3) berbeda skala bahwa saya bergantung pada kepadatan rata-rata poin. Timbangan perlu saling mengalikan satu sama lain, seperti Anda membangun kotak yang dapat Anda gunakan untuk pengambilan sampel yang efisien. Hal ini memungkinkan untuk dengan cepat menemukan sampel kosong = kuadrat, sampel yang benar-benar berada dalam "cluster/cloud" titik, dan yang ada di antaranya. Kategori yang terakhir kemudian dapat digunakan untuk menentukan dengan mudah garis-poli yang mewakili bagian dari lambung cekung.

Semuanya linier dalam pendekatan ini, tidak perlu triangulasi, tidak menggunakan bentuk alfa dan berbeda dengan penawaran komersial/paten seperti dijelaskan di sini ( http://www.concavehull.com/ )

2
monnoo

Orang-orang di sini mengklaim telah mengembangkan pendekatan tetangga terdekat k untuk menentukan lambung cekung satu set poin yang berperilaku "hampir linear pada jumlah poin". Sayangnya kertas mereka tampaknya dijaga dengan sangat baik dan Anda harus meminta mereka untuk itu.

Berikut adalah set referensi yang baik yang termasuk di atas dan mungkin mengarahkan Anda untuk menemukan pendekatan yang lebih baik.

2
Vinko Vrsalovic

Bing Maps V8 SDK interaktif memiliki opsi lambung cekung dalam operasi bentuk lanjutan.

https://www.bing.com/mapspreview/sdkrelease/mapcontrol/isdk/advancedshapeoperations?toWww=1&redig=D53FACBB1A00423195C53D841EA0D14E#JS

Dalam ArcGIS 10.5.1, ekstensi 3D Analyst memiliki alat Volume Batas Minimum dengan tipe geometri lambung cekung, bola, amplop, atau cembung cembung. Ini dapat digunakan di tingkat lisensi apa pun.

Ada algoritma lambung cekung di sini: https://github.com/mapbox/concaveman

1
Jaybird64

Solusi sederhana adalah berjalan di sekitar Ujung poligon. Dengan Edge saat ini dari titik penghubung batas P0 dan P1, titik berikutnya pada batas P2 akan menjadi titik dengan A terkecil yang mungkin, di mana

H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength

Kemudian Anda atur

P0 <- P1
P1 <- P2

dan ulangi sampai Anda kembali ke tempat Anda mulai.

Ini masih O (N ^ 2) sehingga Anda ingin sedikit mengurutkan daftar poin Anda. Anda dapat membatasi serangkaian poin yang perlu Anda pertimbangkan pada setiap iterasi jika Anda mengurutkan poin, katakanlah, kaitannya dengan pusat massa kota.

1
Mike F

Anda dapat melakukannya di QGIS dengan plug in ini; https://github.com/detlevn/QGIS-ConcaveHull-Plugin

Bergantung pada bagaimana Anda membutuhkannya untuk berinteraksi dengan data Anda, mungkin perlu memeriksa bagaimana hal itu dilakukan di sini.

1
Cameron

Pertanyaan bagus! Saya belum mencoba ini sama sekali, tetapi tembakan pertama saya adalah metode berulang ini:

  1. Buat set N ("tidak terkandung"), dan tambahkan semua poin di set Anda ke N.
  2. Pilih 3 poin dari N secara acak untuk membentuk poligon awal P. Hapus dari N.
  3. Gunakan beberapa algoritma titik-dalam-poligon dan lihat titik dalam N. Untuk setiap titik dalam N, jika sekarang berisi oleh P, hapus dari N. Begitu Anda menemukan titik di N yang masih tidak terkandung dalam P, lanjutkan ke langkah 4. Jika N menjadi kosong, Anda selesai.
  4. Panggil titik yang Anda temukan A. Temukan garis dalam P yang paling dekat dengan A, dan tambahkan A di tengahnya.
  5. Kembali ke langkah 3

Saya pikir ini akan berhasil selama performanya cukup baik - heuristik yang bagus untuk 3 poin awal Anda mungkin bisa membantu.

Semoga berhasil!

1
Rob Dickerson

Sebagai referensi yang diadopsi secara liar, PostGIS dimulai dengan convexhull dan kemudian memasukkannya, Anda dapat melihatnya di sini.

https://github.com/postgis/postgis/blob/380583da73227ca1a52da0e0b3413b92ae69af9d/postgis/postgis.sql.in#L5819

0
Evan Carroll

Solusi perkiraan cepat (juga berguna untuk convex hulls) adalah menemukan batas utara dan selatan untuk setiap elemen kecil timur-barat.

Berdasarkan seberapa banyak detail yang Anda inginkan, buat array berukuran tetap dari batas atas/bawah. Untuk setiap titik, hitung kolom E-W mana yang ada di dalamnya dan perbarui batas atas/bawah untuk kolom tersebut. Setelah Anda memproses semua poin, Anda dapat menginterpolasi poin atas/bawah untuk kolom yang terlewat.

Anda juga perlu melakukan pemeriksaan cepat terlebih dahulu untuk mendapatkan bentuk tipis yang sangat panjang dan memutuskan apakah akan membuang bin NS atau Ew.

0
Martin Beckett