平面幾何常用算法

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

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

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

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

形式上看，相當(dāng)于長方形的對角線。

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

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

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

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

a·b＝axbx＋ayby

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

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

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

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

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

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

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

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

計算幾何基礎(chǔ)②叉積的等價定義（更實(shí)用），把叉積定義為一個矩陣的行列式：5、矢量的矢量積（叉乘、叉積）如圖，如果為正數(shù)，則相對原點(diǎn)(0,0)來說，P1在P2的順時針方向；如果為負(fù)數(shù)，則P1在P2的逆時針方向。如果=0，則P1和P2模相等且共線，方向相同或相反。計算幾何基礎(chǔ)如圖，如果為正數(shù)，則相對原點(diǎn)(0,0)來說，P1在P2的順時針方向；如果為負(fù)數(shù)，則P1在P2的逆時針方向。如果=0，則P1和P2模相等且共線，方向相同或相反。9、矢量的矢量積（叉乘、叉積）③探討一個重要問題：給定兩個矢量：和，對它們的公共端點(diǎn)P0來說，判斷是否在的順時針方向。方法：如圖，把P0作為原點(diǎn)，得出向量P1’=P1-P0和P2’=P2-P0，因此，這兩個向量的叉積為：如果該叉積為正，則在的順時針方向，如果為負(fù)，則在的逆時針方向。如果等于0，則P0，P1，P2三點(diǎn)共線。計算幾何基礎(chǔ)13p1p2p4p3顯然，只要p1,p2兩點(diǎn)在線段p3p4的兩邊，并且p3,p4在線段p1p2的兩邊，那么這兩條線段必然相交思考：如何判斷兩點(diǎn)是否在一條線段的兩邊？這樣只要d1*d2<0并且d3*d4<0則p1p2和p3p4這兩條線段必然相交注意：若是等于0則要判斷對應(yīng)的點(diǎn)是否在線段上。判斷兩條線段是否相交計算幾何基礎(chǔ)以下定義的d絕對值為向量的模長，正負(fù)為向量的方向。判斷線段是否相交的模板（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)//判斷點(diǎn)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;}二.判斷點(diǎn)是否在多邊形內(nèi)方法一：射線法仔細(xì)觀察：在多邊形內(nèi)的點(diǎn)和不在多邊形內(nèi)的點(diǎn)向某個方向引一條射線，這些射線和多邊形的交點(diǎn)的個數(shù)有什么特點(diǎn)？結(jié)論：如果從該點(diǎn)引一條射線，這條射線和多邊形的交點(diǎn)個數(shù)為奇數(shù)，則該點(diǎn)在多邊形里面，若為偶數(shù)，則該點(diǎn)在多邊形外面。由于有更好更容易實(shí)現(xiàn)的弧長法，就不貼射線法的模板了。弧長法（轉(zhuǎn)角法）：將坐標(biāo)原點(diǎn)平移到被測點(diǎn)P,這個新坐標(biāo)系將平面劃分為4個象限,對每個多邊形頂點(diǎn)P[i],只考慮其所在的象限，然后按鄰接順序訪問多邊形的各個頂點(diǎn)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,則點(diǎn)在多邊形上;若f<0,弧長和減π;若f>0,弧長和加π.最后對算出的代數(shù)和和上述的情況一樣判斷即可.實(shí)現(xiàn)的時候要注意:若被測點(diǎn)和多邊形的頂點(diǎn)重合時要特殊處理.具體實(shí)現(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為需要判斷的點(diǎn),n為多邊形點(diǎn)的個數(shù){inti,sum=0;//用來保存弧長和

p[n]=p[0];//因?yàn)榈谝粋€點(diǎn)和最后一個點(diǎn)的象限關(guān)系也要判斷

for(i=0;i<=n;i++)//因?yàn)榕袛嗟狞c(diǎn)要作為坐標(biāo)原點(diǎn)

{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);//計算第一個點(diǎn)的象限

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

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;//點(diǎn)在邊上

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++)//恢復(fù)坐標(biāo)

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

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

=∣

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

A=sigma(Ai)(i=1…N-2)P1P2P3P4P5P6A1A2A3A42023/2/128凹多邊形的面積？P1P4P3P22023/2/129依然成立?。。《噙呅蚊娣e公式：A=sigma(Ai)(i=1…N-2)結(jié)論：“有向面積”A比“面積”S其實(shí)更本質(zhì)！2023/2/130任意點(diǎn)為扇心的三角形剖分：我們能把多邊形分成N-2個三角形，為什么不能分成N個三角形呢？比如，以多邊形內(nèi)部的一個點(diǎn)為扇心，就可以把多邊形剖分成N個三角形。P0P1P2P6P5P4P32023/2/131前面的三角剖分顯然對于多邊形內(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/2/132能否把扇心移到多邊形以外呢？P0P1P2P3P42023/2/133既然內(nèi)外都可以，為什么不設(shè)P0為坐標(biāo)原點(diǎn)呢？OP1P2P3P4現(xiàn)在的公式？2023/2/134簡化的公式：A=sigma∣

∣/2（i=1…N

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

Y=∑(yi×mi)/∑mi

2、若每個點(diǎn)的質(zhì)量相同則

X=∑xi/n

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

X=(x0+x1+x2)/3

Y=(y0+y1+y2)/32023/2/1將n邊形分成多個三角形，分別求出重心坐標(biāo)以及質(zhì)量m【因?yàn)橘|(zhì)量分布均勻，所以可以設(shè)密度為1，則面積就是質(zhì)量】因?yàn)橘|(zhì)量都集中在重心所以把所有求出來的重心按逆時針連接起來又是一個多邊形但是這個多邊形的質(zhì)量集中在頂點(diǎn)上所以可以利用上面公式進(jìn)行計算2023/2/1求質(zhì)量分布均勻的n邊形重心#include<cstdio>#include<cstdlib>#include<iostream>usingnamespacestd;constintN=1000000;structpoint{doublex;doubley;}p[N],g;//p數(shù)組保存多邊形的頂點(diǎn)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坐標(biāo)最小的點(diǎn)，如果有多個這樣的點(diǎn)，則選擇x最小的。2.剩余的點(diǎn)根據(jù)他們相對于p0的極角的大小從小到大排序，設(shè)排序后的點(diǎn)依次為P[0....n]。3.設(shè)置一個棧，P0,P1,P2先入棧。4.對于P[3..n]的每個點(diǎn)，若它與棧頂?shù)膬蓚€點(diǎn)不構(gòu)成"向左轉(zhuǎn)"的關(guān)系,則將棧頂?shù)狞c(diǎn)出棧,直至沒有點(diǎn)需要出棧以后將當(dāng)前點(diǎn)進(jìn)棧；所有點(diǎn)處理完之后棧中保存的點(diǎn)就是凸包了。思考：如何對這些極角排序？用atan函數(shù)？顯然會有精度問題，不準(zhǔn)確回憶一下以前講的向量的叉積。2023/2/1p0p1p2如何知道p2的極角就比p1大呢？再思考一下如何判斷左轉(zhuǎn)還是右轉(zhuǎn)？自然也是叉積。。。顯然只需要向量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];//保存輸入結(jié)點(diǎn)Pointst[MAXN];//保存凸包結(jié)點(diǎn)，把que當(dāng)一個棧來使用inttop;//記錄棧頂位置doubledis(Pointa,Pointb)//求a,b兩點(diǎn)距離{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(