论文部分内容阅读
提出了基于法线方向的点包容检测算法。过待定点作一射线,此射线可能与多边形的某几条边有交点,从待定点向这条边的两端点作两个向量,求这两向量的法线方向。对法线方向进行计数,若法线方向为正向,将计数器加1;若法线方向为反向,将计数器减1。当法线方向的正反次数相同时,待定点在多边形外,否则在多边形内。此算法避免了某些算法的错误,计算量小,复杂度为O(n),简单易行。通过软件实验验证可知,算法简单有效、稳定可靠,对简单多边形、自相交多边形及带孔多边形等多类情况同样适用。