计算几何基础培训课程.ppt

计算几何初步 第一单元 线 段 属 性 向量及其运算 计算几何中经常使用向量，而且基本上都是二维的，下面用αβγ代表三个向量 α=(x[0],y[0]) β=(x[1],y[1]) γ=(x[2],y[2]) 某些题目需要经常使用向量运算，因此对于这类问题最好建立构造类型或者类来表示向量，并将向量之间的运算进行重载 一般需要重载加法，减法，和向量乘法 向量及其运算 struct point{ //构造点的数据类型，也可作向量使用 double x; double y; }v1,v2; point operator+(point p1,point p2); double operator*(point p1,point p2); 向量及其运算 向量有两种乘法，内积（数量积，点积）和外积（向量积，叉积），一般是要根据题目需要选择其中一个重载，多数情况是重载外积，其中 内积α·β= x[0]*x[1] + y[0]*y[1] 外积α×β= x[0]*y[1] – x[1]*y[0]= 向量及其运算 内积的几何意义：α在β的投影α’与β的长度乘积 外积的几何意义：α和β所张成的平行四边形的有向面积 外积在计算几何的题目当中经常使用 外积的应用 判断外积的符号，右手定则 如图，α×β0，β×α0 如果α×β== 0 则等价于两个向量共线（同向或反向），可以用此判断三点共线问题。当然，这里的==0在实际编程的时候要用一个精度来控制 外积的应用 考察右图有向线段P1P2 “向右拐” 得到P2P3有向线段P1P2 “向左拐” 得到P2P4可以利用外积判断“拐向”，这在求凸包时会用到 判断点在直线上 利用三点共线的等价条件α×β== 0 直线上取两不同点P1,P2，若点P在直线上，则fabs((P1 - P) × (P2 - P )) eps 如果该题目需要编写求三角形面积的函数，那直接判断这三个点形成的三角形面积是否eps 判断点在线段上 判断点P(x,y)是否在线段P1P2上，其中P1(x1,y1),P2(x2,y2) 需要验证两条 （1）点P在P1P2所在直线上，即三点共线 （2）点P在P1P2为对角线的矩形内 其中（2）利用min(x1,x2)=x=max(x1,x2) min(y1,y2)=y=max(y1,y2) 判断两线段是否相交 判断P1P2是否和P3P4相交，其中Pi坐标为(xi,yi)，同样需要满足两个条件 （1）快速排斥试验：以P1P2为对角线的矩形S1是否和以P3P4为对角线的矩形S2相交，即min(x1,x2)=max(x3,x4) min(x3,x4)=max(x1,x2) min(y1,y2)=max(y3,y4) min(y3,y4)=max(y1,y2) 判断两线段是否相交（续） 判断两线段是否相交： 　我们分两步确定两条线段是否相交： 　　(1)快速排斥试验 　　　　设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。 (2)跨立试验　　　　如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) = 0。同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) = 0。 第二单元 多边形面积 、重心及其他 基本问题（1）： 给定一个简单多边形，求其面积。 输入：多边形（顶点按逆时针顺序排列） 输出：面积S 思考如下图形： Any good idea? 先讨论最简单的多边形——三角形 三角形的面积： 在解析几何里， △ABC的面积可以通过如下方法求得： 点坐标 = 边长 = 海伦公式 = 面积 思考：此