简单多边形包含性检验的算法 1.〔准备)xn←0，yn←y0,m仁-1，i←0； 2.〔排除必不相交情形〕若下列条件有一个成立，则 到4。 2.1p<x;并且p<x+1 2.2Xp≥x;并且p≥x+1； 2.3yp<y:并且yp<y1+1 3.〔计算交点〕yy:+(xp-x)(y+1yi)/(x+1x),分 二种情形： (1)若y=yp,则点P在多边形边界上，算法结束； (2)若y<yp",则m←(-1)m; 4.〔结束判断)i←i+1,若i<n",则返回到2，否则算法 结束，此时若m=-1则点P在多边形外部，m=1则在内部。简单多边形包含性检验的算法 1.〔准备〕xn←x0,yn←y0,m←-1,i←0; 2.〔排除必不相交情形〕若下列条件有一个成立,则 到4。 2.1 xp<xi并且xp<xi+1: 2.2 xp≥xi并且xp≥xi+1; 2.3 yp<yi并且yp<yi+1; 3.〔计算交点〕y=yi +(xp-xi )(yi+1-yi)/(xi+1-xi ),分 二种情形: (1)若y=yp,则点P在多边形边界上,算法结束; (2)若y<yp",则m←(-1)•m; 4.〔结束判断〕i←i+1,若i<n",则返回到2,否则算法 结束,此时若m=-1则点P在多边形外部,m=1则在内部