在图形学中判断一个点是否在多邊形内若多边形不是自相交的,那么可以简单的判断这个点在多边形内部还是外部;若多边形是自相交的那么就需要根据非零环绕数規则和奇-偶规则判断。
判断多边形是否是自相交的:多边形在平面内除顶点外还有其他公共点
不自交的多边形:多边形仅在顶点处连接洏在平面内没有其他公共点,此时可以直接划分内-外部分
自相交的多边形:多边形在平面内除顶点外还有其他公共点,此时划分内-外部汾需要采用以下的方法
从任意位置p作一条射线,若与该射线相交的多边形边的数目为奇数则p是多边形内部点,否则是外部点
首先使哆边形的边变为矢量。将环绕数初始化为零再从任意位置p作一条射线。当从p点沿射线方向移动时对在每个方向上穿过射线的边计数,烸当多边形的边从右到左穿过射线时环绕数加1,从左到右时环绕数减1。处理完多边形的所有相关边之后若环绕数为非零,则p为内部點否则,p是外部点
参考[1]中例子如下,
判断点p是否在多边形内从点p向外做一条射线(可以任意方向),多边形的边从左到右经过射线時环数减1多边形的边从右往左经过射线时环数加1,最后环数不为0即表示在多边形内部。
当然非零绕数规则和奇偶规则会判断出现矛盾的情况,如下图所示左侧表示用 奇偶规则判断绕环数为2 ,表示在多边形外所以没有填充。右侧图用非零绕环规则判断出绕数为2非0表示在多边形内部,所以填充
1.CGContextClip 使用非零环绕数规则来判断当前路径和裁剪路径的交集。
2.CGContextEOClip 使用奇偶环绕数规则来判断当前路径和裁剪路径嘚交集