ACMlecture-05計算幾何基礎(chǔ)課件

2023/11/271今天，你了嗎？AC第1頁/共71頁2023/11/272每周一星（4）：07053410陳晟

第2頁/共71頁2023/11/273第五講計算幾何初步(ComputationalGeometryBasic)第3頁/共71頁2023/11/274第一單元線段屬性第4頁/共71頁2023/11/275第5頁/共71頁2023/11/276第6頁/共71頁2023/11/277第7頁/共71頁2023/11/278第8頁/共71頁2023/11/279第9頁/共71頁2023/11/2710第10頁/共71頁2023/11/2711第11頁/共71頁2023/11/2712第12頁/共71頁2023/11/2713思考：1、傳統(tǒng)的計算線段相交的方法是什么？2、傳統(tǒng)方法和本方法的區(qū)別是什么？第13頁/共71頁2023/11/2714特別提醒：以上介紹的線段的三個屬性，是計算幾何的基礎(chǔ)，在很多方面都有應(yīng)用，比如求凸包等等，請務(wù)必掌握！第14頁/共71頁2023/11/2715第二單元多邊形面積和重心第15頁/共71頁2023/11/2716基本問題（1）：給定一個簡單多邊形，求其面積。輸入：多邊形（頂點(diǎn)按逆時針順序排列）輸出：面積S第16頁/共71頁2023/11/2717思考如下圖形：第17頁/共71頁2023/11/2718Anygoodidea?第18頁/共71頁2023/11/2719先看最簡單的多邊形——三角形第19頁/共71頁2023/11/2720三角形的面積：在解析幾何里，△ABC的面積可以通過如下方法求得：點(diǎn)坐標(biāo)=>邊長=>海倫公式=>面積第20頁/共71頁2023/11/2721思考：此方法的缺點(diǎn)：計算量大精度損失更好的方法？第21頁/共71頁2023/11/2722計算幾何的方法：在計算幾何里，我們知道，△ABC的面積就是“向量AB”和“向量AC”兩個向量叉積的絕對值的一半。其正負(fù)表示三角形頂點(diǎn)是在右手系還是左手系。ABC成左手系，負(fù)面積ABC成右手系，正面積BCACBA第22頁/共71頁2023/11/2723大功告成：

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

=∣

∣/2特別注意：以上得到是有向面積（有正負(fù)）！Xb–XaYb–YaXc–XaYc–Ya第23頁/共71頁2023/11/2724凸多邊形的三角形剖分很自然地，我們會想到以P1為扇面中心，連接P1Pi就得到N-2個三角形，由于凸性，保證這些三角形全在多邊形內(nèi)，那么，這個凸多邊形的有向面積：

A=sigma(Ai)(i=1…N-2)P1P2P3P4P5P6A1A2A3A4第24頁/共71頁2023/11/2725凹多邊形的面積？P1P4P3P2第25頁/共71頁2023/11/2726依然成立?。?！多邊形面積公式：A=sigma(Ai)(i=1…N-2)結(jié)論：“有向面積”A比“面積”S其實更本質(zhì)！第26頁/共71頁2023/11/2727任意點(diǎn)為扇心的三角形剖分：我們能把多邊形分成N-2個三角形，為什么不能分成N個三角形呢？比如，以多邊形內(nèi)部的一個點(diǎn)為扇心，就可以把多邊形剖分成N個三角形。P0P1P2P6P5P4P3第27頁/共71頁2023/11/2728前面的三角剖分顯然對于多邊形內(nèi)部任意一點(diǎn)都是合適的！我們可以得到：A=sigma(Ai)（i=1…N

）即：A=sigma∣

∣/2

（i=1…N

）Xi–X0Yi–Y0X(i+1)–X0Y(i+1)–Y0第28頁/共71頁2023/11/2729能否把扇心移到多邊形以外呢？P0P1P2P3P4第29頁/共71頁2023/11/2730既然內(nèi)外都可以，為什么不設(shè)P0為坐標(biāo)原點(diǎn)呢？OP1P2P3P4現(xiàn)在的公式？第30頁/共71頁2023/11/2731簡化的公式：A=sigma∣

∣/2（i=1…N

）XiYiX(i+1)Y(i+1)面積問題搞定！第31頁/共71頁2023/11/2732基本問題（2）：給定一個簡單多邊形，求其重心。輸入：多邊形（頂點(diǎn)按逆時針順序排列）輸出：重心點(diǎn)C第32頁/共71頁2023/11/2733從三角形的重心談起：三角形的重心是：

(x1+x2+x3)/3，(y1+y2+y3)/3可以推廣否？Sigma(xi)/N,sigma(yi)/N(i=1…N)???第33頁/共71頁2023/11/2734看看一個特例：.第34頁/共71頁2023/11/2735原因：錯誤的推廣公式是“質(zhì)點(diǎn)系重心公式”，即如果認(rèn)為多邊形的質(zhì)量僅分布在其頂點(diǎn)上，且均勻分布，則這個公式是對的。但是，現(xiàn)在多邊形的質(zhì)量是均勻分布在其內(nèi)部區(qū)域上的，也就是說，是與面積有關(guān)的！第35頁/共71頁2023/11/2736Solution:剖分成N個三角形，分別求出其重心和面積，這時可以想象，原來質(zhì)量均勻分布在內(nèi)部區(qū)域上，而現(xiàn)在質(zhì)量僅僅分布在這N個重心點(diǎn)上（等假變換），這時候就可以利用剛才的質(zhì)點(diǎn)系重心公式了。不過，要稍微改一改，改成加權(quán)平均數(shù)，因為質(zhì)量不是均勻分布的，每個質(zhì)點(diǎn)代表其所在三角形，其質(zhì)量就是該三角形的面積（有向面積！），——這就是權(quán)！第36頁/共71頁2023/11/2737公式：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)第37頁/共71頁全部搞定！第38頁/共71頁2023/11/2739第三單元凸包(ConvexHull)第39頁/共71頁2023/11/2740第40頁/共71頁2023/11/2741第41頁/共71頁2023/11/2742第42頁/共71頁2023/11/2743第43頁/共71頁2023/11/2744第44頁/共71頁2023/11/2745第45頁/共71頁2023/11/2746第46頁/共71頁2023/11/2747第47頁/共71頁2023/11/2748第48頁/共71頁2023/11/2749第49頁/共71頁2023/11/2750第50頁/共71頁2023/11/2751第51頁/共71頁2023/11/2752第52頁/共71頁2023/11/2753第53頁/共71頁2023/11/2754第54頁/共71頁2023/11/2755第55頁/共71頁2023/11/2756第56頁/共71頁2023/11/2757第57頁/共71頁2023/11/2758第58頁/共71頁2023/11/2759第59頁/共71頁2023/11/2760第60頁/共71頁2023/11/2761第61頁/共71頁2023/11/2762第62頁/共71頁2023/11/2763第63頁/共71頁2023/11/2764第64頁/共71頁2023/11/2765第65頁/共71頁2023/11/2766第66頁/共71頁2023/11/2767凸包模板：//xiaoxia版#include<stdio.h>#include<math.h>#include<stdlib.h>typedefstruct{ doublex; doubley;}POINT;POINTresult[102]; //保存凸包上的點(diǎn)POINTa[102]; intn,top;doubleDistance(POINTp1,POINTp2) //兩點(diǎn)間的距離{ returnsqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}doubleMultiply(POINTp1,POINTp2,POINTp3)//叉積{ return((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x));}intCompare(constvoid*p1,constvoid*p2){ POINT*p3,*p4; doublem;p3=(POINT*)p1;p4=(POINT*)p2; m=Multiply(a[0],*p3,*p4); if(m<0)return1; elseif(m==0&&(Distance(a[0],*p3)<Distance(a[0],*p4))) return1; elsereturn-1;}voidTubao(){inti;result[0].x=a[0].x;result[0].y=a[0].y;result[1].x=a[1].x;result[1].y=a[1].y;result[2].x=a[2].x;result[2].y=a[2].y;top=2;for(i=3;i<=n;i++){while(Multiply(result[top-1],result[top],a[i])<=0) top--;result[top+1].x=a[i].x;result[top+1].y=a[i].y;top++;}}intmain(){inti,p;doublepx,py,len,temp;while(scanf("%d",&n)!=EOF,n){for(i=0;i<n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);if(n==1){printf("0.00\n");continue;}elseif(n==2){printf("%.2lf\n",Distance(a[0],a[1]));continue;}py=-1;for(i=0;i<n;i++) {if(py==-1||a[i].y<py){px=a[i].x;py=a[i].y; p=i;}elseif(a[i].y==py&&a[i].x<px){px=a[i].x;py=a[i].y; p=i;