计算几何(Computational Geometry),即以计算为主的几何。主要研究几何形体的计算机表示、分析与综合。计算几何在数字可视化、图形学、辅助设计、机器人、地理信息、集成电路、计算机视觉等领域被广泛使用。

1、点

NOIP初赛复习(十三)计算几何基础-少儿编程网

点一般表示成P(x,y),其中x,y为点的坐标。如上图4个点的坐标分别为:

P1(3,2)  P2(-2,-2)  P3(2,4)  P4(4,0)。

过两点可连成一线段,两点之间的距离记为:

NOIP初赛复习(十三)计算几何基础-少儿编程网

假设点的坐标为:

NOIP初赛复习(十三)计算几何基础-少儿编程网

由勾股定理可知:

NOIP初赛复习(十三)计算几何基础-少儿编程网
NOIP初赛复习(十三)计算几何基础-少儿编程网

例如:

NOIP初赛复习(十三)计算几何基础-少儿编程网
NOIP初赛复习(十三)计算几何基础-少儿编程网

2、直线

直线的方程:

一般形式为:ax+by+c=0,或y=kx+b。k称为直线的斜率,b称为截矩。

NOIP初赛复习(十三)计算几何基础-少儿编程网

如上图中,直线L1的方程为:0.75x-y+1=0,L2:y=3,L3:x=4。

直线的斜率:

如上图中,直线L1的斜率为0.75。

特别地:当y1=y2时,斜率k=0(如上图中的L2),

当 x1=x2时,k不存在(如上图中的L3)。

NOIP初赛复习(十三)计算几何基础-少儿编程网

过两点P1,P2可以决定一条直线。斜率为:

NOIP初赛复习(十三)计算几何基础-少儿编程网

而当x1与x2无限接近时,斜率k趋于无穷大,这在编程时要特别小心。

3、向量(矢量)

简单的说,向量(vector)就是有大小有方向的量,如速度、位移等物理量都是向量。

如:有方向的线段,即P1和P2的顺序是有关系的,记为:NOIP初赛复习(十三)计算几何基础-少儿编程网

如果P1是坐标原点,则NOIP初赛复习(十三)计算几何基础-少儿编程网又称为向量P2,如下面示意图。

向量的斜率:既然向量是有方向的,那么向量的斜率k就是有正负之分的,具体如下:

NOIP初赛复习(十三)计算几何基础-少儿编程网

NOIP初赛复习(十三)计算几何基础-少儿编程网 =a,则有向线段NOIP初赛复习(十三)计算几何基础-少儿编程网的长度叫做向量a的长度或模。记作|a|。

夹角:两个非0向量a、b,在空间任取一点O,作NOIP初赛复习(十三)计算几何基础-少儿编程网=a, NOIP初赛复习(十三)计算几何基础-少儿编程网=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点作NOIP初赛复习(十三)计算几何基础-少儿编程网 ,要求NOIP初赛复习(十三)计算几何基础-少儿编程网的模等于|b|,方向与b相反,即NOIP初赛复习(十三)计算几何基础-少儿编程网=-b,则以O为起点、B’为端点的向量称为a与b的差a-b,如下右图。
NOIP初赛复习(十三)计算几何基础-少儿编程网

5、向量的数量积(点乘)

两个向量的数量积是一个数,大小等于这两个向量的模的乘积再乘以它们夹角的余弦。

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|= a·a

结合律:(λ·a)·b = λ(a·b)

交换律:a·b = b·a

分配律:a·(b + c) = a·b + a·c

6、向量的向量积(叉乘、叉积)

向量积的一般含义:两个向量a和b的向量积是一个向量,记作a×b,其模等于由a和b作成的平行四边形的面积,方向与平行四边形所在平面垂直,当站在这个方向观察时,a逆时针转过一个小于π的角到达b的方向。这个方向也可以用物理上的右手螺旋定则判断:右手四指弯向由A转到B的方向(转过的角小于π),拇指指向的就是向量积的方向。如下左图。

NOIP初赛复习(十三)计算几何基础-少儿编程网

我们给出叉积的等价而更有用的定义,把叉积定义为一个矩阵的行列式:

NOIP初赛复习(十三)计算几何基础-少儿编程网

如上右图,如果NOIP初赛复习(十三)计算几何基础-少儿编程网为正数,则相对原点(0,0)来说,NOIP初赛复习(十三)计算几何基础-少儿编程网NOIP初赛复习(十三)计算几何基础-少儿编程网的顺时针方向;如果NOIP初赛复习(十三)计算几何基础-少儿编程网为负数,则NOIP初赛复习(十三)计算几何基础-少儿编程网NOIP初赛复习(十三)计算几何基础-少儿编程网的逆时针方向。如果NOIP初赛复习(十三)计算几何基础-少儿编程网=0,则NOIP初赛复习(十三)计算几何基础-少儿编程网NOIP初赛复习(十三)计算几何基础-少儿编程网模相等且共线,方向相同或相反。

也可以用向量的分解证明:

NOIP初赛复习(十三)计算几何基础-少儿编程网
即:
NOIP初赛复习(十三)计算几何基础-少儿编程网

注:i,j,k分别为x,y,z方向上的单位向量

现在探讨一个重要的问题:给定两个向量:NOIP初赛复习(十三)计算几何基础-少儿编程网NOIP初赛复习(十三)计算几何基础-少儿编程网 ,对它们的公共端点P0来说,判断NOIP初赛复习(十三)计算几何基础-少儿编程网是否在NOIP初赛复习(十三)计算几何基础-少儿编程网的顺时针方向。
NOIP初赛复习(十三)计算几何基础-少儿编程网
方法:如上图,把P0作为原点,得出向量P1’=P1-P0和P2’=P2-P0,因此,这两个向量的叉积为:
NOIP初赛复习(十三)计算几何基础-少儿编程网
如果该叉积为正,则NOIP初赛复习(十三)计算几何基础-少儿编程网NOIP初赛复习(十三)计算几何基础-少儿编程网的顺时针方向,如果为负,则NOIP初赛复习(十三)计算几何基础-少儿编程网NOIP初赛复习(十三)计算几何基础-少儿编程网的逆时针方向。如果等于0,则P0,P1,P2三点共线。

讨论另一个重要问题:确定连续线段是向左转还是向右转,如下图,即两条连续线段NOIP初赛复习(十三)计算几何基础-少儿编程网NOIP初赛复习(十三)计算几何基础-少儿编程网在点P1是向左转还是向右转。也即∠P1P0P2的转向。
NOIP初赛复习(十三)计算几何基础-少儿编程网
方法:叉积,同上。

向量的叉积对于计算几何有着重要的意义,是很多算法的核心。用叉积可以判断从一个向量到另一个向量的旋转方向,可以求同时垂直于两个向量的直线(向量)方向,还能用来计算面积……。

向量的旋转:实际应用中,经常需要从一个向量转到另一个向量,这个过程称为向量的旋转,旋转的方向由叉积判定。很多例子都用到向量的旋转这个方法和相应特性。

7、坐标系中的矩形

NOIP初赛复习(十三)计算几何基础-少儿编程网

若矩形边平行坐标轴,如(a)图,此时给出2个点的坐标:P1(x1,y1),P2(x2,y2),则其它两点坐标为:P3(x2,y1),P4(x1,y2);

若矩形边不平行坐标轴,如(b)图,此时给出三点坐标:P1(x1,y1), P2(x2,y2),P3(x3,y3),则第4点坐标可以推得,利用切割法可以得到:

NOIP初赛复习(十三)计算几何基础-少儿编程网

8、圆

设圆心的坐标为(x0,y0),半径为r。则圆的一般方程为:

NOIP初赛复习(十三)计算几何基础-少儿编程网
NOIP初赛复习(十三)计算几何基础-少儿编程网

若O1(x0,y0)为原点(0,0),则方程为:NOIP初赛复习(十三)计算几何基础-少儿编程网,点与圆的关系:若点为P(x1,y1),代入方程:
若:NOIP初赛复习(十三)计算几何基础-少儿编程网 >r2  ,则P(x1,y1)在圆外;
若:NOIP初赛复习(十三)计算几何基础-少儿编程网=r2  ,则P(x1,y1)在圆上;
若:NOIP初赛复习(十三)计算几何基础-少儿编程网<r2  ,则P(x1,y1)在圆内。

9、多边形面积

在计算几何里,我们知道,△ABC的面积就是“向量AB”和“向量AC”两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。

NOIP初赛复习(十三)计算几何基础-少儿编程网
NOIP初赛复习(十三)计算几何基础-少儿编程网

特别注意:以上得到是有向面积(有正负)!

凸多边形的三角形剖分

以 P1为扇面中心,连接P1Pi就得到N-2个三角形,由于凸性,保证这些三角形全在多边形内,那么,这个凸多边形的有向面积:

A=sigma(Ai)  (i=1…N-2)

NOIP初赛复习(十三)计算几何基础-少儿编程网

任意点为扇心的三角形剖分

以多边形内部的一个点为扇心,就可以把多边形剖分成 N个三角形。

NOIP初赛复习(十三)计算几何基础-少儿编程网

我们可以得到:A=sigma(Ai)  ( i=1…N ),即:

NOIP初赛复习(十三)计算几何基础-少儿编程网

点在多边形内的判定

方法一:射线法

从判定点任意引一条射线,如果和边界的交点是奇数次,说明点在多边形内,如果交点为偶数个,点在多边形外。在多边形上需另外判断。

方法二:转角法

计算多边形每条边的转角的和,如果为360度,则点在多边形内,如果为0度,则在多边形外,如果为180度则点在多边形上(也适合非简单多边形)。

如果按照上面的定义实现,需要计算大量的反三角函数,不仅速度慢,而且容易产生精度误差。我们一般假设一条向右的射线,统计多边形穿过这条射线的正反次数,把这个数记为绕数wn(Winging Number),逆时针穿过是wn++,顺时针穿过wn–。

注意在程序现实的时候,判断是否穿过,以及穿过方向时,需要用叉积判断输入点在边的左边还是右边。

10、计算几何的经典算法—凸包

凸包就是把给定点包围在内部、面积最小的图多边形,它在计算几何里有着极其重要的作用。解决凸包问题一般有:斜率逼近法、数学构造法(Jarvis算法)和Graham算法。

可通过设置一个关于侯选点的堆栈S来解决凸包问题,设输入点集Q中的每个点都被压入堆栈一次,不是凸包中的点最终将被弹出堆栈。当算法终止时,堆栈S中仅包含凸包中的顶点,其从下往上的顺序为各点在边界上出现的逆时针方向排列的顺序。如下图:

NOIP初赛复习(十三)计算几何基础-少儿编程网
NOIP初赛复习(十三)计算几何基础-少儿编程网
NOIP初赛复习(十三)计算几何基础-少儿编程网
NOIP初赛复习(十三)计算几何基础-少儿编程网
NOIP初赛复习(十三)计算几何基础-少儿编程网
NOIP初赛复习(十三)计算几何基础-少儿编程网