在这里整理了一下自己找的资料,和《算法导论》,为了在学习中能够更清晰,同时还可以方便以后的回顾。
http://www.cnblogs.com/jbelial
计算几何的基础——矢量
矢量分析是高等数学的一个分支,主要应用于物理学(如力学分析)。在一些计算几何问题中,矢量和矢量运算的一些独特的性质往往能发挥出十分突出的作用,使问题的求解过程变得简洁而高效。熟练掌握一些矢量分析的方法,并灵活地加以运用,就能轻松地解决许多看似复杂的计算几何题,或者会对我们解这类题目有很大帮助,甚至还有一些计算几何题是非用矢量方法不能解决的。
1、直线
①直线的方程:
一般形式为:ax+by+c=0,或y=kx+b。k 称为直线的斜率,b 称为截矩。
特例:若a≠0,则一般方程可为:x+by+c=0;若b≠0,则一般方程可为:ax+y+c=0。
②直线的斜率:
如下图:过两点P1,P2可以决定一条直线。斜率为:
③两条直线垂直,则它们的斜率乘积等于-1。
2、线段
① 凸组合:两个不同的点P1(x1,y1)、P2(x2,y2)的凸组合是满足下列条件的点P3(x3,y3):
对某个0≤σ≤1,有x3=σx1+(1-σ)x2,y3=σy1+(1-σ)y2
一般也可以写成:P3=σP1+(1-σ)P2
直观上看,P3 通过直线P1P2,并且处于P1 和P2 之间(也包括P1,P2 两点)的任意点。
② 线段:线段P1P2是两个相异点P1,P2 的凸组合的集合,其中P1,P2 称为线段的端点
3、向量(矢量)的概念
①矢量:有方向的线段,即P1 和P2 的顺序是有关系的,记为:P1P2
如果P1 是坐标原点,则P1P2又称为向量P2,如下面的矢量示意图。
②矢量的斜率:既然矢量是有方向的,那么矢量的斜率k 就是有正负之分的,具体如下:
③设OA=a,则有向线段OA的长度叫做向量(矢量)a 的长度或模。记作|a|。
④夹角:两个非0 矢量a、b,在空间任取一点O,作OA=a,OB =b,则角∠AOB 叫做矢量a 与b 的夹角,记作<a,b>。若<a,b>=π/2,则称a 与b 互相垂直,记作a⊥b。
4、矢量的加减法
以点O 为起点、A 为端点作矢量a,以点A 为起点、B 为端点作矢量b,则以点O 为起点、B为端点的矢量称为a 与b 的和a+b,如下中图。
从A 点作AB',要求AB'的模等于|b|,方向与b相反,即AB' =-b,则以O为起点、B’为端点的矢量称为a 与b 的差a-b,如下右图。
5、矢量的分解
定理:如果空间三个矢量a,b,c 不共面,那么对任一矢量p,一定存在一个且仅一个有序实数组x,y,z,使得:p=xa+yb+zc。
含义与物理上的合力和力的分解一样。
6、矢量的数量积(点乘)
两个矢量的数量积是一个数,大小等于这两个矢量的模的乘积再乘以它们夹角的余弦。
a·b=|a||b|cos<a,b>
用上面讲到的矢量的分解可以证明,数量积等于两个矢量的对应支量乘积之和。
a·b=axbx+ayby+azbz
数量积的性质:
① a·e=|a||e|cos<a,e>=|a|cos<a,e>
② a⊥b 等价于a·b=0,即axbx+ayby+azbz=0
③ 自乘:|a|2= a·a
④ 结合律:(λ·a)·b= λ(a·b)
⑤ 交换律:a·b = b·a
⑥ 分配律:a·(b +c) = a·b + a·c
7、、矢量的矢量积(叉乘、叉积)
① 矢量积的一般含义:两个矢量a和b 的矢量积是一个矢量,记作a×b,其模等于由a 和b作成的平行四边形的面积,方向与平行四边形所在平面垂直,当站在这个方向观察时,a 逆时针转过一个小于π的角到达b 的方向。这个方向也可以用物理上的右手螺旋定则判断:右手四指弯向由A 转到B 的方向(转过的角小于π),拇指指向的就是矢量积的方向。如下图(左)。
② 我们给出叉积的等价而更有用的定义,把叉积定义为一个矩阵的行列式:
如上右图,如果 p1 × p2 为正数,则相对原点(0,0)来说, p1 在p 2 的顺时针方向; 如果p 1 × p2为负数,则p 1 在p 2 的逆时针方向。如果p 1× p2 =0,则p 1 和p 2 模相等且共线,方向相同或相反。
③ 给定两个矢量:P0P1和P0P2,对它们的公共端点P0来说,判断P0P1是否在P0P2的顺时针方向。
方法:如上图,把0 p 作为原点,得出向量P1’=P1-P0 和P2’=P2-P0,因此,这两个向量的叉积为:
④ 讨论另一个重要问题:确定连续线段是向左转还是向右转,如下图,即两条连续线段P0P1
和P1P2在点P1 是向左转还是向右转。也即∠P1P0P2的转向。
方法:叉积,同上。
计算几何的基本算法:
1、两点间的线段长度,P1(x1,y1),P2(x2,y2)
2、已知2 点P1(X1,Y1),P2(X2,Y2),求直线P1P2 的斜率
k=(y2-y1)/(x2-x1);
3、求过P1(x1,y1),P2(x2,y2)的直线方程ax+by+c=0
有以下的3 种情况:
① x1=x2,不存在k,此时方程为:x=x1
② y1=y2,k=0,此时方程为:y=y1
③ 一般地,若x1≠x2且y1≠y2,由方程一般形式x+by+c=0代入:
4、已知两条不平行的直线P1P2 ,P3P4,求交点P5首先判断这两条直线是否平行或重合,
再解下面的二元一次方程:
procedureGetJiao(p1,p2,p3,p4:pointtype; var p5:pointtype);
vara1,b1,c1,a2,b2,c2,d:extended;
begin
getline(p1.x,p1.y,p2.x,p2.y,a1,b1,c1);{求直线方程}
getline(p3.x,p3.y,p4.x,p4.y,a2,b2,c2);
if (a1=0) and (a2=0) or (b1=0) and (b2=0) then exit;{两个特例}
{表示两条直线分别平行于X 轴或Y 轴}
if (b1<>0) and (b2<>0) and (a1/b1=a2/b2) thenexit;
{表示两条直线斜率相等,即平行}
a1:=p1.y-p2.y; b1:=p2.x-p1.x; c1:=p1.x*p2.y-p2.x*p1.y;
a2:=p3.y-p4.y; b2:=p4.x-p3.x; c2:=p3.x*p4.y-p4.x*p3.y;
d:=a1*b2-a2*b1;
p5.x:=(b1*c2-b2*c1)/d; {交点坐标}
p5.y:=(c1*a2-c2*a1)/d;
end;
5、判断两条线段P1P2 ,P3P4 是否相交
方法1:只要在4 的基础上,加上一个判断,看交点是否在线段P1P2 ,P3P4 上。
function judgejiao(var p1,p2,p3,p4):Boolean;
var p:pointtype;
begin
getjiao(p1,p2,p3,p4,p); {求交点}
if min(p1.x,p2.x)<=p.x<=max(p1.x,p2.x) and min(p1.y,p2.y)<=p.y<=max(p1.y,p2.y)
andmin(p3.x,p4.x)<=p.x<=max(p3.x,p4.x) and min(p3.y,p4.y)<=p.y<=max(p3.y,p4.y)
then jiao:=true {判断在线段内}
else jiao:=false;
end;
方法2:用叉积去做,分两步:
第1 步:快速排斥试验,如果分别以P1P2 ,P3P4 为对角线做矩形,而这两个矩形不相交,则这两条线段肯定不相交,如下左图;即使两个矩形相交,这两条线段也不一定相交,如下右图,这时再用第2 步判断;
表示成语句,即两个矩形相交当且仅当下列式子为真:
(max(x1,x2)≥min(x3,x4))∧ (max(x3,x4)≥min(x1,x2)) ∧(max(y1,y2)≥min(y3,y4))∧(max(y3,y4)≥min(y1,y2))
两个矩形相交必须在两个方向上都相交,式子的前半部分判断在x 方向上是否相交,后半部分判断在y 方向上是否相交。
第2 步:确定每条线段是否“跨立”另一条线段所在的直线。
跨立:如果点P1 处于直线P3P4的一边,而P2处于该直线的另一边,则我们说线段p1p2跨立直线P3P4,如果P1 或P2 在直线P3P4 上,也算跨立。
两条线段相交当且仅当它们能够通过第1 步的快速排斥试验,并且每一条线段都跨立另一条线段所在的直线。
具体第2 步的实现,只要用叉积去做就可以了,即只要判断矢量p1p3和p1p4是否在p1p2的两边相对的位置上,如果这样,则线段p1p2跨立直线P3P4。也即检查叉积(P3-P1)×(P2-P1)与(P4-P1)×(P2-P1)的符号是否相同,相同则不跨立,线段也就不相交,否则相交。
当然也有一些特殊情况需要处理,如任何一个叉积为0,则P3 或P4 在直线P1P2 上,又因为通过了快速排斥试验,所以下图左边的情况是不可能出现的,只会出现右边的两种情况。当然,还会出现一条或两条线段的长度为0,如果两条线段的长度都是0,则只要通过快速排斥试验就能确定;如果仅有一条线段的长度为0,如p3p4的长度为0,则线段相交当且仅当叉积(P3-P1)×(P2-P1)。
SEGMENTS-INTERSECT(P1,P2,P3,P4)
1 d1 ← DIRECTION ( p2,p4,p1 )
2 d2 ← DIRECTION ( p3,p4,p2 )
3 d3 ← DIRECTION ( p1,p2,p3 )
4 d4 ← DIRECTION ( p1,p2,p4 )
5 if ( ( d1 > 0 and d2 < 0 ) or( d1 < 0 and d2 > 0 ) ) and
((d3 > 0 and d4 < 0 ) or ( d3 < 0 and d4 >0 ))
6 then return TRUE
7 else if ( d1 = 0 and ON-SEGMENT (p3 , p4 , p1 ) )
8 then return TRUE
9 else if ( d2 = 0 and ON-SEGMENT (p3 , p4 , p2 ) )
10 then return TRUE
11 else if ( d3 = 0 and ON-SEGMENT ( p1 , p2 , p3 ) )
12 then return TRUE
13 else if ( d4= 0 and ON-SEGMENT ( p1 , p2 , p4) )
14 then return TRUE
15 else return FALSE
DIRECTION( pi , pj , pk)
1 return (pj - pi) * ( pk - pi ) ;
ON-SEGMENT ( pi , pj , pk )
1 if ( min (xi , xj) <= xk <=max (xi , xj) and min(yi , yj) <= yk <= max(yi , yj ) )
2 then retrun TRUE
3 else return FALSE
6、已知直线ax+by+c=0,求点P1(x1,y1)关于此直线的对称点P2(x2,y2)。
首先线段P1P2的中点在L1 上,所以得出方程1:a*(x1+x2)/2+b(y1+y2)/2+c=0。
对于L1,y=-ax/b-c/b,所以k1=-a/b,对于L2,k2=(y2-y1)/(x2-x1) ,再利用L1 和L2 的斜率乘积等于-1,
得出方程2:a(y2-y1)-b(x2-x1)=0。,对于方程1 和方程2 利用消元法,解方程组即可求出x2 和y2。
7、判断两点P3和P4是否在直线P1P2的异侧
用叉乘和矢量的旋转,如果a×b 和a×c 的方向一致,则P3 和P4是在a 的同侧,否则在异侧。
8、求点p 到直线ab 的距离
9、已知3 点P1(X1,Y1),P2(X2,Y2),P3(X3,Y3),求三角形P1P2P3 的面积
方法1:用海伦公式
方法2:矢量的叉积
因为:
所以:S三角形 = S平行四边形/2;
联系客服