// 返回兩點之間的距離
float Distance(POINT p1, POINT p2)
{
	float fRet;
	fRet = sqrt( (double)( (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y) ) );
	return fRet;
}
float Distance(POINT p1, pointf p2)
{
	float fRet;
	fRet = sqrt( (double)( (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y) ) );
	return fRet;
}

// 返回點c到線段ab的最小距離
// a和b是線段的兩個端點， c是檢測點
float DistanceLine(POINT  a, POINT b, POINT c)  
{
	POINT  ab; // = b - a;
	ab.x = b.x - a.x;
	ab.y = b.y - a.y;
	POINT ac;// = c-a;
	ac.x = c.x - a.x;
	ac.y = c.y - a.y;
	float f ;//= ab * ac;
	f = ab.x * ac.x + ab.y * ac.y;
	if ( f<0 ) 
	{
		return Distance(a, c);
	}
	float d;// = ab * ab;
	d = ab.x * ab.x + ab.y * ab.y;
	if ( f>d) return Distance(b, c);
	f = f/d; 
	pointf D;// = a + f *ab;   // c在ab線段上的投影點
	D.x = a.x + f * ab.x;
	D.y = a.y + f * ab.y;
	return Distance(a, D);
}


計算幾何算法(含源代碼)㈠ 點的基本運算 
1. 平面上兩點之間距離 1 
2. 判斷兩點是否重合 1 
3. 矢量叉乘 1 
4. 矢量點乘 2 
5. 判斷點是否在線段上 2 
6. 求一點饒某點旋轉后的坐標 2 
7. 求矢量夾角 2 

㈡ 線段及直線的基本運算 
1. 點與線段的關系 3 
2. 求點到線段所在直線垂線的垂足 4 
3. 點到線段的最近點 4 
4. 點到線段所在直線的距離 4 
5. 點到折線集的最近距離 4 
6. 判斷圓是否在多邊形內 5 
7. 求矢量夾角余弦 5 
8. 求線段之間的夾角 5 
9. 判斷線段是否相交 6 
10.判斷線段是否相交但不交在端點處 6 
11.求線段所在直線的方程 6 
12.求直線的斜率 7 
13.求直線的傾斜角 7 
14.求點關于某直線的對稱點 7 
15.判斷兩條直線是否相交及求直線交點 7 
16.判斷線段是否相交，如果相交返回交點 7 

㈢ 多邊形常用算法模塊 
1. 判斷多邊形是否簡單多邊形 8 
2. 檢查多邊形頂點的凸凹性 9 
3. 判斷多邊形是否凸多邊形 9 
4. 求多邊形面積 9 
5. 判斷多邊形頂點的排列方向，方法一 10 
6. 判斷多邊形頂點的排列方向，方法二 10 
7. 射線法判斷點是否在多邊形內 10 
8. 判斷點是否在凸多邊形內 11 
9. 尋找點集的graham算法 12 
10.尋找點集凸包的卷包裹法 13 
11.判斷線段是否在多邊形內 14 
12.求簡單多邊形的重心 15 
13.求凸多邊形的重心 17 
14.求肯定在給定多邊形內的一個點 17 
15.求從多邊形外一點出發到該多邊形的切線 18 
16.判斷多邊形的核是否存在 19 

㈣ 圓的基本運算 
1 .點是否在圓內 20 
2 .求不共線的三點所確定的圓 21 

㈤ 矩形的基本運算 
1.已知矩形三點坐標，求第4點坐標 22 

㈥ 常用算法的描述 22 

㈦ 補充 
1．兩圓關系： 24 
2．判斷圓是否在矩形內： 24 
3．點到平面的距離： 25 
4．點是否在直線同側： 25 
5．鏡面反射線： 25 
6．矩形包含： 26 
7．兩圓交點： 27 
8．兩圓公共面積： 28 
9. 圓和直線關系： 29 
10. 內切圓： 30 
11. 求切點： 31 
12. 線段的左右旋： 31 
13．公式： 32 


/* 需要包含的頭文件 */ 
#include 

/* 常用的常量定義 */ 
const double INF = 1E200 
const double EP = 1E-10 
const int MAXV = 300 
const double PI = 3.14159265 

/* 基本幾何結構 */ 
struct POINT 
{ 
double x; 
double y; POINT(double a=0, double b=0) { x=a; y=b;} file://constructor 
}; 
struct LINESEG 
{ 
POINT s; 
POINT e; LINESEG(POINT a, POINT b) { s=a; e=b;} 
LINESEG() { } 
}; 
struct LINE // 直線的解析方程 a*x+b*y+c=0 為統一表示，約定 a >= 0 
{ 
double a; 
double b; 
double c; LINE(double d1=1, double d2=-1, double d3=0) {a=d1; b=d2; c=d3;} 
}; 

/********************\ 
* * 
* 點的基本運算 * 
* * 
\********************/ 

double dist(POINT p1,POINT p2) // 返回兩點之間歐氏距離 
{ 
return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) ); 
} 
bool equal_point(POINT p1,POINT p2) // 判斷兩個點是否重合 
{ 
return ( (abs(p1.x-p2.x)} 

/*****************************************************************************
* 
r=multiply(sp,ep,op),得到(sp-op)*(ep-op)的叉積 
r>0:ep在矢量opsp的逆時針方向； 
r=0：opspep三點共線； 
r<0:ep在矢量opsp的順時針方向 
******************************************************************************
*/ 

double multiply(POINT sp,POINT ep,POINT op) 
{ 
return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y)); 
} 

/*****************************************************************************
** 
r=dotmultiply(p1,p2,op),得到矢量(p1-op)和(p2-op)的點積，如果兩個矢量都非零矢量
 
r<0:兩矢量夾角為銳角；r=0：兩矢量夾角為直角；r>0:兩矢量夾角為鈍角 
******************************************************************************
*/ 
double dotmultiply(POINT p1,POINT p2,POINT p0) 
{ 
return ((p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y)); 
} 

/* 判斷點p是否在線段l上，條件：(p在線段l所在的直線上)&& (點p在以線段l為對角線的
矩形內) */ 
bool online(LINESEG l,POINT p) 
{ 
return((multiply(l.e,p,l.s)==0) 
&&( ( (p.x-l.s.x)*(p.x-l.e.x)<=0 )&&( (p.y-l.s.y)*(p.y-l.e.y)<=0 ) ) ); 
} 

// 返回點p以點o為圓心逆時針旋轉alpha(單位：弧度)后所在的位置 
POINT rotate(POINT o,double alpha,POINT p) 
{ 
POINT tp; 
p.x-=o.x; 
p.y-=o.y; 
tp.x=p.x*cos(alpha)-p.y*sin(alpha)+o.x; 
tp.y=p.y*cos(alpha)+p.x*sin(alpha)+o.y; 
return tp; 
} 

/* 返回頂角在o點，起始邊為os，終止邊為oe的夾角(單位：弧度) 
角度小于pi，返回正值 
角度大于pi，返回負值 
可以用于求線段之間的夾角 
*/ 
double angle(POINT o,POINT s,POINT e) 
{ 
double cosfi,fi,norm; 
double dsx = s.x - o.x; 
double dsy = s.y - o.y; 
double dex = e.x - o.x; 
double dey = e.y - o.y; 

cosfi=dsx*dex+dsy*dey; 
norm=(dsx*dsx+dey*dey)*(dex*dex+dey*dey); 
cosfi /= sqrt( norm ); 

if (cosfi >= 1.0 ) return 0; 
if (cosfi <= -1.0 ) return -3.1415926; 

fi=acos(cosfi); 
if (dsx*dey-dsy*dex>0) return fi; // 說明矢量os 在矢量 oe的順時針方向 
return -fi; 
} 


/*****************************\ 
* * 
* 線段及直線的基本運算 * 
* * 
\*****************************/ 

/* 判斷點與線段的關系,用途很廣泛 
本函數是根據下面的公式寫的，P是點C到線段AB所在直線的垂足 

AC dot AB 
r = --------- 
||AB||^2 
(Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay) 
= ------------------------------- 
L^2 

r has the following meaning: 

r=0 P = A 
r=1 P = B 
r<0 P is on the backward extension of AB 
r>1 P is on the forward extension of AB 
0*/ 
double relation(POINT p,LINESEG l) 
{ 
LINESEG tl; 
tl.s=l.s; 
tl.e=p; 
return dotmultiply(tl.e,l.e,l.s)/(dist(l.s,l.e)*dist(l.s,l.e)); 
} 

// 求點C到線段AB所在直線的垂足 P 
POINT perpendicular(POINT p,LINESEG l) 
{ 
double r=relation(p,l); 
POINT tp; 
tp.x=l.s.x+r*(l.e.x-l.s.x); 
tp.y=l.s.y+r*(l.e.y-l.s.y); 
return tp; 
} 
/* 求點p到線段l的最短距離,并返回線段上距該點最近的點np 
注意：np是線段l上到點p最近的點，不一定是垂足 */ 
double ptolinesegdist(POINT p,LINESEG l,POINT &np) 
{ 
double r=relation(p,l); 
if(r<0) 
{ 
np=l.s; 
return dist(p,l.s); 
} 
if(r>1) 
{ 
np=l.e; 
return dist(p,l.e); 
} 
np=perpendicular(p,l); 
return dist(p,np); 
} 

// 求點p到線段l所在直線的距離,請注意本函數與上個函數的區別 
double ptoldist(POINT p,LINESEG l) 
{ 
return abs(multiply(p,l.e,l.s))/dist(l.s,l.e); 
} 

/* 計算點到折線集的最近距離,并返回最近點. 
注意：調用的是ptolineseg()函數 */ 
double ptopointset(int vcount,POINT pointset[],POINT p,POINT &q) 
{ 
int i; 
double cd=double(INF),td; 
LINESEG l; 
POINT tq,cq; 

for(i=0;i{ 
l.s=pointset[i]; 
l.e=pointset[i+1]; 
td=ptolinesegdist(p,l,tq); 
if(td{ 
cd=td; 
cq=tq; 
} 
} 
q=cq; 
return cd; 
} 
/* 判斷圓是否在多邊形內.ptolineseg()函數的應用2 */ 
bool CircleInsidePolygon(int vcount,POINT center,double radius,POINT polygon[]
) 
{ 
POINT q; 
double d; 
q.x=0; 
q.y=0; 
d=ptopointset(vcount,polygon,center,q); 
if(dreturn true; 
else 
return false; 
} 

/* 返回兩個矢量l1和l2的夾角的余弦(-1 --- 1)注意：如果想從余弦求夾角的話，注意反
余弦函數的定義域是從 0到pi */ 
double cosine(LINESEG l1,LINESEG l2) 
{ 
return (((l1.e.x-l1.s.x)*(l2.e.x-l2.s.x) + 
(l1.e.y-l1.s.y)*(l2.e.y-l2.s.y))/(dist(l1.e,l1.s)*dist(l2.e,l2.s))) ); 
} 
// 返回線段l1與l2之間的夾角 單位：弧度 范圍(-pi，pi) 
double lsangle(LINESEG l1,LINESEG l2) 
{ 
POINT o,s,e; 
o.x=o.y=0; 
s.x=l1.e.x-l1.s.x; 
s.y=l1.e.y-l1.s.y; 
e.x=l2.e.x-l2.s.x; 
e.y=l2.e.y-l2.s.y; 
return angle(o,s,e); 
} 
// 如果線段u和v相交(包括相交在端點處)時，返回true 
bool intersect(LINESEG u,LINESEG v) 
{ 
return( (max(u.s.x,u.e.x)>=min(v.s.x,v.e.x))&& file://排斥實驗 
(max(v.s.x,v.e.x)>=min(u.s.x,u.e.x))&& 
(max(u.s.y,u.e.y)>=min(v.s.y,v.e.y))&& 
(max(v.s.y,v.e.y)>=min(u.s.y,u.e.y))&& 
(multiply(v.s,u.e,u.s)*multiply(u.e,v.e,u.s)>=0)&& file://跨立實驗 
(multiply(u.s,v.e,v.s)*multiply(v.e,u.e,v.s)>=0)); 
} 


// (線段u和v相交)&&(交點不是雙方的端點) 時返回true 
bool intersect_A(LINESEG u,LINESEG v) 
{ 
return((intersect(u,v))&& 
(!online(u,v.s))&& 
(!online(u,v.e))&& 
(!online(v,u.e))&& 
(!online(v,u.s))); 
} 


// 線段v所在直線與線段u相交時返回true；方法：判斷線段u是否跨立線段v 
bool intersect_l(LINESEG u,LINESEG v) 
{ 
return multiply(u.s,v.e,v.s)*multiply(v.e,u.e,v.s)>=0; 
}