1、计算几何学朱成名2014/4/18大纲2计算几何的基本工具计算几何的常见问题总结线段方面的问题凸包方面的问题最远 /近点对问题叉积点积3计算几何的基本工具叉积 (向量积 )已知有向线段 op1=(x1,y1),op2 =(x2,y2).op1 op2和 的叉积为：op1 op2几何意义： 是 以 和 为边的平行四边形的有向面积。op1 op2O(0,0)p2(x2,y2)p1(x1,y1)另一种定义：op1 op2 =det x1,x2y1,y2p(x1+x2,y1+y2)= x1y2 x2y1op2 op1= = det x2,x1y2,y1= op1 op2 sin( )。4右手法则可快速
2、判断两个平面向量叉积的 方向 ，继而判断两个向量的 相对位置 关系。O(0,0)p2(x2,y2)p1(x1,y1)op1op2 0，表示 op1到 op2成 逆时针，即 op2在 op1的 左边 。op2op1 0若 op1op2 = 0 ，则表示 op1和 op2共线 (同向或反向 )。O(0,0)p1(x1,y1)p2(x2,y2)共向O(0,0)p1(x1,y1)p2(x2,y2)反向5计算几何的基本工具点积 (数量积 )已知有向线段 op1=(x1,y1),op2 =(x2,y2)。op1 op2和 的点积为：op1 op2几何意义： 是 在 上的投影与 长度的乘积。 op1 op2
3、= op1 cos( ) op2 。op2O(0,0)p1(x1,y1)p2(x2,y2)另一种定义：op1 op2= x1x2 + y1y2= op2 op1cos(2 ) = cos( ） = cos()6大纲计算几何的基本工具计算几何的常见问题总结线段方面的问题凸包方面的问题最远 /近点对问题叉积点积7计算几何的常见问题线段方面的问题1.判断连续线段是向左转还是向右转？O(0,0)p1(x1,y1)p2(x2,y2)计算叉积 op1op2 。右左若 0,即 op2在 op1的左边，因此在 p1点向左转。若 0 ( db （ ad）指向 ad (db)的 前方 )ad db 0 ad db 010判断两条线段是否相交？abdcab ad 与 ab ac 结 果 异号；& cd ca 与 cd cb 结 果 异号return true真有同号假无同号，有 0return false交点是否在线 段上是否return truereturn false是否 还存在 0是否
