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

看板Programming作者yoco315 (眠月)時間16年前 (2009/10/09 22:57)推噓7(7推 0噓 8→)

留言15則, 7人參與討論串3/3 (看更多)

※ 引述《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

10/10 01:27, , 1^F

10/10 01:27, 1^F

推

Fenikso

10/10 03:25, , 2^F

10/10 03:25, 2^F

推

LPH66

10/10 05:54, , 3^F

10/10 05:54, 3^F