计算几何基础篇

　　　　在这里整理了一下自己找的资料，和《算法导论》，为了在学习中能够更清晰，同时还可以方便以后的回顾。

　　　　　　　　　　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在P0P2的顺时针方向，如果为负，则P0P1在P0P2的逆时针方向。如果等于0，则P0，P1，P2三点共线。

④ 讨论另一个重要问题：确定连续线段是向左转还是向右转，如下图，即两条连续线段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首先判断这两条直线是否平行或重合，

再解下面的二元一次方程：

procedure GetJiao(p1,p2,p3,p4:pointtype; var p5:pointtype);

var a1,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) then exit;

{表示两条直线斜率相等，即平行}

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)

and min(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）。