Algoritma untuk menemukan centroid poligon beraturan (titik label)

13

Saya perlu menemukan centroid (atau titik label) untuk poligon berbentuk tidak teratur di Google Maps. Saya menunjukkan InfoWindows untuk paket dan memerlukan tempat untuk melabuhkan InfoWindow yang dijamin ada di permukaan. Lihat gambar di bawah.

teks alternatif teks alternatif

Pada kenyataannya saya tidak memerlukan apa pun yang spesifik dengan Google Maps, hanya mencari ide tentang cara menemukan poin ini secara otomatis.

Gagasan pertama saya adalah menemukan centroid "salah" dengan mengambil rata-rata lat dan lngs dan titik-titik penempatan acak dari sana sampai saya menemukan satu yang memotong poligon. Saya sudah memiliki kode point-in-polygon. Ini sepertinya sangat "meretas" bagi saya.

Saya harus mencatat bahwa saya tidak memiliki akses ke kode sisi server mana pun yang mengeluarkan geometri jadi saya tidak dapat melakukan sesuatu seperti ST_PointOnSurface (the_geom).

Jason
sumber

Jawaban:

6

Cepat dan kotor: Jika centroid "salah" tidak ada dalam poligon, gunakan simpul terdekat ke titik itu.

Pesolek
sumber
Saya belum memikirkan hal ini. Idealnya saya suka titik ini dalam poligon dan bukan di tepian, tapi mungkin ini yang saya maksudkan.
Jason
Setelah Anda menemukan titik tepi, Anda dapat memotong kotak kecil yang berpusat di titik itu dengan poligon dan kemudian memilih pusat massa persimpangan. Ketika kuadrat cukup kecil ini dijamin menjadi titik interior (meskipun tentu saja akan sangat dekat dengan tepi).
whuber
@Jason Jika Anda menggunakan centroid sungguhan, Anda mungkin tidak akan mengalami masalah ini. Seharusnya tidak terlalu sulit untuk menerjemahkan sesuatu dengan cepat ke JavaScript: github.com/cartesiananalytics/Pipra/blob/master/src/…
Dandy
Sementara solusi saya (sinar dari centroid palsu) akan bekerja sebagian besar waktu, saya pikir solusi ini mungkin akan bekerja paling baik karena kesederhanaannya dan fakta bahwa Anda dijamin menemukan titik setidaknya di tepi, dan dapat dengan mudah bergeser untuk berada di dalam poligon dengan sedikit usaha.
Jason
3

Anda mungkin ingin melihat ini: http://github.com/tparkin/Google-Maps-Point-in-Polygon

Tampaknya menggunakan algoritma Ray Casting yang harus cocok dengan kasus yang Anda sajikan.

Ada posting blog di sini. http://appdelegateinc.com/blog/2010/05/16/point-in-polygon-checking/

DavidF
sumber
Jika Anda ingin mengimplementasikan ini di sisi server, baik JTS (Java) dan Geos (C) mengimplementasikan fungsi ini.
DavidF
Ya, saya mungkin seharusnya menambahkan bahwa saya sudah memiliki kode untuk menentukan apakah centroid "dihitung" saya berada dalam poligon atau tidak. Yang sebenarnya saya inginkan adalah beberapa cara untuk membuat centroid yang ada di dalam poligon.
Jason
3

Algoritma ESRI (lebih tua) menghitung pusat massa dan, setelah mengujinya untuk dimasukkan dalam poligon, menggerakkannya secara horizontal jika perlu sampai terletak di dalam poligon. (Ini bisa dilakukan dalam banyak cara tergantung pada operasi fundamental apa yang tersedia dalam lingkungan pemrograman Anda.) Ini cenderung menghasilkan titik label yang cukup dekat dengan pusat visual poligon: coba pada ilustrasi.

whuber
sumber
1

Saya memecahkan masalah saya dengan memperluas kode epoly populer dari http://econym.org.uk/gmap . Pada dasarnya apa yang akhirnya saya lakukan adalah:

  • Buat serangkaian sinar yang dimulai dari "false centroid" dan luaskan ke setiap sudut dan samping (total 8)
  • Secara bertahap buat titik 10,20,30 ... persen ke bawah setiap sinar dan lihat apakah titik ini ada dalam poligon asli kami

Kode epoly diperpanjang di bawah ini:

google.maps.Polygon.prototype.Centroid = function() {
var p = this;
var b = this.Bounds();
var c = new google.maps.LatLng((b.getSouthWest().lat()+b.getNorthEast().lat())/2,(b.getSouthWest().lng()+b.getNorthEast().lng())/2);
if (!p.Contains(c)){
    var fc = c; //False Centroid
    var percentages = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]; //We'll check every 10% down each ray and see if we're inside our polygon
    var rays = [
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getSouthWest().lng())]}),
        new google.maps.Polyline({path:[fc,b.getNorthEast()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,b.getSouthWest()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),b.getSouthWest().lng())]})
    ];
    var lp;
    for (var i=0;i<percentages.length;i++){
        var percent = percentages[i];
        for (var j=0;j<rays.length;j++){
            var ray = rays[j];
            var tp = ray.GetPointAtDistance(percent*ray.Distance()); //Test Point i% down the ray
            if (p.Contains(tp)){
                lp = tp; //It worked, store it
                break;
            }
        }
        if (lp){
            c = lp;
            break;
        }
    }
}
return c;}

Masih sedikit retas tetapi tampaknya berhasil.

Jason
sumber
Metode ini akan gagal untuk beberapa poligon berliku. Misalnya, buffer polyline {{0, 9}, {10, 20}, {9, 9}, {20, 10}, {9, 0}, {20, -10}, {9, -9} , {10, -20}, {0, -9}, {-10, -20}, {-9, -9}, {-20, -10}, {-9, 0}, {-20, 10}, {-9, 9}, {-10, 20}, {0,9}} kurang dari 1/2. Ini juga tidak efisien dibandingkan dengan metode QAD Dandy, misalnya.
whuber
1

Algoritma 'kotor' lain untuk melakukan itu:

  • Ambil kotak pembatas geometri (Xmax, Ymax, Xmin, Ymin)

  • Loop sampai titik acak ( Xmin+rand*(Xmax-Xmin), Ymin+rand*(Ymax-Ymin) ) ditemukan dalam geometri (menggunakan Google-Maps-Point-in-Polygon )

Julien
sumber
+1 karena ini mungkin memiliki peluang yang bagus untuk hit yang kedua kalinya. Selama "acak" Anda dapat direproduksi setiap kali untuk tidak mengganggu pengguna, ini juga merupakan solusi yang valid. Peluangnya untuk tidak mengenai titik valid segera tipis, terutama jika Anda mulai dengan titik perkiraan yang baik.
Dandy
1
@Andy: Sebenarnya, dalam beberapa kasus ini bisa menjadi algoritma yang sangat buruk. Pertimbangkan sliver diagonal yang sempit misalnya. Ini ada dalam praktiknya (mis., Parsel panjang bagian depan jalan) dan dapat dengan mudah menempati kurang dari 0,1% dari kotak pembatas (kadang-kadang jauh lebih sedikit). Agar yakin (95% percaya diri) mengenai memukul poligon seperti itu dengan teknik ini akan membutuhkan sekitar 3.000 iterasi.
whuber
@ Wouber: Jika Anda memilih lokasi awal yang buruk ya itu bisa memakan waktu cukup lama untuk berjalan hingga selesai. Jika Anda juga menganggap bahwa secara hipotesis 95% klik akan berada pada geometri yang lebih diinginkan, ini mungkin hanya masalah 5% dari waktu. Sama halnya dengan pertanyaan SIG lainnya. Jika kinerja adalah tujuannya, tidak pernah ada solusi tunggal, yang terbaik adalah mengubah taktik berdasarkan heuristik. Tidak ada alasan untuk menjalankan ini untuk 3000 iterasi. Anda selalu dapat menalangi ke QAD saya setelah 10. Saya pikir akan sia-sia untuk mencoba yang ini untuk beberapa iterasi karena lokasi mungkin lebih diinginkan.
Dandy
@Dandy: Tapi ada apa dengan solusi QAD Anda? Anda bahkan dapat memodifikasinya sedikit dengan memindahkan dari labelpoint uji coba asli ke simpul terdekat di beberapa buffer internal poligon: masih QAD tetapi sekarang dijamin mendarat di lokasi internal fitur asli. BTW, strategi Anda segera bailing out adalah bagus. Setiap kali saya membuat kode penyelidikan acak seperti ini, saya mengkompilasi rasio area fitur dengan kotak pembatasnya, menggunakannya untuk menemukan waktu yang diharapkan untuk sukses, dan segera memperingatkan pengguna jika itu bisa lama.
whuber
@Whuber rasio area heuristik adalah ide bagus karena Anda baru saja menghitung centroid ketika Anda menghitung area. Adapun masalah dengan solusi QAD saya: ada di tepi. Jika saya memilih titik itu dan buffer seperti yang Anda katakan, bahwa jari-jari "kecil" mungkin lebih besar dari panjang di bagian yang sempit itu. Selalu ada sudut kasus. Begitu banyak yang harus dipertimbangkan, hanya untuk membuat balon yang akan mengacaukan UI dan mengaburkan geometri. Mungkin lebih baik untuk memilih titik tertinggi atau terendah.
Dandy
1

Mengingat klarifikasi Anda baru-baru ini bahwa Anda lebih suka lokasi yang benar-benar interior, Anda dapat memilih titik pada Medial Axis Transform yang tidak juga pada batas poligon. (Jika Anda tidak memiliki kode untuk MAT, Anda dapat memperkirakannya dengan buffer negatif terhadap poligon. Pencarian biner atau garis potong akan dengan cepat menghasilkan poligon interior kecil yang mendekati bagian dari MAT; gunakan titik apa pun pada batasnya.)

whuber
sumber
Saya mengerti apa yang Anda katakan tentang menggunakan ujung geometri sedemikian rupa sehingga ujungnya berada di bagian dalam poligon yang menarik. Saya tidak mengerti bagaimana cara membuat edge / vertex ini. Satu-satunya hal yang dapat saya pikirkan adalah membuat segitiga virtual dengan memotong sinar tegak lurus dari titik yang menarik ke segmen yang berlawanan dengan segmen dari titik yang dipilih. Titik tengah di antara kedua titik itu bisa menjadi puncak dari segitiga virtual itu.
Dandy
@Dandy: Itulah inti masalahnya. Ada banyak cara untuk melakukannya tergantung pada apa yang SIG Anda lakukan secara asli. Misalnya, setelah Anda menemukan sinar yang memotong fitur asli dalam set panjang positif, persimpangan itu akan menjadi penyatuan segmen segmen yang terpisah. Gunakan pusat dari salah satu segmen itu. Cara lain adalah mulai dengan titik mana saja pada fitur (lebih disukai dekat bagian tengahnya, yang merupakan apa yang dicapai metode QED Anda), buat poligon kecil sederhana (misalnya, persegi) berpusat di sana, berpotongan dengan fitur asli, pilih yang terhubung unik komponen ...
whuber
(lanjutan) ... berisi titik awal, dan secara rekursif memilih pusat untuk komponen itu. Akan ada banyak metode yang tersedia ketika GIS Anda memungkinkan Anda mengulangi urutan simpul yang menggambarkan batas fitur. Jika penyangga negatif didukung, Anda dapat secara iteratif menemukan satu set titik interior jarak maksimum ("kerangka", yang merupakan subset dari MAT). Ini sedikit mahal tetapi cukup mudah untuk diprogram dan menghasilkan poin label yang sangat baik.
whuber
0

Mengapa tidak menggunakan centroid hanya untuk posisi vertikal (lintang)? Kemudian, Anda dapat memposisikan label secara horizontal dengan memilih garis bujur rata-rata pada garis lintang itu . (Untuk ini, Anda perlu menemukan nilai bujur untuk tepi poligon pada garis lintang tertentu, yang seharusnya tidak memberi Anda masalah).

Juga, berhati-hatilah dengan bentuk U, dan yang lebih kompleks. :) Mungkin bagi mereka, pilih rata-rata dari pasangan garis bujur paling kanan (masing-masing pasangan akan sesuai dengan sepotong poligon), karena jendela info berorientasi seperti itu?

Ini memberi Anda sedikit lebih banyak kontrol atas penentuan posisi, juga; misalnya, mungkin lebih baik untuk memposisikan jendela info di 66 atau 75% secara vertikal, agar poligon lebih terlihat. (Atau mungkin tidak! Tetapi Anda memiliki tombol untuk mengubah.)

Dan S.
sumber
0

Bagaimana kalau hanya menggunakan titik yang diklik pengguna untuk memilihnya, jika dipilih oleh pengguna itu.

Pesolek
sumber
Itu dapat dipilih dengan klik mouse atau permintaan non-spasial, jadi ini tidak akan selalu berhasil.
Jason
0

Saya mencoba menyelesaikan ini juga. Saya telah memberlakukan syarat pada poligon saya bahwa mereka tidak dapat memiliki garis silang yang masuk ke dalam apa yang akan saya uraikan.

Jadi, pendekatan saya menggunakan triangulasi. Mengambil simpul acak (mungkin mengambil simpul pada titik ekstrim N, E, W, atau S dapat menyederhanakan hal-hal).

Dari dhuwur ini, tarik garis ke dhuwur satu dhuwur, yaitu jika dhuwur Anda adalah dwma 3, lihatlah dwma 3 + 2.

Buat garis dari titik awal Anda ke titik ini. Jika garis yang dibangun:

  1. tidak melintasi garis lain dan
  2. titik tengahnya tidak di luar poligon

Maka Anda telah membuat segitiga yang berada di dalam poligon. Jika simpul yang berhasil adalah n + 2, maka segitiga Anda adalah {n, n + 1, n + 2}, yang akan kita sebut sebagai {v, v1, v2}. Jika tidak, coba simpul berikutnya, dan lanjutkan sampai semua simpul telah dicoba.

Saat Anda menemukan segitiga, temukan pusatnya dengan mengambil garis dari titik v ke titik tengah v1 dan v2. Titik tengah garis itu dijamin berada di dalam segitiga, dan di dalam poligon.

Saya belum mengkodekan ini, tetapi saya bisa melihat ketika saya memikirkannya bahwa poligon dengan garis silang sebenarnya akan menyebabkan beberapa kondisi eksotis di mana ini tidak bekerja. Jika itu jenis poligon yang Anda miliki, Anda harus menguji setiap segmen garis pada poligon dan pastikan itu tidak dilintasi. Lewati segmen garis yang dilintasi, dan saya pikir itu akan berhasil.


sumber