线点包容检测算法

摘要

提出的算法是先以快速的方法判断线与多边形是否有交点,如有,则求出线与多边形的各个交点,将交点进行排序,将此线按交点顺序分为多段;如果无交点,则此线只有一段.检测各段中点是否位于多边形内,如果位于内部,则此段在内,否则此段在外.以倾斜射线法检测点的包容性,其特点是此射线不与多边形的顶点或边重合,无须作特殊情况的处理,计算区域小,因而计算量小,对自相交多边形及带孔多边形等多类情况同样适用.通过编写程序计算验证表明,此算法简单有效、稳定可靠,适用于多类情况.