輸入多邊形頂點(diǎn)按逆時(shí)針順序排列課件

2023/9/51多邊形面積和重心2023/8/31多邊形面積和重心2023/9/52基本問題（1）：給定一個(gè)簡(jiǎn)單多邊形，求其面積。輸入：多邊形（頂點(diǎn)按逆時(shí)針順序排列）輸出：面積S2023/8/32基本問題（1）：給定一個(gè)簡(jiǎn)單多邊形，求其面2023/9/53思考如下圖形：2023/8/33思考如下圖形：2023/9/54先看最簡(jiǎn)單的多邊形——三角形2023/8/34先看最簡(jiǎn)單的多邊形——三角形2023/9/55計(jì)算幾何的方法：在計(jì)算幾何里，我們知道，△ABC的面積就是“向量AB”和“向量AC”兩個(gè)向量叉積的絕對(duì)值的一半。其正負(fù)表示三角形頂點(diǎn)是在右手系還是左手系。ABC成左手系，負(fù)面積ABC成右手系，正面積BCACBA2023/8/35計(jì)算幾何的方法：在計(jì)算幾何里，我們知道，△2023/9/56大功告成：

Area(A,B,C)=1/2*(↑AB)×(↑AC)

=∣

∣/2特別注意：以上得到是有向面積（有正負(fù)）！Xb–XaYb–YaXc–XaYc–Ya2023/8/36大功告成： Area(A,B,C)=1/2023/9/57凸多邊形的三角形剖分很自然地，我們會(huì)想到以P1為扇面中心，連接P1Pi就得到N-2個(gè)三角形，由于凸性，保證這些三角形全在多邊形內(nèi)，那么，這個(gè)凸多邊形的有向面積：A=sigma(Ai)(i=1…N-2)P1P2P3P4P5P6A1A2A3A42023/8/37凸多邊形的三角形剖分很自然地，我們會(huì)想到以2023/9/58凹多邊形的面積？P1P4P3P22023/8/38凹多邊形的面積？P1P4P3P22023/9/59多邊形面積公式：A=sigma(Ai)(i=1…N-2)結(jié)論：“有向面積”A比“面積”S其實(shí)更本質(zhì)！2023/8/39多邊形面積公式：A=sigma(Ai)2023/9/510任意點(diǎn)為扇心的三角形剖分：我們能把多邊形分成N-2個(gè)三角形，為什么不能分成N個(gè)三角形呢？比如，以多邊形內(nèi)部的一個(gè)點(diǎn)為扇心，就可以把多邊形剖分成N個(gè)三角形。P0P1P2P6P5P4P32023/8/310任意點(diǎn)為扇心的三角形剖分：我們能把多邊形2023/9/511前面的三角剖分顯然對(duì)于多邊形內(nèi)部任意一點(diǎn)都是合適的！我們可以得到：A=sigma(Ai)（i=1…N）即：A=sigma∣

∣/2（i=1…N）Xi–X0Yi–Y0X(i+1)–X0Y(i+1)–Y02023/8/311前面的三角剖分顯然對(duì)于多邊形內(nèi)部任意一點(diǎn)2023/9/512能否把扇心移到多邊形以外呢？P0P1P2P3P42023/8/312能否把扇心移到多邊形以外呢？P0P1P22023/9/513既然內(nèi)外都可以，為什么不設(shè)P0為坐標(biāo)原點(diǎn)呢？OP1P2P3P4現(xiàn)在的公式？2023/8/313既然內(nèi)外都可以，為什么不設(shè)P0為坐標(biāo)原點(diǎn)2023/9/514簡(jiǎn)化的公式：A=sigma∣

∣/2（i=1…N）XiYiX(i+1)Y(i+1)面積問題搞定！2023/8/314簡(jiǎn)化的公式：A=sigma∣∣/2023/9/515基本問題（2）：給定一個(gè)簡(jiǎn)單多邊形，求其重心。輸入：多邊形（頂點(diǎn)按逆時(shí)針順序排列）輸出：重心點(diǎn)C2023/8/315基本問題（2）：給定一個(gè)簡(jiǎn)單多邊形，求其2023/9/516從三角形的重心談起：三角形的重心是：(x1+x2+x3)/3，(y1+y2+y3)/3可以推廣否？Sigma(xi)/N,sigma(yi)/N(i=1…N)???2023/8/316從三角形的重心談起：三角形的重心是：可以2023/9/517看看一個(gè)特例：.2023/8/317看看一個(gè)特例：.2023/9/518原因：錯(cuò)誤的推廣公式是“質(zhì)點(diǎn)系重心公式”，即如果認(rèn)為多邊形的質(zhì)量?jī)H分布在其頂點(diǎn)上，且均勻分布，則這個(gè)公式是對(duì)的。但是，現(xiàn)在多邊形的質(zhì)量是均勻分布在其內(nèi)部區(qū)域上的，也就是說，是與面積有關(guān)的！2023/8/318原因：錯(cuò)誤的推廣公式是“質(zhì)點(diǎn)系重心公式”2023/9/519Solution:剖分成N個(gè)三角形，分別求出其重心和面積，這時(shí)可以想象，原來質(zhì)量均勻分布在內(nèi)部區(qū)域上，而現(xiàn)在質(zhì)量?jī)H僅分布在這N個(gè)重心點(diǎn)上（等假變換），這時(shí)候就可以利用剛才的質(zhì)點(diǎn)系重心公式了。不過，要稍微改一改，改成加權(quán)平均數(shù)，因?yàn)橘|(zhì)量不是均勻分布的，每個(gè)質(zhì)點(diǎn)代表其所在三角形，其質(zhì)量就是該三角形的面積（有向面積！），——這就是權(quán)！2023/8/319Solution:剖分成N個(gè)三角形，分別2023/9/520公式：C=sigma(Ai*Ci)/A(i=1…N)Ci=Centroid(△OPi