Menemukan pusat geometri objek?

37

Diberikan satu set poin 2D atau 3D:

Bagaimana menemukan pusat geometri suatu objek?

Menurut gambar berikut, pusat geometri berbeda dari pusat massa jika dihitung dalam bentuk yang paling sederhana yaitu, kepadatan massa homogen. Masalahnya muncul, memang, dalam perhitungan mereka. Umumnya, satu pendekatan adalah rata-rata koordinat X dan koordinat Y secara terpisah, yaitu menemukan posisi rata-rata untuk titik yang diberikan (di sini dalam 2D). Ini dapat digunakan sebagai centroid untuk set poin yang mewakili suatu objek. Seperti yang ditunjukkan, karena titik ekstra di sepanjang tepi bawah, untuk persegi panjang sederhana centroid yang dihasilkan adalah (0,5,0,4) sedangkan jawaban yang benar adalah (0,5,0,5) .
Perhatikan bahwa contoh yang diberikan terlalu sederhana. Namun masalah yang menarik adalah untuk bentuk kompleks dalam 2D ​​dan objek dalam 3D yang hanya koordinat titik tersedia.
BTW, cara komputasi yang efisien menarik.

Hanya untuk menyebutkan bahwa saya telah memeriksa beberapa tautan web seperti Wikipedia, tetapi masalah saya saat ini adalah bahwa ada sekelompok titik 2D dan 3D yang ingin menemukan titik sebagai perwakilan bagi mereka. Dengan demikian centroid menjadi menarik. Poin diberikan tanpa informasi topologi. Anda dapat menganggap mereka sebagai point cloud. Demonstrasi di sini disediakan untuk memperjelas bahwa rata-rata koordinat yang dikenal (lihat misalnya T&J Stack Overflow ) ini mungkin salah seperti yang ditunjukkan dalam contoh.

masukkan deskripsi gambar di sini

Berikut ini beberapa implementasi untuk perbandingan:

  • aa = jawaban yang diterima di bawah
  • chull = cembung-lambung poin yaitu, poligon emas
  • cent = centroid diusulkan dalam Wikipedia dan dibahas dalam aa sebagai centroid poligon
  • centl = centroid dari polyline seperti yang dijelaskan dalam aa

Secara visual, centlterlihat lebih representatif untuk geometri yang diberikan dibandingkan dengan cent. Dua orang lain terlihat menjanjikan di sini, tetapi biasanya mereka terlalu bias jika dispersi poin tidak homogen seperti kasus biasa.
Dan juga pertimbangkan bahwa meskipun cembung membuat lambung masalah menjadi lebih sederhana namun dapat menghasilkan tepi yang terlalu panjang dan terlalu pendek tanpa posisi simetris di ruang, yaitu, kesadaran diperlukan jika Anda melakukan rata-rata sederhana (yaitu, tanpa pembobotan) untuk kedua kasus : seluruh titik (hijau) atau simpul poligon cembung (biru).

masukkan deskripsi gambar di sini

Satu aplikasi dapat ditemukan di Menemukan minimum area-persegi panjang untuk poin yang diberikan? .

Pengembang
sumber
Akankah ini berhasil? Menemukan centroid poligon? (StackOverflow)
blah238
3
Saya tidak yakin apa Pertanyaan Anda. Pusat Geometri atau (biasanya centroid) dapat berbeda dari barycenter (pusat massa). Ini adalah fakta yang sudah diketahui. Juga ada berbagai cara untuk menghitung pusat geometri. Lihat: en.wikipedia.org/wiki/Triangle_center , en.wikipedia.org/wiki/Encyclopedia_of_Triangle_Centers & fakultas.evansville.edu/ck6/encyclopedia/ETC.html .
Devdatta Tengshe
1
Re the update: ketika tidak ada topologi, titik cloud hanyalah titik cloud. Sosok Anda dari persegi poligonal tidak berlaku (dan Anda 'massa' dari (0.5,0.4) tampaknya tidak muncul dari rumus standar, dengan cara: simetri berpendapat sangat untuk setiap titik sentral dari alun-alun untuk bertepatan dengan (0,5 , 0,5), tidak peduli bagaimana hal itu didefinisikan). Untuk beberapa gagasan tentang menemukan lokasi representatif atau pusat untuk awan titik dalam dua dimensi dan lebih, silakan lihat stats.stackexchange.com/questions/1927 .
Whuber
1
@Developer, saya melihat poin Anda sekarang, poin ke-5 Anda di bagian bawah "persegi panjang" (sebenarnya sebuah poligon) membuat rata-rata koordinat titik sederhana menghasilkan barycenter yang berbeda dari yang ada pada poligon seperti jawaban whuber menjelaskan.
blah238
1
Aha! Aku benar-benar merindukan simpul kelima itu, meskipun aku telah mencari hal semacam itu. Untuk membantu pembaca di masa mendatang, saya telah sedikit menyunting pertanyaan untuk menunjukkan ini. Ini benar-benar sampai ke inti permasalahan, juga: menyisipkan atau menghapus simpul di sepanjang tepi akan mengubah bagaimana poli {line, gon} diwakili , tetapi seharusnya tidak mengubah perhitungan sifat geometris bawaannya. Itulah mengapa barycenter dari simpul dapat memiliki hubungan yang hampir sewenang-wenang dengan barycenter poligon atau batasnya.
Whuber

Jawaban:

44

Setiap poligon memiliki, setidaknya, empat "pusat" yang berbeda:

  • The barycenter dari simpulnya.

  • Penghalang tepi.

  • Barycenter sebagai poligon.

  • "Pusat" khusus GIS yang berguna untuk pelabelan (biasanya dihitung dengan metode kepemilikan tidak berdokumen).

(Mereka mungkin tidak sengaja bertepatan dalam kasus-kasus khusus, tetapi untuk poligon "generik" mereka adalah poin yang berbeda.)

"Barycenter" secara umum adalah "pusat massa." Tiga jenis berbeda pada di mana massa dianggap berada: itu baik seluruhnya pada simpul, menyebar secara seragam di tepi, atau menyebar secara seragam di seluruh poligon itu sendiri.

Ada metode sederhana untuk menghitung ketiga tukang baring. Salah satu pendekatan bergantung pada fakta dasar bahwa barycenter dari persatuan dua massa yang terpisah adalah rata-rata tertimbang massa rata-rata dari barycenters. Dari sini kita dengan mudah memperoleh yang berikut:

  1. Barycenter dari dua simpul (dengan bobot sama) adalah rata-rata mereka. Ini diperoleh dengan rata-rata koordinat mereka secara terpisah. Secara geometris, ini adalah titik tengah segmen garis yang bergabung dengan dua simpul.

  2. Secara induktif, barycenter dari n (dengan bobot yang sama) diperoleh dengan rata-rata koordinatnya secara terpisah.

  3. Barycenter dari segmen garis adalah titik tengahnya. (Ini jelas dengan simetri.)

  4. Barycenter dari polyline diperoleh dengan menemukan titik tengah dari setiap segmen garis dan kemudian membentuk rata-rata tertimbang mereka menggunakan panjang segmen sebagai bobot.

    Misalnya, perhatikan bentuk "L" yang digambarkan oleh titik (0,0), (6,0), (6,12). Ada dua segmen: satu dengan panjang 6 dengan titik tengah di ((0 + 0) / 2, (0 + 6) / 2) = (3,0) dan yang lain dari panjang 12 dengan titik tengah di ((6 + 6) / 2, (0 + 12) / 2) = (6,6). Koordinat rata-rata tertimbang panjangnya adalah (x, y) dengan

    x = (6*3 + 12*6) / (6+12) = 5,  y = (6*0 + 12*6) / (6+12) = 4.
    

    Ini berbeda dari barycenter dari tiga simpul, yaitu ((0 + 6 + 6) / 3, (0 + 0 + 12) / 3) = (4,4).

    ( Sunting Sebagai contoh lain, perhatikan gambar dalam pertanyaan, yang meskipun berbentuk bujur sangkar, direpresentasikan sebagai pentagon yang ditentukan oleh urutan titik (0,0), (1 / 2,0), (1,0), (1,1), (0,1). Lima sisi memiliki panjang 1/2, 1/2, 1, 1, 1 dan titik tengah (1 / 4,0), (3 / 4,0), (1/2) , 1/2), (1 / 2,1), dan (0,1 / 2), secara berurutan.

    [(1/2)*(1/4, 0) + (1/2)*(3/4, 0) + (1)*(1, 1/2) + (1)*(1/2, 1) + (1)*(0, 1/2)] / (1/2+1/2+1+1+1)
    = (2/4, 2/4) = (0.5, 0.5)
    

    seperti yang diharapkan, meskipun barycenter dari simpul saja (dihitung seperti dalam # 2 di atas) adalah (0,5, 0,4).)

  5. Barycenter dari poligon dapat diperoleh dengan triangulasi untuk menguraikannya menjadi segitiga. Barycenter dari segitiga-qua-poligon bertepatan dengan barycenter dari simpulnya. Rata-rata area-weighted dari barycenters ini adalah barycenter poligon. Area segitiga siap dihitung dalam hal koordinat titiknya (misalnya, dalam hal produk baji dari dua sisi). Untuk ilustrasi perhitungan area seperti itu, termasuk bagaimana mengeksploitasi area yang ditandatangani (positif atau negatif), lihat bagian "Area" di halaman catatan kursus saya (lama) .

    ( Sunting Pertimbangkan poligon yang digambarkan dalam pertanyaan misalnya. Kita dapat melakukan triangulasi dengan segitiga ((0,0), (1 / 2,0), (0,1)) di sebelah kiri, ((0,1), (1 / 2,0), (1,1)) di tengah, dan ((1,1), (1,0), (1 / 2,0)) di sebelah kanan. Wilayah mereka 1/4 Masing-masing, 1/2, 1/4 dan barycenter mereka - diperoleh dengan rata-rata simpul mereka - adalah (1 / 6,1 / 3), (1 / 2,2 / 3), dan (5 / 6,1 / 3) 3), rata-rata area-weighted dari barycenters ini sama dengan

    [(1/4)*(1/6,1/3) + (1/2)*(1/2,2/3) + (1/4)*(5/6,1/3)] / (1/4 + 1/2 + 1/4)
    = (12/24, 6/12)
    = (0.5, 0.5)
    

    sebagaimana mestinya, meskipun ada simpul kelima di sepanjang tepi bawah.)

Jelaslah bahwa masing - masing metode ini efisien : hanya memerlukan satu lintasan melewati representasi "spageti" dari poligon, menggunakan waktu yang cukup (sedikit) pada setiap langkah. Perhatikan bahwa dalam semua kasus kecuali yang pertama (dari simpul murni), diperlukan lebih banyak informasi dari sekadar daftar koordinat titik: Anda juga perlu mengetahui topologi gambar tersebut. Dalam contoh "L", kita perlu tahu bahwa (0,0) terhubung ke (6,0) dan tidak ke (6,12), misalnya.

Ini semua adalah konsep Euclidean. Mereka dapat diperluas ke bola (atau ellipsoid) dengan beberapa cara. Yang langsung melihat fitur sebagai kompleks sederhana dalam tiga (Euclidean) dimensi, menghitung barycenter yang sesuai, dan kemudian memproyeksikannya keluar dari pusat ellipsoid kembali ke permukaan. Ini tidak memerlukan konsep atau formula baru; Anda hanya perlu bekerja dengan koordinat ketiga (z) di samping dua koordinat pertama. (Area masih ditemukan menggunakan panjang produk wedge.)

Generalisasi lain mengakui bahwa metrik Euclidean - akar kuadrat dari jumlah kuadrat, menurut Pythagoras - dapat diubah ke metrik Lp lainnya untuk p> = 1: Anda mengambil akar p dari jumlah kekuatan pth. Menemukan "barycenters" yang tepat tidak lagi begitu sederhana, karena sifat aditif yang indah dieksploitasi di atas (barycenters adalah rata-rata tertimbang dari barycenters dari bagian yang lebih sederhana dari suatu gambar) tidak lagi berlaku secara umum. Seringkali, solusi numerik perkiraan berulang harus diperoleh. Mereka bahkan mungkin tidak unik.

Pusat tambahan dapat didefinisikan untuk berbagai tujuan. Segitiga memiliki banyak pusat berbeda yang dapat menggeneralisasi (agak) ke poligon: pusat lingkaran, pusat (beberapa) lingkaran maksimal, pusat elips pembatas area minimum, dan lainnya. Setiap set dapat ditutup dalam berbagai "lambung," seperti lambung cembung, dan pusat lambung tersebut diperoleh.

Perhatikan bahwa banyak "pusat" ini tidak selalu terletak di bagian dalam poligon. (Namun, setiap pusat yang masuk akal dari poligon cembung akan terletak di dalam interiornya.)

Keragaman pendekatan dan solusi ini mengindikasikan bahwa seseorang harus mewaspadai istilah generik seperti "pusat geometri" atau sekadar "pusat": bisa saja tentang apa saja.

whuber
sumber
Kepada komunitas: Jawaban yang bagus seperti ini dari 'whuber' dapat diharapkan hanya untuk pertanyaan yang bagus, karena keakraban saya dengan pilihannya, dengan demikian, akankah kalian semua keberatan untuk memilih-up pertanyaan itu juga jika Anda menganggapnya menarik;)
Pengembang
Saya menemukan itu berguna dalam beberapa hal, ingin memberikan sesuatu kepada kontiruter lain sebagai motivasi untuk menjawab. Saya menandai ini namun jawaban konstruktif yang dapat diterima sejauh ini.
Pengembang
Bisakah Anda jelaskan mengapa area masih ditemukan menggunakan produk wedge di bola? Bukankah area segitiga berbentuk bola lebih cocok? Referensi terdekat (selain dari jawaban yang luar biasa ini!) Yang saya temukan adalah: jennessent.com/downloads/Graphics_Shapes_Online.pdf - yang menggunakan bidang segitiga bundar.
Jason Davies
@ Alasan saya tertarik: bagaimana Anda mengusulkan menggunakan area segitiga bola untuk menghitung barycenters fitur bola?
whuber
@whuber Poligon bulat didekomposisi menjadi segitiga bulat, dan pusat barik dari setiap segitiga dihitung dengan rata-rata koordinat Cartesian dari simpul-simpulnya. Saya mengusulkan bahwa barycenter poligon adalah rata-rata tertimbang dari segitiga ini, di mana beratnya adalah area segitiga bola , bukan area planar seperti yang Anda sarankan dalam jawaban Anda (dengan asumsi saya memahami produk irisan dengan benar).
Jason Davies