什么是“二維計(jì)算幾何”？當(dāng)我們將需要解決的幾何問題的范圍限制在二維平面內(nèi)，這樣就用到了二維計(jì)算幾何。要用電腦解平面幾何題？這就是陷入誤區(qū)了，我們并不是用計(jì)算機(jī)算數(shù)學(xué)卷子上的幾何題去了，而是解決一些更加復(fù)雜的幾何相關(guān)問題。

為了解決復(fù)雜且抽象的問題，我們一定要選擇合適的研究方法。對(duì)于計(jì)算機(jī)來說，給它看幾何圖形……

我們可以把要研究的圖形放在平面直角坐標(biāo)系或極坐標(biāo)系下，這樣解決問題就會(huì)方便很多。

計(jì)算幾何中坐標(biāo)一般是實(shí)數(shù)，編程時(shí)使用double，不要使用精度較低的float。

在進(jìn)行浮點(diǎn)數(shù)運(yùn)算時(shí)會(huì)產(chǎn)生精度誤差，可以設(shè)置一個(gè)偏差值eps(epsilon)來控制精度。

判斷浮點(diǎn)數(shù)是否等于零或兩個(gè)浮點(diǎn)數(shù)是否相等要用eps輔助判斷。

#include<bits/stdc++.h>
using namespace std;
#define db double
const db pi = acos(-1.0);   //高精度圓周率
const db eps = 1e-8;        //可根據(jù)具體需要更改精度
inline int sgn(db x){		//判斷是否等于零
	if(fabs(x)<eps) return 0;
	else return x<0?-1:1;
}
inline int dcmp(db x,db y){	//比較浮點(diǎn)數(shù)
	if(fabs(x-y)<eps)return 0;
	else return x<y?-1:1;
}

點(diǎn)和向量

1. 點(diǎn)

二位平面中的點(diǎn)用(x,y)表示。

struct Point{
	db x,y;
	Point(){}
	Point(db _x,db _y):x(_x),y(_y){}
};

2. 兩點(diǎn)之間的距離

db Dist(Point &a,Point &b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

3. 向量

有大小，有方向的量稱為向量(矢量) ，只有大小沒有方向的量稱為標(biāo)量。

在平面上兩個(gè)點(diǎn)可確定一個(gè)向量，由于向量不是一個(gè)有向線段，及向量沒有起點(diǎn)與終點(diǎn)的概念，所有向量平移后不變。大多時(shí)候?yàn)榱朔奖憧芍苯訉⑾蛄科揭频皆c(diǎn)處。向量的表示在形式上與點(diǎn)一樣，可以用點(diǎn)的數(shù)據(jù)結(jié)構(gòu)表示向量。

typedef Point Vector;

4. 向量的運(yùn)算

在struct Point中，對(duì)向量運(yùn)算重載運(yùn)算符。

+：點(diǎn)加點(diǎn)沒有意義，點(diǎn)加向量得到另一個(gè)點(diǎn)，向量加向量得到另一個(gè)向量。

Point operator+(Point &a){return Point(x+a.x,y+a.y);}

-：兩個(gè)點(diǎn)的差得到一個(gè)向量，向量A減B得到有B指向A的向量。

Point operator-(Point &a){return Point(x-a.x,y-a.y);}

*：向量乘實(shí)數(shù)等比例放大。

Point operator*(db a){return Point(x*a,y*a);}

/:向量與實(shí)數(shù)相除等比例縮小。

Point operator/(db a){return Point(x/a,y/a);}

==:相等

bool operator==(Point &a){return sgn(x-a.x)==0&&sgn(y-a.y)==0;}

點(diǎn)積和叉積

向量的基本運(yùn)算是點(diǎn)積和叉積，計(jì)算幾何的各種操作幾乎都基于這兩種操作。

1. 點(diǎn)積(Dot product)

其中θ為A，B之間的夾角。點(diǎn)積的幾何意義是A在B上投影的長度乘以B的模長。

在編程中并不需要知道θ。如果已知A=(A.x,A.y),B=(B.x,B.y)，那么有：

A?B=A.x?B.x+A.y?B.y

A.x?B.x+A.y?B.y

=(|A|cosθ1?|B|cosθ2)+(|A|sinθ1?|B|sinθ2)

|A||B|(cosθ1cosθ2+sinθ1sinθ2)

|A||B|cos(θ1?θ2)

|A||B|cosθ

db Dot(Vector &a,Vector &b){return a.x*b.x+a.y*b.y;}

2. 點(diǎn)積的應(yīng)用

（1）判斷A,B之間的角是鈍角銳角還是直角。

（2）求A的長度(模)

db len(Vector &a){return sqrt(Dot(a,a));}

（3）求A,B夾角的大小

db Angle(Vector &a,Vector &b){return acos(Dot(a,b)/len(a)/len(b));}

3. 叉積(Cross product)

叉積是比點(diǎn)積等常用的集合概念。

θ表示A旋轉(zhuǎn)到B所經(jīng)過的夾角。

兩個(gè)向量的叉積的結(jié)果是一個(gè)帶符號(hào)的數(shù)值，其幾何意義為A,B形成平行四邊形的“有向”面積，其正負(fù)可通過“右手定則”判斷。

db Cross(Vector &a,Vector &b){return a.x*b.y-a.y*b.x;}

A.x?B.y?A.y?B.x

=|A||B|(cosθ1sinθ2?sinθ1cosθ2)

=|A||B|sin(θ2?θ1)

當(dāng)θ2>θ1時(shí)，結(jié)果為正，且B在A的逆時(shí)針方向。

故可通過正負(fù)來判斷A，B的相對(duì)位置。

4. 叉積的基本應(yīng)用

（1）判斷A，B的方向關(guān)系。

（2）計(jì)算兩向量構(gòu)成的平行四邊形的“有向面積”

db Area2(Point a,Point b,Point c){return Cross(b-a,c-a);}

（3）計(jì)算3個(gè)點(diǎn)構(gòu)成的三角形面積

（4）向量旋轉(zhuǎn)

是向量(x,y)繞起點(diǎn)逆時(shí)針旋轉(zhuǎn)θ，旋轉(zhuǎn)后的向量為(x′,y′)

Vector Rotate(Vector a,db rad){
	return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}

（5）用叉積檢查向量是否平行或重合

bool Parallel(Vector a,Vector b){return sgn(Cross(a,b))==0;}

點(diǎn)和線

1. 直線的表示

直線的表示方法很多，編程時(shí)可靈活選擇：

（1）用直線上的兩個(gè)點(diǎn)表示。

（2）ax+by+c=0，普通式。

（3）y=kx+b，斜街式，注意斜率不存在的情況。

（4）P=P0+vt，點(diǎn)向式。用P0和v來表示直線P，t是任意值，P0是直線上一點(diǎn)，v是方向向量，v=A?B。

t無限制時(shí)，P是直線。

t∈[0,1]，P是A，B之間的線段。

t>0,P是射線。

struct line{
	Point p1,p2;
	line(){}
	line(Point _p1,Point _p2):p1(_p1),p2(_p2){}
	//一個(gè)點(diǎn)和角(angle)確定直線，0<=angle<pi
	line(Point p,db angle){
		p1=p;
		if(sgn(angle-pi/2)==0){p1=p+Point(0,1);}
		else p1=p+Point(1,tan(angle));
	}
	//ax+by+c=0;
	line(db a,db b,db c){
		if(sgn(a)==0){
			p1=Point(0,-c/b);
			p2=Point(1,-c/b);
		}
		else if(sgn(b)==0){
			p1=Point(-c/a,0);
			p2=Point(-c/a,1);
		}
		else{
			p1=Point(0,-c/b);
			p2=Point(-c/a,0);
		}
	}
};

2. 線段的表示

可以用兩個(gè)點(diǎn)表示線段，直接用直線的數(shù)據(jù)結(jié)構(gòu)表示線段。

typedef line Segment;

3. 在二維平面上，點(diǎn)和直線有三種位置關(guān)系，在直線上，左側(cè)和右側(cè)。用叉積的正負(fù)可判斷方向。

int Point_line_relation(Point p,line v){
	int c=sgn(Cross(p-v.p1,v.p2-v.p1));
	if(c<0)return 1;		//順時(shí)針
	else if(c>0)return 2;	        //逆時(shí)針
	return 0;			//在直線上
}

4. 點(diǎn)和線段的關(guān)系

先用叉積判斷是否共線，再用點(diǎn)積判斷點(diǎn)與線段兩端的角是否為180°。

int Point_on_seg(Point p,line v){
	return sgn(Cross(v.p1-p,v.p2-p))==0&&sgn(Dot(v.p1-p,v.p2-p))<=0;
}

5. 點(diǎn)到直線的距離

已知點(diǎn)p到直線v(p1,p2)，求p到v的距離。首先用叉積求p,p1,p2構(gòu)成的平行四邊形的面積，然后除以線段(p1,p2)的長度即可。

db Dis_point_line(Point p,line v){
    return fabs(Cross(p-v.p1,v.p2-v.p1)/Dist(v.p1,v.p2));//注意叉積有正負(fù)
}

6. 點(diǎn)在直線上的投影

已知直線上的兩點(diǎn)p1，p2以及直線外一點(diǎn)p,求投影點(diǎn)p0，我們先來看下上圖左邊的那種情形。

令，即k是線段p0p1和p2p1長度的比值，那么有。

根據(jù)點(diǎn)積的概念有，

及

帶入即：

那么：

容易證明上圖右邊那種情況也滿足此式。

Point Point_line_proj(Point p,line v){
	double k=Dot(p-v.p1,v.p2-p)/len(v.p2-v.p1)/len(v.p2-v.p1);
	return v.p1+(v.p2-v.p1)*k;
}

7. 點(diǎn)關(guān)于直線的對(duì)稱點(diǎn)

求點(diǎn)p關(guān)于直線的對(duì)稱點(diǎn)，先求投影點(diǎn)，在求對(duì)稱點(diǎn)。

Point Point_line_symmetry(Point p,line v){
	Point p1=Point_line_proj(p,v);
	return Point(p1.x*2-p.x,p1.y*2-p.y);
}

8. 點(diǎn)到線段的距離

點(diǎn)p到線段AB的距離，在p到A的距離，p到B的距離，p到直線AB的距離(如果垂足在線段AB上)。

db Dis_point_seg(Point p,Segment v){
	if(Dot(p-v.p1,v.p2-v.p1)<0||Dot(p-v.p2,v.p1-v.p2)<0)return min(Dist(p,v.p1),Dist(p,v.p2));
	return Dis_point_line(p,v);
}

9. 兩條直線的位置關(guān)系

int line_relation(line v1,line v2){
	if(sgn(Cross(v1.p1-v1.p2,v2.p1-v2.p2))==0){
		if(Point_line_relation(v1.p1,v2)==0)return 1;//重合
		else return 0;//平行
	}
	return 2;//相交
}

10. 求兩個(gè)直線的交點(diǎn)

可以聯(lián)立方程求解，也可以用簡單的叉積來實(shí)現(xiàn)。

如圖，AB與CD的交點(diǎn)為P。

容易得到以下兩個(gè)等式：

聯(lián)立上面兩個(gè)方程，即可得到點(diǎn)P的坐標(biāo)：

Point Cross_point(line a,line b){
	db s1=Cross(b.p1-a.p1,a.p2-a.p1);
	db s2=Cross(a.p2-a.p1,b.p2-a.p1);//注意叉積的正負(fù)
	return Point(s1*b.p2.x+s2*b.p1.x,s1*b.p2.y+s2*b.p1.y)/(s1*s2);
}

注意函數(shù)要對(duì)(s1+s2)做除法，在調(diào)用前要保證兩直線不平行且不重合。

11. 判斷兩線段是否有交點(diǎn)

bool Cross_segment(Segment a,Segment b){
	db c1=Cross(a.p1-a.p2,b.p1-a.p2),c2=Cross(a.p1-a.p2,b.p2-a.p2);
	db d1=Cross(b.p1-b.p2,a.p1-b.p2),d2=Cross(b.p1-b.p2,a.p2-b.p2);
	return c1*c2<=0&&d1*d2<=0;
}

12. 求兩個(gè)線段的交點(diǎn)

先判斷有沒有交點(diǎn)，有交點(diǎn)轉(zhuǎn)化為直線求就行了。

多邊形

1. 判斷點(diǎn)在多邊形內(nèi)部

給定一個(gè)點(diǎn)P和一個(gè)多邊形，判斷點(diǎn)P在多邊形的內(nèi)部還是外部。

從點(diǎn)P引出一條直線(與多邊形交于兩點(diǎn))，檢查P與多邊形每條邊的相交情況，檢查的方向不影響結(jié)果，但不能中途改變方向。

檢查以下3個(gè)參數(shù)：

顯然u,v是用來判斷是否相交，c用來判斷p與邊的位置關(guān)系。

最后當(dāng)num>0時(shí)p在多邊形內(nèi)部。

int Point_in_polygon(Point pt,Point *p,int n){
	//注意P[]中的點(diǎn)為嚴(yán)格逆時(shí)針或順時(shí)針
	for(int i=0;i<n;++i){
		if(p[i]==pt)return 3;//點(diǎn)p在多邊形的頂點(diǎn)上
	}
	for(int i=0;i<n;++i){
		line v=line(p[i],p[(i+1)%n]);
		if(Point_on_seg(pt,v))return 2;//點(diǎn)在多邊形邊上
	}
	int num=0;
	for(int i=0;i<n;++i){
		int j=(i+1)%n;
		int c=sgn(Cross(pt-p[j],p[i]-p[j]));
		int u=sgn(p[i].y-pt.y);
		int v=sgn(p[j].y-pt.y);
		if(c>0&&u<0&&v>=0)num++;
		if(c<0&&u>=0&&v<0)num--;//注意這里不能用n*v<0判斷
	}
	return num>0;//1在內(nèi)部，0在外部 
}

3. 求多邊形面積

對(duì)于一個(gè)多邊形，可以在其內(nèi)部找一點(diǎn)p，將多邊形劃分為n個(gè)三角形，計(jì)算n個(gè)三角形的面積之和即可。

實(shí)際上p的位置可任意選取，叉積的正負(fù)可將多余的面積抵消掉，所以一般將p選在原點(diǎn)。

db Polygon_area(Point*p,int n){
	db ans=0;
	for(int i=0;i<n;++i){
		ans+=Cross(p[i],p[(i+1)/n]);
	}
	return ans/2;//注意面積有正負(fù)，可根據(jù)需要判斷是否要去絕對(duì)值
}