点与含多边形位置关系判断.ppt

点与多边形关系判断 用过点的垂直线与多边形交点分布的奇偶特性判别多边形与点的关系。若两侧交点个数均为奇数，则可判断点位于多边形内，若与某一侧个数为偶数，则可判断点位于多边形外。 从待判断的点向某一个方向（左方向）引射线，计算和多边形交点的个数，如果个数是偶数或者0则点在多边形外，如果是奇数，则在多边形内。这个只是最基本的判别情况，还有一些复杂的情况需要特殊处理*特殊情况1、射线经过顶点：当射线经过顶点时，判断就会出现异常情况，现在规定，线段的两个端点，相对于另一个端点在上面的顶点称为上端点，下面是下端点，如果经过下端点，则认为边和射线不相交。2、点在边上：这种情况也不能用交点个数的奇偶性来判断了，要快速地判断这个点是否在边上。3、射线法改进：传统的射线法一开始就直接计算点和多边形的交点个数，这样的话，会花费大量的时间来作拓扑关系的判断。改进的算法是首先利用多边形的最小外接矩形迅速排出掉不在MBR内的点，然后利用交点个数的奇偶性判断* 通过过目标点做水平左射线来考虑目标点与多边形一条边的关系 射线和线段的关系?:相交返回1，不相交返回0，射线起点在线段上返回-1??IsIntersectAnt*-100-10**谢谢