1、第 8章 计算几何学 沈云付上海大学计算机工程与科学学院本章主要内容8.1 几何基本知识8.2 基本算法8.3 凸包8.4 实例研究8.1 几何基本知识8.1.1 矢量的概念8.1.2 矢量加减法8.1.3 矢量叉积 8.1.4 折线段的拐向判断8.1.5 判断点是否在线段上8.1.6 跨立试验与判断两线段是否相交8.1.7 整数点与 Pick定理8.1.1 矢量的概念1、 线段设 A(x1,y1)， B (x2,y2)是平面上任意两点线段 AB上的任一点 C (x,y)满足x=x1+(1- )x2y=y1+(1- )y2 012、有向线段 AB（ 向量）： 始点 A， 终点 B 3、给定两个
2、向量 OA和 OB（ 简记 A， B）4、以 O， A， B， A+B为顶点的平行四边形面积OA OB= = x1y2-x2y1= -(OB OA)x1 x2y1 y28.1.2 矢量加减法 设二维矢量 P = ( x1, y1 )， Q = ( x2 , y2 ) 。 矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )。 矢量加法的几何意义是以向量 P、 Q为邻边的平行四边形的对角线 矢量减法定义为： P Q = ( x1 x2 , y1 y2 ) 8.1.3 矢量叉积2、 叉积的性质 ：1、矢量叉积： OA OB定义为以 O， A， B， A+B为顶点的平行四边形
3、的带符号的面积。OA OBAB AC0 OB在 OA的逆时针方向=0 O、 A、 B共线0 AC在 AB的逆时针方向= 0 A、 B、 C共线0AB、 BC在 B处 右转： AB AC 0A、 B、 C三点共线： AB AC 08.1.5 判断点是否在线段上判断点 C在线段 AB上的依据是： 点 C在线段 AB所在的直线 L上， C 在以 A、 B为对角顶点的矩形内。BCA点在线段上的条件ON_SEGMENT算法描述： C点在直线 AB上： AB AC=0 C点不在线段 AB的延长线或反向延长线上：(min(xA,xB) = xC)且 (xC = max(xA,xB) 且 (min(yA,yB) = yC)且 (yC = max(yA,yB)
