62关系判别 2.多边形重叠性检验 假定两个多变形的最小矩形为a和b,左下角和右 上角的坐标分别为: (Bmax, Bmax) Y (amax, Yambx b (Bmin, Bmin) Xamin, Yamin) X 湖北大学数计学院 16
湖北大学数计学院 16 6.2 关系判别 2. 多边形重叠性检验 假定两个多变形的最小矩形为a和b,左下角和右 上角的坐标分别为：
62关系判别 2.多边形重叠性检验 则当a,b两矩形满足下列条件之一时,a和b不重 叠 Xamax<=Bmin Yamax<=bmin Xamin>=Bmax Yamin>=Bmax 当a、b两矩形不满足上述条件,即意味两多边 形可能重叠。此时需通过两多边形的边边求 交来判断是否重叠。当存在交点时,既表明 两多边形重叠,否则不重叠。 湖北大学数计学院 17
湖北大学数计学院 17 6.2 关系判别 2. 多边形重叠性检验 则当a,b两矩形满足下列条件之一时，a和b不重 叠 Xamax<=Xbmin Yamax<=Ybmin Xamin>=Xbmax Yamin>=Ybmax 当a、b两矩形不满足上述条件，即意味两多边 形可能重叠。此时需通过两多边形的边边求 交来判断是否重叠。当存在交点时，既表明 两多边形重叠，否则不重叠
63直线段裁剪 裁剪的目的 判断图形元素是否落在裁剪窗口之内并找出其位于 内部的部分 栽剪的处理的基础 图元关于窗口内外关系的判别 图元与窗口的求交 假定条件 矩形裁剪窗口:mN理nyma 待裁剪线段: 湖北大学数计学院
湖北大学数计学院 18 6.3 直线段裁剪 • 裁剪的目的 – 判断图形元素是否落在裁剪窗口之内并找出其位于 内部的部分 • 裁剪的处理的基础 – 图元关于窗口内外关系的判别 – 图元与窗口的求交 • 假定条件 – 矩形裁剪窗口：[xmin,xmax]X[ymin,ymax] – 待裁剪线段： P x y P x y 0 0 0 1 1 1 ( , ) ( , )
63直线段裁剪 ◆在二维坐标系中,需要在观察坐标系下对窗口进行裁 剪,即只保留窗口内的那部分图形,去掉窗口外的图 形 ◇假设窗口是标准矩形,即边与坐标轴平行的矩形,由 上(y=wyt)、下(y=wyb)、左(x=wx|)、右 (x=wxr)四条边描述 yt 窗 Wy wXr X 湖北大学数计学院 19
湖北大学数计学院 19 6.3 直线段裁剪 ❖ 在二维坐标系中，需要在观察坐标系下对窗口进行裁 剪，即只保留窗口内的那部分图形，去掉窗口外的图 形。 ❖ 假设窗口是标准矩形，即边与坐标轴平行的矩形，由 上 （ y=wyt ） 、 下 （ y=wyb ） 、 左 （ x=wxl ） 、 右 （x=wxr）四条边描述。 x y o wyt wyb wxl wxr 窗口
63直线段裁剪 待裁剪线段和窗口的关系 线段完全可见 显然不可见 ---ym ax 线段至少有一端点在 窗口之外,但非显然 不可见 Xmin Xm ax 为提高效率,算法设计时应考虑: (一)快速判断情形(1)(2); 2c-)设法减少情形3求交次数和每次求交时所需 20
湖北大学数计学院 20 6.3 直线段裁剪 • 待裁剪线段和窗口的关系 – 线段完全可见 – 显然不可见 – 线段至少有一端点在 窗口之外，但非显然 不可见 为提高效率，算法设计时应考虑： (一）快速判断情形(1)(2)； (二) 设法减少情形(3)求交次数和每次求交时所需 的计算量