计算几何-基础篇

　　　　　　　数学工具越高级，解决问题就越高效。

-------------------------------------------华丽的分割线-----------------------------------------------

计算几何的基础——矢量

矢量分析是高等数学的一个分支，主要应用于物理学（如力学分析）。在一些计算几何问题中，矢量和矢量运算的一些独特的性质往往能发挥出十分突出的作用，使问题的求解过程变得简洁而高效。熟练掌握一些矢量分析的方法，并灵活地加以运用，就能轻松地解决许多看似复杂的计算几何题，或者会对我们解这类题目有很大帮助，甚至还有一些计算几何题是非用矢量方法不能解决的。

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在p2的顺时针方向； 如果p1×p2为负数，则p1在p2的逆时针方向。如果p1×p2=0，则p1和p2模相等且共线，方向相同或相反。

③ 给定两个矢量：P0P1和P0P2，对它们的公共端点P0来说，判断P0P1是否在P0P2的顺时针方向。

方法：如上图，把0p作为原点，得出向量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);{求交点}

ifmin(p1.x,p2.x)<=p.x<=max(p1.x,p2.x)andmin(p1.y,p2.y)<=p.y<=max(p1.y,p2.y)

andmin(p3.x,p4.x)<=p.x<=max(p3.x,p4.x)andmin(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)

1d1←DIRECTION ( p2,p4,p1 )

2d2←DIRECTION ( p3,p4,p2 )

3d3←DIRECTION ( p1,p2,p3 )

4d4←DIRECTION ( p1,p2,p4 )

5if ( ( d1 > 0 and d2 < 0 ) or ( d1 < 0 and d2 > 0 ) ) and

((d3 > 0 and d4 < 0 ) or ( d3 < 0 and d4 > 0 ))

6then return TRUE

7else if ( d1 = 0 and ON-SEGMENT ( p3 , p4 , p1 ) )

8then return TRUE

9else if ( d2 = 0 and ON-SEGMENT ( p3 , p4 , p2 ) )

10then return TRUE

11else if ( d3 = 0 and ON-SEGMENT ( p1 , p2 , p3 ) )

12then return TRUE

13else if ( d4= 0 and ON-SEGMENT ( p1 , p2 , p4) )

14then return TRUE

15else return FALSE

DIRECTION( pi , pj , pk)

1return (pj - pi) * ( pk - pi ) ;

ON-SEGMENT ( pi , pj , pk )

1if ( min (xi , xj) <= xk <= max (xi , xj) and min(yi , yj) <= yk <= max(yi , yj ) )

2then retrun TRUE

3else 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；