计算几何资料集.docVIP

计算几何资料集 本文档对应的程序库：点击下载 1.1????? 矢量 1.1.1?? 矢量的定义 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。因此在实际使用时，矢量的定义可以和顶点结构一样，而有向线段的定义需要建立在顶点的结构之上。而线段的定义可以和有向线段相同，只是在使用时可以不考虑起点和终点。注意我们现在考虑的几何结构都是二维的，所以点（矢量）、有向线段（线段）也被定义为二维。 //点结构 struct TPoint { double x, y; TPoint(double a=0, double b=0) { x=a; y=b;}//这里为了使用方便，加入构造函数，不用担心，在C++的结构体中，可以插入函数定义。它和class的区别在于其内部的函数都是public类型的。 }; ? //线段结构 struct TLineSeg { TPoint s, e; TLineSeg(TPoint a, TPoint b) { s=a; e=b;} TLineSeg(){} }; 1.1.2?? 矢量加减 矢量的加减对应于三角形法则： 设两个二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则： ????????? 矢量加法定义： P + Q = ( x1 + x2 , y1 + y2 )；即上图中的R ????????? 矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。即上图中的S 显然有性质： ????????? P + Q = Q + P； ????????? P - Q = - ( Q - P )。 下面我们定义两个函数用于矢量的加减： //矢量相加 TPoint Add(TPoint a, TPoint b) { return(TPoint(a.x+b.x,a.y+b.y)); } ? //矢量相减 TPoint Subtract(TPoint a, TPoint b) { return(TPoint(a.x-b.x,a.y-b.y)); } 1.1.3?? 矢量叉积 计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = ( x1, y1 )，Q = ( x2, y2 )，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P × Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。 叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系： ????????? 若 P × Q 0 , 则P（前者）在Q（后者）的顺时针方向。 ????????? 若 P × Q 0 , 则P在Q的逆时针方向。 ????????? 若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向。 下面是两个矢量叉积的函数： /************************************************************************** r=multiply(p1,p2),得到两个矢量p1,p2的叉积 r0:p1（前者）在p2（后者）的顺时针方向； r=0:p1,p2共向； r0:p1在p2的逆时针方向 举个简单的例子，看笛卡尔坐标系下x轴和y轴，分别选(1,0)和(0,1)，得叉积为10，x在y的顺时针方向，即y到x是顺时针方向 ***************************************************************************/ double Multiply(TPoint p1, TPoint p2) { return(p1.x*p2.y-p2.x*p1.y); } 1.2??? 点、线段、矩形、多边形、圆之间的关系 1.2.1?? 折线段的拐向判断 折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向： ????????? 若(p1 - p0)×(p2 - p0) 0,则p0p1在p1点拐向右侧后得到p1p2。 ????????? 若(p1 - p0)×(p2