62关系判别 1.点的包含性检验 因此,可用如下判别式判断夹角的方向: =|7=(x-xn)*y1-yn)-(x +1~X。)* y P 当1>0时,为逆时针方向 当T<0时,为顺时针方向 交点数判别法 B C B A D A E E 湖北大学数计学院
湖北大学数计学院 11 6.2 关系判别 1. 点的包含性检验 因此，可用如下判别式判断夹角的方向： 当T>0时，为逆时针方向； 当T<0时，为顺时针方向。 交点数判别法 (x - x )*(y - y ) (x - x )*(y ) i p i 1 p i 1 p i p T = − − y + + A B C D E A B C D E
62关系判别 1.点的包含性检验 交点数法所利用的原理: 由P点向任一方向作一条射线,然后求出该射 线与多边形边的交点数。则有: 1)当交点数为偶数(0)时,则说明点P在多 边形外; 2)当交点数为奇数时,则说明点P在多边形 内。 为处理简单,通常射线的与坐标轴平行 湖北大学数计学院
湖北大学数计学院 12 6.2 关系判别 1. 点的包含性检验 交点数法所利用的原理： 由P点向任一方向作一条射线，然后求出该射 线与多边形边的交点数。则有： 1）当交点数为偶数（0）时，则说明点P在多 边形外； 2）当交点数为奇数时，则说明点P在多边形 内。 为处理简单，通常射线的与坐标轴平行
62关系判别 1.点的包含性检验 奇异情况处理: 即当射线穿过多边形顶点时的特殊处理。 D E 当射线穿过的顶点两边在射线两侧,此时认 为相交一次。而在同侧时,则认为相交两次。 湖北大学数计学院 13
湖北大学数计学院 13 6.2 关系判别 1. 点的包含性检验 奇异情况处理： 即当射线穿过多边形顶点时的特殊处理。 当射线穿过的顶点两边在射线两侧，此时认 为相交一次。而在同侧时，则认为相交两次
62关系判别 2.多边形重叠性检验 通常采用“最小最大试验法”,也称为“排斥 试验法”。这种方法可迅速排除掉不可能相 互重叠的情况,从而减少计算工作量,加快 图形处理速度。 1)多边形的最小包含矩形 是指平面上能包含多边形的最小的矩形。如 下图所示。 最小包含矩形 湖北大学数计学院
湖北大学数计学院 14 6.2 关系判别 2. 多边形重叠性检验 通常采用“最小最大试验法”，也称为“排斥 试验法”。这种方法可迅速排除掉不可能相 互重叠的情况，从而减少计算工作量，加快 图形处理速度。 1）多边形的最小包含矩形 是指平面上能包含多边形的最小的矩形。如 下图所示。 最小包含矩形
62关系判别 2.多边形重叠性检验 2)重叠性检验 利用最小包含矩形,可排除两个多边形不重 叠情况。 如果两个多边形的最小包含矩形,不发生重叠, 则这两个多边形必不重叠。 湖北大学数计学院 15
湖北大学数计学院 15 6.2 关系判别 2. 多边形重叠性检验 2）重叠性检验 利用最小包含矩形，可排除两个多边形不重 叠情况。 如果两个多边形的最小包含矩形，不发生重叠， 则这两个多边形必不重叠