平面幾何常用算法

平面幾何常用算法2014.8.211.計算幾何基礎2023/2/12.凸包問題3.旋轉卡殼計算幾何基礎2023/2/11、向量（矢量）的概念①矢量：有方向的線段，即P1和P2的順序是有關系的，記為：如果P1是坐標原點，則又稱為向量P2。②矢量的斜率：既然矢量是有方向的，那么矢量的斜率k就是有正負之分的，具體如下：IIIⅢⅣ計算幾何基礎1、向量（矢量）的概念③設=a，則有向線段的長度叫做向量（矢量）a的長度或模，記作|a|。④夾角：兩個非0矢量a、b，在空間任取一點O，作=a，=b，則角∠AOB叫做矢量a與b的夾角，記作<a，b>。若<a，b>=π/2，則稱a與b互相垂直，記作a⊥b。計算幾何基礎計算幾何基礎2、矢量的加減法

以點O為起點、A為端點作矢量a，以點A為起點、B為端點作矢量b，則以點O為起點、B為端點的矢量稱為a與b的和a+b，如下中圖。

若從A點作，要求的模等于|b|，方向與b相反，即

=-b，則以O為起點、B’為端點的矢量稱為a與b的差a-b，如下右圖。3、矢量的分解定理：如果平面兩個矢量a,b，對任一矢量p，一定存在一個且僅一個有序實數(shù)組x,y，使得：p=xa+yb。含義與物理上的合力或力的分解一樣。

形式上看，相當于長方形的對角線。

計算幾何基礎4、矢量的數(shù)量積（點乘）

兩個矢量的數(shù)量積是一個數(shù)，大小等于這兩個矢量的模的乘積再乘以它們夾角的余弦。即：

a·b＝|a||b|cos<a,b>

數(shù)量積等于兩個矢量的對應支量乘積之和。即：

a·b＝axbx＋ayby

計算幾何基礎4、矢量的數(shù)量積（點乘）

數(shù)量積的性質：①

a·e=|a||e|cos<a,e>=|a|cos<a,e>②

a⊥b等價于a·b＝0,即axbx＋ayby=0③

自乘：|a|2＝a·a④

結合律：（λ·a）·b=λ(a·b)⑤

交換律：a·b＝b·a⑥

分配律：a·(b+c)＝a·b+a·c計算幾何基礎5、矢量的矢量積（叉乘、叉積）①矢量積的一般含義：兩個矢量a和b的矢量積是一個矢量，記作a×b，其模等于由a和b作成的平行四邊形的面積，方向與平行四邊形所在平面垂直，當站在這個方向觀察時，a逆時針轉過一個小于π的角到達b的方向。這個方向也可以用物理上的右手螺旋定則判斷：右手四指彎向由A轉到B的方向（轉過的角小于π），拇指指向的就是矢量積的方向。

計算幾何基礎②叉積的等價定義（更實用），把叉積定義為一個矩陣的行列式：5、矢量的矢量積（叉乘、叉積）如圖，如果為正數(shù)，則相對原點(0,0)來說，P1在P2的順時針方向；如果為負數(shù)，則P1在P2的逆時針方向。如果=0，則P1和P2模相等且共線，方向相同或相反。計算幾何基礎如圖，如果為正數(shù)，則相對原點(0,0)來說，P1在P2的順時針方向；如果為負數(shù)，則P1在P2的逆時針方向。如果=0，則P1和P2模相等且共線，方向相同或相反。9、矢量的矢量積（叉乘、叉積）③探討一個重要問題：給定兩個矢量：和，對它們的公共端點P0來說，判斷是否在的順時針方向。方法：如圖，把P0作為原點，得出向量P1’=P1-P0和P2’=P2-P0，因此，這兩個向量的叉積為：如果該叉積為正，則在的順時針方向，如果為負，則在的逆時針方向。如果等于0，則P0，P1，P2三點共線。計算幾何基礎13p1p2p4p3顯然，只要p1,p2兩點在線段p3p4的兩邊，并且p3,p4在線段p1p2的兩邊，那么這兩條線段必然相交思考：如何判斷兩點是否在一條線段的兩邊？這樣只要d1*d2<0并且d3*d4<0則p1p2和p3p4這兩條線段必然相交注意：若是等于0則要判斷對應的點是否在線段上。判斷兩條線段是否相交計算幾何基礎以下定義的d絕對值為向量的模長，正負為向量的方向。判斷線段是否相交的模板（hdu1086）include<iostream>usingnamespacestd;structpoint{doublex,y;};structsegment{pointbegin,end;};doublemin(doublex,doubley){returnx<y?x:y;}doublemax(doublex,doubley){returnx>y?x:y;}boolonsegment(pointpi,pointpj,pointpk)//判斷點pk是否在線段pipj上{if(min(pi.x,pj.x)<=pk.x&&pk.x<=max(pi.x,pj.x)){if(min(pi.y,pj.y)<=pk.y&&pk.y<=max(pi.y,pj.y)){returntrue;}}returnfalse;}doubledirection(pointpi,pointpj,pointpk)//計算向量pkpi和向量pjpi的叉積{return(pi.x-pk.x)*(pi.y-pj.y)-(pi.y-pk.y)*(pi.x-pj.x);}booljudge(pointp1,pointp2,pointp3,pointp4)//判斷線段p1p2和p3p4是否相交{doubled1=direction(p3,p4,p1);doubled2=direction(p3,p4,p2);doubled3=direction(p1,p2,p3);doubled4=direction(p1,p2,p4);if(d1*d2<0&&d3*d4<0)returntrue;if(d1==0&&onsegment(p3,p4,p1))returntrue;if(d2==0&&onsegment(p3,p4,p2))returntrue;if(d3==0&&onsegment(p1,p2,p3))returntrue;if(d4==0&&onsegment(p1,p2,p4))returntrue;returnfalse;}二.判斷點是否在多邊形內方法一：射線法仔細觀察：在多邊形內的點和不在多邊形內的點向某個方向引一條射線，這些射線和多邊形的交點的個數(shù)有什么特點？結論：如果從該點引一條射線，這條射線和多邊形的交點個數(shù)為奇數(shù)，則該點在多邊形里面，若為偶數(shù)，則該點在多邊形外面。由于有更好更容易實現(xiàn)的弧長法，就不貼射線法的模板了?；￠L法（轉角法）：將坐標原點平移到被測點P,這個新坐標系將平面劃分為4個象限,對每個多邊形頂點P[i],只考慮其所在的象限，然后按鄰接順序訪問多邊形的各個頂點P[i]分析P[i]和P[i+1],有下列四種情況:、(1)P[i+1]和P[i]在同一象限，此時弧長和不變;(1)P[i+1]在P[i]的下一象限,此時弧長和加π/2;(2)P[i+1]在P[i]的上一象限,此時弧長和減π/2;(3)P[i+1]在P[i]的相對象限,首先計算f=p[i+1].y*p[i].x-p[i+1].x*p[i].y(叉積),若f=0,則點在多邊形上;若f<0,弧長和減π;若f>0,弧長和加π.最后對算出的代數(shù)和和上述的情況一樣判斷即可.實現(xiàn)的時候要注意:若被測點和多邊形的頂點重合時要特殊處理.具體實現(xiàn)的時候取x>=0y>=0作為第一象限x<0y>=0作為第二象限x<0y<0作為第三象限x>=0y<0作為第四象限2023/2/1S=-pi/2-pi/2+0-pi/2-pi/2=-2*pi弧長法模板（zju1081）2023/2/1structpoint{intx,y;}p[MAX];boolinpolygon(pointt,intn)//t為需要判斷的點,n為多邊形點的個數(shù){inti,sum=0;//用來保存弧長和

p[n]=p[0];//因為第一個點和最后一個點的象限關系也要判斷

for(i=0;i<=n;i++)//因為判斷的點要作為坐標原點

{p[i].x-=t.x;p[i].y-=t.y;}intt1=p[0].x>=0?(p[0].y>=0?0:3):(p[0].y>=0?1:2);//計算第一個點的象限

for(i=1;i<=n;i++){if(!p[i].x&&!p[i].y)break;//多邊形的一個頂點就是被測點

intf=p[i].y*p[i-1].x-p[i].x*p[i-1].y;//做叉積

if(!f&&p[i-1].x*p[i].x<=0&&p[i-1].y*p[i].y<=0)break;//點在邊上

intt2=p[i].x>=0?(p[i].y>=0?0:3):(p[i].y>=0?1:2);//計算象限

if(t2==(t1+1)%4)sum+=1;//P[i+1]在P[i]的下一象限,此時弧長和加π/2;

elseif(t2==(t1+3)%4)sum-=1;//P[i+1]在P[i]的上一象限,此時弧長和減π/2;

elseif(t2==(t1+2)%4)//P[i+1]在P[i]的相對象限

{if(f>0)sum+=2;elsesum-=2;}t1=t2;}for(intj=0;j<n;j++)//恢復坐標

{p[j].x+=t.x;p[j].y+=t.y;}if(i<=n||sum)returntrue;elsereturnfalse;}2023/2/119多邊形面積和重心2023/2/120基本問題（1）：給定一個簡單多邊形，求其面積。輸入：多邊形（頂點按逆時針順序排列）輸出：面積S2023/2/121思考如下圖形：2023/2/122先看最簡單的多邊形——三角形2023/2/123三角形的面積：在解析幾何里，△ABC的面積可以通過如下方法求得：點坐標=>邊長=>海倫公式=>面積2023/2/124思考：此方法的缺點：計算量大精度損失更好的方法？2023/2/125計算幾何的方法：在計算幾何里，我們知道，△ABC的面積就是“向量AB”和“向量AC”兩個向量叉積的絕對值的一半。其正負用右手螺旋定則判斷負面積正面積BCACBA2023/2/126大功告成：

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

=∣

∣/2特別注意：以上得到是有向面積（有正負）！Xb–XaYb–YaXc–XaYc–Ya2023/2/127凸多邊形的三角形剖分很自然地，我們會想到以P1為扇面中心，連接P1Pi就得到N-2個三角形，由于凸性，保證這些三角形全在多邊形內，那么，這個凸多邊形的有向面積：

A=sigma(Ai)(i=1…N-2)P1P2P3P4P5P6A1A2A3A42023/2/128凹多邊形的面積？P1P4P3P22023/2/129依然成立?。。《噙呅蚊娣e公式：A=sigma(Ai)(i=1…N-2)結論：“有向面積”A比“面積”S其實更本質！2023/2/130任意點為扇心的三角形剖分：我們能把多邊形分成N-2個三角形，為什么不能分成N個三角形呢？比如，以多邊形內部的一個點為扇心，就可以把多邊形剖分成N個三角形。P0P1P2P6P5P4P32023/2/131前面的三角剖分顯然對于多邊形內部任意一點都是合適的！我們可以得到：A=sigma(Ai)（i=1…N

）即：A=sigma∣

∣/2

（i=1…N

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

∣/2（i=1…N

）XiYiX(i+1)Y(i+1)2023/2/135基本問題（2）：給定一個簡單多邊形，求其重心。輸入：多邊形（頂點按逆時針順序排列）輸出：重心點C求任意多邊形的重心1、質量集中在頂點上，n個頂點坐標為(xi,yi)，質量為mi，則重心X=∑(xi×mi)/∑mi

Y=∑(yi×mi)/∑mi

2、若每個點的質量相同則

X=∑xi/n

Y=∑yi/n2、質量分布均勻3、特殊地，質量均勻的三角形重心：

X=(x0+x1+x2)/3

Y=(y0+y1+y2)/32023/2/1將n邊形分成多個三角形，分別求出重心坐標以及質量m【因為質量分布均勻，所以可以設密度為1，則面積就是質量】因為質量都集中在重心所以把所有求出來的重心按逆時針連接起來又是一個多邊形但是這個多邊形的質量集中在頂點上所以可以利用上面公式進行計算2023/2/1求質量分布均勻的n邊形重心#include<cstdio>#include<cstdlib>#include<iostream>usingnamespacestd;constintN=1000000;structpoint{doublex;doubley;}p[N],g;//p數(shù)組保存多邊形的頂點doublecrossProd(pointA,pointB,pointC)//計算三角形ABC有向面積{return(B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);}voidcompGravity(intn)//求重心g{pointtmp;doublesumArea,area;sumArea=0;g.x=g.y=0;for(inti=2;i<n;++i){area=crossProd(p[0],p[i-1],p[i]);sumArea+=area;tmp.x=p[0].x+p[i-1].x+p[i].x;tmp.y=p[0].y+p[i-1].y+p[i].y;g.x+=tmp.x*area;g.y+=tmp.y*area;}g.x/=(sumArea*3.0);g.y/=(sumArea*3.0);}2023/2/1二、凸包的求解2023/2/1二.凸包的求法(Graham算法)凸包的定義：你可以這樣想象：平面上有很多根釘子,你的手里有一根橡皮環(huán),你用橡皮環(huán)把這些釘子都套起來，然后松手，橡皮環(huán)所形成的圖形就是這些釘子的一個凸包（如下圖）Graham掃描法：1.選則p0作為y坐標最小的點，如果有多個這樣的點，則選擇x最小的。2.剩余的點根據(jù)他們相對于p0的極角的大小從小到大排序，設排序后的點依次為P[0....n]。3.設置一個棧，P0,P1,P2先入棧。4.對于P[3..n]的每個點，若它與棧頂?shù)膬蓚€點不構成"向左轉"的關系,則將棧頂?shù)狞c出棧,直至沒有點需要出棧以后將當前點進棧；所有點處理完之后棧中保存的點就是凸包了。思考：如何對這些極角排序？用atan函數(shù)？顯然會有精度問題，不準確回憶一下以前講的向量的叉積。2023/2/1p0p1p2如何知道p2的極角就比p1大呢？再思考一下如何判斷左轉還是右轉？自然也是叉積。。。顯然只需要向量p0p1和向量p0p2做叉積就可以了，如果大于0則p2的極角比p1大。2023/2/1432023/2/1442023/2/1452023/2/1462023/2/1472023/2/1482023/2/1492023/2/1502023/2/1512023/2/1522023/2/1532023/2/1542023/2/1552023/2/1graham算法模板#include<iostream>#include<cmath>#include<algorithm>usingnamespacestd;constintMAXN=105;constdoubleeps=1e-8;structPoint{intx;inty;};Pointp[MAXN];//保存輸入結點Pointst[MAXN];//保存凸包結點，把que當一個棧來使用inttop;//記錄棧頂位置doubledis(Pointa,Pointb)//求a,b兩點距離{returnsqrt(double((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));}intcross(Pointp1,Pointp2,Pointp0)//求P0P1與P0P2的叉積{return(