Menghitung centroid poligon bulat

11

Saya ingin cara umum untuk menghitung centroid untuk poligon pada sebuah bola.

Sejauh ini, referensi online terbaik adalah:

Alat untuk Grafik dan Bentuk oleh Jeff Jenness.

Metode yang dijelaskan di sana menyarankan penguraian poligon menjadi beberapa segitiga bola, dan menghitung rata-rata centroid segitiga bola, yang dibobot oleh area segitiga bola.

Saya tahu bahwa ada beberapa cara untuk mendefinisikan centroid poligon bulat, tetapi saya mencari sesuatu yang analog dengan definisi titik dan polyline berikut:

  • Poin : rata-rata aritmatika vektor Cartesian yang mewakili poin.
  • Polylines : rata-rata tertimbang vektor Cartesian yang mewakili titik tengah dari setiap segmen garis, ditimbang oleh panjang (bola) masing-masing segmen.

Tampaknya kelanjutan yang masuk akal untuk memiliki poligon centroid didefinisikan sebagai rata-rata tertimbang dari dekomposisi segitiga, ditimbang berdasarkan luas.

Pertanyaan saya adalah apakah metode dalam referensi di atas akan berfungsi terlepas dari dekomposisi segitiga yang digunakan. Secara khusus, ia menyebutkan membusuk menjadi segitiga relatif ke titik arbitrer, bahkan di luar poligon, sehingga beberapa segitiga akan memiliki area negatif yang berkontribusi bobot negatif.

Terkait: Bagaimana menemukan pusat geometri suatu objek?

Jason Davies
sumber

Jawaban:

9

Itu tidak akan bekerja secara konsisten bahkan ketika Anda melakukan semua triangulasi relatif terhadap satu, titik tetap . Masalahnya adalah bahwa perhitungan bola dan Euclidean sedang dicampur tanpa mempertimbangkan apa artinya.

Salah satu cara untuk membuat ini jelas adalah dengan mempertimbangkan segitiga yang agak ekstrem, seperti hampir setengah dari belahan bumi. Misalnya, mulai dari (lon, lat) = (-179, 0), jalankan di sepanjang khatulistiwa ke (0, 0), lalu naik ke kutub utara di (0, 90), lalu kembali ke awal di (- 179, 0). Ini adalah segitiga 90-179-90 yang terdiri dari sebagian besar belahan utara belahan bumi barat. Masalahnya adalah bahwa titik akhir (ditampilkan sebagai titik-titik putih pada gambar) praktis terletak di pesawat: satu di kutub dan dua lainnya hampir berseberangan. Jadi rata-rata mereka, diproyeksikan kembali ke bola (titik merah), hampir di kutub - tapi itu sejauh dari pusat yang masuk akal yang bisa didapat:

Segitiga bola besar

Sebagai contoh lain, mari kita lakukan triangulasi sebuah poligon yang mewakili belahan bumi relatif terhadap pusatnya, Kutub Utara. Kami akan selalu membagi belahan bumi Barat menjadi dua bagian yang sama, masing-masing segitiga 90-90-90 (sehingga menghindari masalah dengan segitiga besar yang membentang di belahan bumi). Belahan bumi Timur, bagaimanapun, akan dibagi menjadi n semi-sama adil. Vertikal lune k ( k = 1, 2, ..., n ) memiliki koordinat (lon, lat)

((k-1) * 180/n, 0),  (k * 180/n, 0),  (k * 180/n, 90).

Nasi untuk k = 8

Gambar ini menunjukkan pengaturan untuk k = 8. Titik-titik merah adalah "pusat" segitiga individu yang dihitung berdasarkan dokumen "Alat untuk Grafik dan Bentuk", hal 65-67.

Melakukan perhitungan, saya menemukan bahwa dengan k = 2, pusat area-tertimbang memang di Kutub Utara (seperti yang akan ditunjukkan oleh pertimbangan simetri), tetapi ketika n bertambah, hasilnya dengan cepat bergeser ke belahan bumi Barat dan, di batas, mendekati garis lintang 89,556 derajat di sepanjang garis bujur -90 derajat. Ini adalah sekitar 50 kilometer selatan Kutub Utara itu sendiri.

Harus diakui, kesalahan +/- 50 kilometer untuk poligon yang mencakup 20.000 kilometer kecil; jumlah total variasi sewenang - wenang karena triangulasi yang berbeda dalam kasus ini hanya 0,5%. Jelas kesalahan relatif dapat dibuat besar secara sewenang-wenang dengan memasukkan segitiga negatif (cukup tambahkan dan kurangi beberapa segitiga sangat besar relatif terhadap segitiga kecil). Terlepas dari itu, siapa pun yang berupaya melakukan perhitungan bola ternyata mencoba menghindari kesalahan proyeksi, sehingga mereka mencari akurasi tinggi. Metode triangulasi ini tidak dapat direkomendasikan.

whuber
sumber
Anda telah menunjukkan bahwa kesalahan dapat terakumulasi untuk n besar, tetapi tidak jelas bahwa pendekatan tersebut cacat. Nilai n apa yang Anda gunakan untuk mencapai nilai pembatas?
Jason Davies
Juga, terima kasih banyak untuk melakukan perhitungan dan melihat ini secara mendalam. Saya hanya ingin sedikit klarifikasi sebelum saya bisa menyelesaikan masalahnya. :)
Jason Davies
Jason, saya menambahkan contoh pendahuluan untuk memberi Anda beberapa intuisi. Batas itu sendiri dengan cepat didekati; beberapa lusin akan memberi Anda beberapa digit signifikan. Tetapi contoh baru harus meletakkan keraguan yang tersisa bahwa triangulasi tertimbang ini melakukan sesuatu yang masuk akal - kecuali untuk segitiga kecil, di mana Anda jauh lebih baik melakukan perhitungan dalam koordinat yang diproyeksikan di tempat pertama. Satu-satunya alasan untuk melakukan perhitungan bola adalah ketika area analisis Anda benar-benar global, karena semua proyeksi menghasilkan banyak distorsi.
whuber
1
Fantastis, terima kasih. Jadi jika saya mengerti dengan benar, hanya rata-rata vektor Cartesian tidak menghasilkan centroid yang masuk akal untuk segitiga bulat (terutama yang besar seperti contoh pertama Anda). Saya akan menyelidiki metode yang lebih baik misalnya menemukan persimpangan median lingkaran besar.
Jason Davies
BTW, saya masih berharap bahwa pusat massa bidang-tertimbang mirip dengan di atas akan bekerja. Bayangkan setiap poligon diberi volume 3D dengan menambahkan titik di asal bola itu. Kemudian gantung bola dengan tali yang tidak terlihat yang terhubung ke asalnya dan temukan keseimbangan yang stabil. Centroid adalah titik paling bawah (ini adalah proyeksi pusat massa ke permukaan bola). Ini harus bekerja selain dari beberapa kasus ambigu misalnya strip di sekitar khatulistiwa, di mana saya bisa memilih titik yang masuk akal. Senang berdiskusi dalam pertanyaan baru jika Anda pikir itu sepadan.
Jason Davies
3

Merupakan ide yang baik untuk menyebutkan sifat-sifat yang seharusnya dimiliki oleh sentroid poligon. Inilah kriteria saya:

(A) Ini adalah properti dari interior poligon (bukan simpul atau tepi). Dengan demikian, membelah tepi menjadi dua dengan memasukkan simpul tambahan seharusnya tidak mengubah posisi centroid. Perhatikan bahwa definisi Jenness tentang centroid gagal pada kriteria ini, karena posisi centroid akan bergantung pada bagaimana poligon dibagi menjadi segitiga.

(B) Perturbing bentuk poligon sedikit harus memindahkan centroid sedikit. Di sini perlu untuk memaksakan batasan pada keseluruhan poligon (misalnya, ke belahan bumi tunggal). Tanpa pembatasan ini, mudah untuk membuat kasus-kasus di mana centroid akan tiba-tiba berayun ke sisi yang berlawanan dari bumi dengan sedikit gerakan titik. Kondisi ini tidak termasuk metode yang mengharuskan pusat massa berada di dalam poligon.

(c) Ia harus direduksi menjadi definisi datar centroid untuk poligon kecil.

Berikut adalah dua pendekatan yang memenuhi kriteria ini:

(1) Hitung centroid untuk poligon ellipsoidal dalam tiga dimensi dan proyeksikan kembali ke permukaan ellipsoid (sepanjang normal ke ellipsoid). Keuntungan besar: centroid dapat dihitung dengan memecah poligon menjadi bentuk yang lebih sederhana.

(2) Centroid adalah titik dengan jarak geodesik RMS minimum ke semua titik di bagian dalam poligon. Lihat Buss dan Fillmore, "Rata-Rata Bulat dan Aplikasi untuk Splines Bulat dan Interpolasi", Transaksi ACM pada Grafik 20 , 95-126 (2001). Keuntungan besar: titik yang dihasilkan tidak tergantung pada bagaimana permukaan tertanam dalam R 3 .

Sayangnya, tidak satu pun dari definisi ini yang mudah untuk dipraktikkan. Namun , metode pertama dapat dilakukan hanya untuk bola. Area "dasar" terbaik untuk digunakan adalah segi empat yang dibatasi oleh tepi poligon, dua meridian melalui titik-ujung tepi, dan khatulistiwa. Hasil untuk keseluruhan poligon mencakup penjumlahan kontribusi di tepinya. (Langkah-langkah tambahan perlu diambil jika poligon mengelilingi sebuah kutub.)

Misalkan titik akhir dari tepi adalah (φ 1 , λ 1 ) dan (φ 2 , λ 2 ). Biarkan azimut tepi dan titik akhir dengan α 1 dan α 2 . Dengan asumsi jari-jari bola adalah 1, luas segiempat adalah

  A = α 2 - α 1
      = 2 tan −1 [tan ½ (λ 2 - λ 1 ) dosa ½ (φ 2 + φ 1 ) / cos ½ (φ 2 + φ 1 )]

(Rumus ini untuk daerah, karena Bessel, secara substansial berperilaku lebih baik daripada rumus L'Huilier yang umum digunakan untuk luas segitiga.)

Komponen centroid untuk segi empat ini diberikan oleh

  2 Ax ⟩ = φ 2 sin (λ 2 - λ 0 ) - φ 1 sin (λ 1 - λ 0 )
  2 Ay ⟩ = cos α 02 - σ 1 ) - (φ 2 cos (λ 2 - λ 0 ) - φ 1 cos (λ 1 - λ 0 ))
  2 Az ⟩ = (λ 2 - λ 1 ) - sin α 02 - σ1 )

di mana σ 2 - σ 1 adalah panjang dari tepi, dan λ 0 dan α 0 adalah bujur dan azimuth dari tepi di mana ia melintasi garis khatulistiwa, dan sumbu x dan y diorientasikan sehingga persimpangan khatulistiwa berada di x = 1, y = 0. ( z adalah poros melalui kutub, tentu saja.)

cffk
sumber
Bisakah Anda menjelaskan mengapa posisi centroid Jenness akan bergantung pada bagaimana poligon dibagi menjadi segitiga? Saya tahu dari contoh @ whuber bahwa perhitungan centroid Jenness salah untuk segitiga bola, tetapi bagaimana jika centroid berdasarkan median segitiga bola digunakan sebagai gantinya? Apakah ini masih gagal?
Jason Davies
Jenness secara efektif menggantikan poligon bulat dengan seperangkat segitiga planar dan menghitung centroid mereka. Jelas (?), Hasilnya akan tergantung pada partisi. Melakukan perhitungan yang saya uraikan menggunakan centroid segitiga bulat baik-baik saja. Anda dapat menemukan rumus untuk centroid di JE Brock, The Inersia Tensor untuk Segitiga Bulat, J. Applied Mechanics 42, 239 (1975) dx.doi.org/10.1115/1.3423535
cffk
Aku melihat kertas Brock lagi. Rumusnya untuk pusat massa segitiga berbentuk bola melibatkan jumlah di atas tepi segitiga. Oleh karena itu dapat digeneralisasi secara sepele untuk diterapkan pada poligon (tanpa perlu memecahnya menjadi segitiga).
cffk
Apakah Anda keberatan memberikan referensi untuk perhitungan area karena Bessel juga? Sepertinya saya tidak dapat menemukannya di mana pun, dan saya tertarik untuk menulis rutin area poligon bulat cepat (dan akurat). Terima kasih!
Jason Davies
Saya menemukannya, dan menyadari bahwa Anda menerjemahkannya ke bahasa Inggris, jadi terima kasih. :)
Jason Davies