第十一章 计算几何问题.doc

1 第十一章计算几何问题 引言一、二维平面中的点、线段和多边形 1 、点: 用数偶),(yx 表示点 p 的坐标。 2 、线段: 由它的两个端点表示。如果),( 11yxp?,),( 22yxq?是两个离散的点,端点为 p 和q 的线段,表示为 pq 。 3 、多边形: 多边形路径?是点 nppp,,, 21?的一个序列,其中, 1?iipp 是线段, 11???ni 。如果 npp? 1 ,则由?所封闭起来的区域称为多边形?。 ip 称为多边形的顶点;线段 1?iipp 称为多边形的边。通常用“多边形”来表示多边形的边界。 4 、简单多边形和非简单的多边形: 除了顶点之外,任何两条边都不会交叉的多边形称为简单多边形; 有交叉边的多边形称为非简单的多边形。例:图 (a) 是简单的多边形,图 (b) 是非简单的多边形。图 简单的多边形(a) 和非简单的多边形(b) 5 、凸多边形和非凸多边形凸多边形:连接多边形任意两个顶点的线段,完全处于多边形内部, 非凸多边形:连接多边形任意两个顶点的线段,不完全处于多边形内部例: 图 (a) 表示一个凸多边形,图 (b) 表示一个非凸多边形。 2 图 凸多边形(a) 和非凸多边形(b) 二、有向面积 1 、以源点作为始点的两个向量的有向面积点),( 11yxp?,),( 22yxq?是以源点)0,0(?o 作为始点的两个向量 op及 oq 的端点, 则向量 op及 oq 的有向面积为: op? oq21 21yy xx? 1221yxyx???? oq? op 2 、两向量有向面积的平行四边形表示若过点 p 平行于 oq 的直线与过点 q 平行于 op 的直线相交于 s , sqp,, 的垂线与 X 轴分别相交于 cba,, , 平行四边形 opsq 的面积 S 为: obq ?的面积加上梯形 qbcs 的面积,减去 opa ?的面积,再减去梯形 pacs 的面积。显然, 2xob ac??,1xoa bc??,21yyap bq cs????。221111112222)(2 12 1)(2 12 1xyyyyxxyyyyxS???????? 1221yxyx??图 由两个向量所构成的平行四边形 3 、结论 1) op? oq 的有向面积的绝对值,等于平行四边形 opsq 的面积。 3 2)当 op? oq 值为正时,向量 op 可沿着平行四边形内部逆时针旋转到达 oq ; 3)当 op? oq 值为负时,向量 op 可沿着平行四边形内部顺时针旋转到达 oq 。 4 、左转的三角区和右转的三角区 qpo,, 三点的坐标分别为),(,),(,),( 332211yxyxyx , op),( 1212yyxx???, oq),( 1313yyxx???。 op? oq)()()()( 12131312yyxxyyxx?????? 133221133221xyxyxyyxyxyx??????上述 op? oq 的有向面积,也可用下面的行列式的值来确定: 13322113322133 22 111 1 1xyxyxyyxyxyxyx yx yxD???????( ) 当D 为正时, oqpo,,, 构成一个反时针方向的回路,就说路径 qpo,, 是左转的, 当D 为负时, oqpo,,, 构成一个顺时针方向的回路,就说路径 qpo,, 是右转的, 当0?D 时,这三点在同一直线上。例:图 表示左转的三角区和右转的三角区。图 左转的三角区域( a)和右转的三角区域( b) 二、几何扫描 1 、几何扫描对物体进行扫描,以便确定物体的几何形状、识别物体中各个部件的几何特征及部件之间的联系。 2 、平面几何扫描在二维平面上,对某一个对象从左到右用垂直线进行扫描。三、平面扫描算法的基本组成部分: 1 、事件调度点 schedule p_ 按X 坐标排序的点序,由这些点定义了扫描线的“站点”位置。 2 、扫描线状态, 扫描线的“站点”状态,表示在“站点”位置时,所处理几何对象的状态。扫描线状态的描述,取决于所处理的几何对象。 4 平面线段的交点问题一、问题给定平面上 n 条线段的集合},,,{ 21nlllL??,寻找它们的交点集合。二、平面上线段的关系描述定义 令il 和jl 是平面上任意两条线段, 它们与 X 坐标为 x 的垂线分别相交于点 ip 与jp 。若 ip 的Y 坐标值大于 jp 的Y 坐标值,就说 il 在x 高于 jl ,记为 jxill?。如果线段 il 和jl , 其中有一条、或者两条都不与 X 坐标为 x 的垂线相交, 就说这两条线段不存在 x?关系。例: