資源描述:
《acm算法 計算幾何基礎》由會員上傳分享,免費在線閱讀,更多相關內容在教育資源-天天文庫。
1、ACM程序設計計算機學院劉春英9/25/20211今天,你了嗎?AC9/25/20212每周一星(6):老菜(donhau)9/25/20213第七講計算幾何初步(ComputationalGeometryBasic)9/25/20214第一單元線段屬性9/25/202159/25/202169/25/202179/25/202189/25/202199/25/2021109/25/2021119/25/2021129/25/202113思考:1、傳統(tǒng)的計算線段相交的方法是什么?2、傳統(tǒng)方法和本方
2、法的區(qū)別是什么?9/25/202114特別提醒:以上介紹的線段的三個屬性,是計算幾何的基礎,在很多方面都有應用,比如求凸包等等,請務必掌握!9/25/202115第二單元多邊形面積和重心9/25/202116基本問題(1):給定一個簡單多邊形,求其面積。輸入:多邊形(頂點按逆時針順序排列)輸出:面積S9/25/202117思考如下圖形:9/25/202118Anygoodidea?9/25/202119先討論最簡單的多邊形——三角形9/25/202120三角形的面積:在解析幾何里,△ABC的面積可
3、以通過如下方法求得:點坐標=>邊長=>海倫公式=>面積9/25/202121思考:此方法的缺點:計算量大精度損失更好的方法?9/25/202122計算幾何的方法:在計算幾何里,我們知道,△ABC的面積就是“向量AB”和“向量AC”兩個向量叉積的絕對值的一半。其正負表示三角形頂點是在右手系還是左手系。ABC成左手系,負面積ABC成右手系,正面積BCACBA9/25/202123大功告成:Area(A,B,C)=1/2*(↑AB)×(↑AC)=∣∣/2特別注意:以上得到是有向面積(有正負)!Xb–Xa
4、Yb–YaXc–XaYc–Ya9/25/202124凸多邊形的三角形剖分很自然地,我們會想到以P1為扇面中心,連接P1Pi就得到N-2個三角形,由于凸性,保證這些三角形全在多邊形內,那么,這個凸多邊形的有向面積:A=sigma(Ai)(i=1…N-2)P1P2P3P4P5P6A1A2A3A49/25/202125凹多邊形的面積?P1P4P3P29/25/202126依然成立?。?!多邊形面積公式:A=sigma(Ai)(i=1…N-2)結論:“有向面積”A比“面積”S其實更本質!9/25/20212
5、7任意點為扇心的三角形剖分:我們能把多邊形分成N-2個三角形,為什么不能分成N個三角形呢?比如,以多邊形內部的一個點為扇心,就可以把多邊形剖分成N個三角形。P0P1P2P6P5P4P39/25/202128前面的三角剖分顯然對于多邊形內部任意一點都是合適的!我們可以得到:A=sigma(Ai)(i=1…N)即:A=sigma∣∣/2(i=1…N)Xi–X0Yi–Y0X(i+1)–X0Y(i+1)–Y09/25/202129能不能把扇心移到多邊形以外呢?P0P1P2P3P49/25/202130既然
6、內外都可以,為什么不設P0為坐標原點呢?OP1P2P3P4現(xiàn)在的公式?9/25/202131簡化的公式:A=sigma∣∣/2(i=1…N)XiYiX(i+1)Y(i+1)面積問題搞定!9/25/202132基本問題(2):給定一個簡單多邊形,求其重心。輸入:多邊形(頂點按逆時針順序排列)輸出:重心點C9/25/202133從三角形的重心談起:三角形的重心是:(x1+x2+x3)/3,(y1+y2+y3)/3可以推廣否?Sigma(xi)/N,sigma(yi)/N(i=1…N)???9/25/2
7、02134看看一個特例:.9/25/202135原因:錯誤的推廣公式是“質點系重心公式”,即如果認為多邊形的質量僅分布在其頂點上,且均勻分布,則這個公式是對的。但是,現(xiàn)在多邊形的質量是均勻分布在其內部區(qū)域上的,也就是說,是與面積有關的!9/25/202136Solution:剖分成N個三角形,分別求出其重心和面積,這時可以想象,原來質量均勻分布在內部區(qū)域上,而現(xiàn)在質量僅僅分布在這N個重心點上(等假變換),這時候就可以利用剛才的質點系重心公式了。不過,要稍微改一改,改成加權平均數(shù),因為質量不是均勻分
8、布的,每個質點代表其所在三角形,其質量就是該三角形的面積(有向面積!),——這就是權!9/25/202137公式:C=sigma(Ai*Ci)/A(i=1…N)Ci=Centroid(△OPiPi+1)=(O+↑Pi+↑Pi+1)C=sigma((↑Pi+↑Pi+1)(↑Pi×↑Pi+1))/(6A)9/25/202138全部搞定!9/25/202139第三單元凸包(ConvexHull)9/25/2021409/25/2021419/25/2021429/25/2021439/2