Algoritma untuk menemukan poligon yang melampirkan poin

8

Saya mencoba menemukan algoritma yang dapat menentukan poligon sekecil mungkin untuk mencakup beberapa poin.

Saya tahu bagaimana cara mendapatkan cembung lambung di sekitar semua titik, tetapi mengatakan bahwa titik-titik tersebut terletak di pulau yang berbeda, apakah mungkin untuk menentukan bahwa ada kesenjangan antara kelompok yang berbeda dan mendapatkan poligon terpisah untuk masing-masing kelompok?

algorithm polygon convex-hull clustering concave-hull jjrdk
sumber
Jawabannya adalah hanya satu poligon yang dibutuhkan; wilayahnya bisa mendekati nol; dan itu tidak pernah unik. (Salah satu cara untuk menemukan solusi: ada titik di pesawat tempat setiap titik di set aslinya terlihat. Lacak rute yang tidak memotong sendiri dari titik ini ke masing-masing titik yang diberikan pada gilirannya, membentuk bintang dengan sinar yang sangat sempit.) Ini menunjukkan bahwa masalahnya tidak sepenuhnya dinyatakan: ia membutuhkan pernyataan tujuan analitis yang lebih jelas dan lebih menyeluruh.
whuber

Jawaban:

9

Kedengarannya seperti Anda memerlukan algoritma pengelompokan (mis. K-means clustering) pertama, diikuti oleh lambung kapal (convex hull, tetapi lambung cekung mungkin memiliki area yang lebih kecil tetapi lebih sulit untuk diterapkan).


sumber
Lihat juga: en.wikipedia.org/wiki/Hierarchical_clustering
julien
3

Alat "Clustr" yang kami gunakan (d) di Flickr untuk menghasilkan shapefile yang berasal dari foto yang diberi tag geo mungkin bermanfaat:

https://github.com/straup/Clustr

(Stackexchange mencegah saya menambahkan lebih dari 2 tautan dalam posting ini. Jika Anda mencari "bentuk alfa", Anda dapat menemukan kode tersebut.flickr posting blog yang kami lakukan ketika kami mengumumkan shapefile.)

Itu dirancang untuk mencoba dan menghasilkan kontur dari kantong poin yang terus berubah (alias foto). Bit matematika-y yang sebenarnya ada di sini:

http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

Clustr memiliki beberapa bug yang dikenal tetapi sebagian besar berfungsi, sebagian besar waktu ...

pengguna2016
sumber
2

dari perspektif basis data kedengarannya seperti Anda ingin mengelompokkan poin pada ilands dan membuat convexhull pada setiap grup.

di postgis akan terlihat seperti:

SELECT ST_Convexhull(ST_Collect(p.the_geom))
FROM pointtable p INNER JOIN islands i ON ST_Intersects(p.the_geom,i.the_geom)
GROUP BY i.id;

/ Nicklas

Nicklas Avén
sumber
Saya pikir saya tidak jelas dalam pertanyaan awal saya. Intinya adalah bahwa saya tidak tahu di mana titik-titiknya berada, tetapi akan berada di lokasi yang berbeda, jadi saya membutuhkan algoritma untuk secara dinamis membuat cluster di mana titik-titik tersebut, tidak memindahkannya ke area yang ditentukan. Saya memodifikasi algoritma pengelompokan k-means untuk mencari kumpulan data untuk centroid cluster dan kemudian cluster.
jjrdk
Maksud Anda, Anda tidak tahu di mana Kepulauan? Anda tidak memiliki representasi vektor pulau, ok. Tapi apa yang Anda maksud dengan "tidak memindahkan mereka". Saya tidak menyarankan memindahkan apa pun? ...
Nicklas Avén
Saya tidak tahu di mana grup (pulau) akan berada, itu akan tergantung pada lokasi poin. Jadi saya mencoba menemukan poligon terkecil yang melingkupi lokasi titik. Dengan pindah, maksud saya titik pengelompokan dalam jumlah cluster yang ditentukan seperti dalam pengelompokan k-means.
jjrdk
1

arcpy.AggregatePoints_cartography (pntGeometryList, outAppendFeatureClass, buffer_radius)

Di mana pntGeometryList adalah daftar poin Anda, outAppendFeatureClass maka akan menampilkan classecreecration agregation dan buffer_radius yang akan menentukan tautan antara setiap titik 'yang menghadap ke luar'.

Berbulu
sumber
Maaf, baru saja dapatkan sisa pertanyaan Anda, yang tidak saya baca.
Berbulu
Bagaimana Anda menyusun poin Anda?
Berbulu
1

Pada awalnya saya pikir saran Dan untuk k-means masuk akal, tetapi setelah melihat data hasil set mouse pada halaman wikipedia untuk k-means , sepertinya pengelompokan Expectation-Maximization lebih dekat dengan apa yang Anda inginkan.

masukkan deskripsi gambar di sini

Kirk Kuykendall
sumber
1
Terima kasih atas jawaban Anda, saya benar-benar telah maju dan membuat versi modifikasi dari algoritma k-means yang mengelompokkan berdasarkan jarak maksimum. Saya ngeblog di
jjrdk
Tampak hebat. Saya pikir EM pasti akan lebih sulit untuk diterapkan. Akan menarik untuk melihat apakah kode Anda akan bekerja di silverlight, mungkin menggunakan TPL ini .
Kirk Kuykendall