线点包容检测算法

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

Algorithm for Point and Line in Polygon Test

A convenience algorithm for point and line in polygon test,sloping line method is provided,the characteristic of this method is that the sloping line is not match together with any peak or edge of polygon,no special situation is needed processing,the computation is decreased.The prepared algorithm of line in polygon is not perfect,a new algorithm is presented.First,identify whether there are crossing points in line and polygon by a quick method,if there are crossing points,calculate the crossing points of line and polygon,put these points in order,and then make the line into several segments by these crossing points.If there is not crossing point,the line is only one segment.Test the center of every segment in polygon.If its center is in the polygon,then this segment is in the polygon,else,it is not.This algorithm is simple and effective in programming,and it is suitable for most case.