算法08計算幾何基礎(chǔ)

ACM程序設(shè)計杭州電子科技大學(xué)劉春英

2023/4/62周末月賽，你嗎？報名了2023/4/63每周一星（7）：nikoseven2023/4/64第八講計算幾何初步(ComputationalGeometryBasic)2023/4/65第一單元線段屬性2023/4/662023/4/672023/4/682023/4/692023/4/6102023/4/6112023/4/6122023/4/6132023/4/614思考：1、傳統(tǒng)的計算線段相交的方法是什么？2、傳統(tǒng)方法和本方法的區(qū)別是什么？2023/4/615特別提醒：以上介紹的線段的三個屬性，是計算幾何的基礎(chǔ)，在很多方面都有應(yīng)用，比如求凸包等等，請務(wù)必掌握！2023/4/616第二單元多邊形面積和重心2023/4/617基本問題（1）：給定一個簡單多邊形，求其面積。輸入：多邊形（頂點按逆時針順序排列）輸出：面積S2023/4/618思考如下圖形：2023/4/619Anygoodidea?2023/4/620先看最簡單的多邊形——三角形2023/4/621三角形的面積：在解析幾何里，△ABC的面積可以通過如下方法求得：點坐標(biāo)=>邊長=>海倫公式=>面積2023/4/622思考：此方法的缺點：計算量大精度損失更好的方法？2023/4/623計算幾何的方法：在計算幾何里，我們知道，△ABC的面積就是“向量AB”和“向量AC”兩個向量叉積的絕對值的一半。其正負(fù)表示三角形頂點是在右手系還是左手系。ABC成左手系，負(fù)面積ABC成右手系，正面積BCACBA2023/4/624大功告成：

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

=∣

∣/2特別注意：以上得到是有向面積（有正負(fù)）！Xb–XaYb–YaXc–XaYc–Ya2023/4/625凸多邊形的三角形剖分很自然地，我們會想到以P1為扇面中心，連接P1Pi就得到N-2個三角形，由于凸性，保證這些三角形全在多邊形內(nèi)，那么，這個凸多邊形的有向面積：A=sigma(Ai)(i=1…N-2)P1P2P3P4P5P6A1A2A3A42023/4/626凹多邊形的面積？P1P4P3P22023/4/627依然成立！??！多邊形面積公式：A=sigma(Ai)(i=1…N-2)結(jié)論：“有向面積”A比“面積”S其實更本質(zhì)！2023/4/628任意點為扇心的三角形剖分：我們能把多邊形分成N-2個三角形，為什么不能分成N個三角形呢？比如，以多邊形內(nèi)部的一個點為扇心，就可以把多邊形剖分成N個三角形。P0P1P2P6P5P4P32023/4/629前面的三角剖分顯然對于多邊形內(nèi)部任意一點都是合適的！我們可以得到：A=sigma(Ai)（i=1…N）即：A=sigma∣

∣/2（i=1…N）Xi–X0Yi–Y0X(i+1)–X0Y(i+1)–Y02023/4/630能否把扇心移到多邊形以外呢？P0P1P2P3P42023/4/631既然內(nèi)外都可以，為什么不設(shè)P0為坐標(biāo)原點呢？OP1P2P3P4現(xiàn)在的公式？2023/4/632簡化的公式：A=sigma∣

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

(O+↑Pi+↑Pi+1)/3C=sigma((↑Pi+↑Pi+1)(↑Pi×↑Pi+1))/(6A)全部搞定！2023/4/640第三單元凸包(ConvexHull)2023/4/6412023/4/6422023/4/6432023/4/6442023/4/6452023/4/6462023/4/6472023/4/6482023/4/6492023/4/6502023/4/6512023/4/6522023/4/6532023/4/6542023/4/6552023/4/6562023/4/6572023/4/6582023/4/6592023/4/6602023/4/6612023/4/6622023/4/6632023/4/664