Re: [問題] 不規則區域的重心

[yoco315 (眠月)]

※ 引述《makiyolove (暴力熊)》之銘言：
: 各位版友好：
: 在一起)。現在我想要在這個不規則圖形上找重心，但是找

google 了一下看到這個..
http://www.exaflop.org/docs/cgafaq/cga2.html

我還看完了，順便幫你整理出重點：

        一整個多邊形的重心好似很難算，
        但是一個三角形的重心很好算，
        兩個三角形的重心也很好算，三個三角型的重心也很好算，
        四個也很好算…五個也…六個也…七個也…八格也路…

        原來如此！我們只要把多邊形三角化以後，
        求所有三角形的重心的重心就好了！
        報告完畢。

我人真好 QQ

--
Subject 2.02: How can the centroid of a polygon be computed?

The centroid (a.k.a. the center of mass, or center of gravity) of a polygon
can be computed as the weighted sum of the centroids of a partition of the
polygon into triangles. The centroid of a triangle is simply the average of
its three vertices, i.e., it has coordinates (x1 + x2 + x3)/3 and (y1 + y2 +
y3)/3. This suggests first triangulating the polygon, then forming a sum of
the centroids of each triangle, weighted by the area of each triangle, the
whole sum normalized by the total polygon area. This indeed works, but there
is a simpler method: the triangulation need not be a partition, but rather
can use positively and negatively oriented triangles (with positive and
negative areas), as is used when computing the area of a polygon. This leads
to a very simple algorithm for computing the centroid, based on a sum of
triangle centroids weighted with their signed area. The triangles can be
taken to be those formed by one fixed vertex v0 of the polygon, and the two
endpoints of consecutive edges of the polygon: (v1,v2), (v2,v3), etc. The
area of a triangle with vertices a, b, c is half of this expression:
(b[X] - a[X]) * (c[Y] - a[Y]) -
(c[X] - a[X]) * (b[Y] - a[Y]);

Code available at ftp://grendel.csc.smith.edu/pub/code/centroid.c (3K).
Reference: [Gems IV] pp.3-6; also includes code.

--
To iterate is human, to recurse, divine.
遞迴只應天上有, 凡人該當用迴圈.              　   L. Peter Deutsch

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 118.160.107.24
推 tropical72:我沒試過，不過有人說誤差蠻大的
推 Fenikso:這方法是準的哪會有誤差...
推 LPH66:數值(浮點數)誤差吧...
推 Fenikso:可是整個演算法就一次整數除法
→ Fenikso:其他都是整數的加減乘..
→ Fenikso:如果允許有理數運算的話完全是準的
→ Fenikso:就算用double也不會差多少
→ yoco315:我有問題（舉手）  關於誤差大的說明
→ yoco315:有沒有更詳細的資料？或是推薦較準的方法?
推 AmosYang:八格也路 XD
推 denny61001:大家都好強喔>///<  我什麼都看不懂
推 LouisXIV:我是不知道應該要多準才行，不過既然是
→ LouisXIV:影像處理的話，其實把pixel坐標平均一
→ LouisXIV:下就可以得到答案了！誤差應該在一個
→ LouisXIV:pixel以內，感覺上已經可以接受了！