点包容性检测

Algorithm for Point in Polygon

介绍了一个易于实现的点包容性检测算法——倾斜射线法,其特点是射线不会与多边形的顶点或边重合,无须作特殊情况的处理,需计算的区域小,因而计算量小。判断倾斜射线与多边形的交点数,如果交点数为奇数,则点在多边形内,否则,点在多边形外。验证表明,此算法简单有效、稳定可靠,对自相交多边形及带孔多边形等情况同样适用。

The traditional algorithm for checking point in polygon is not convenience, then a convenience algorithm sloping line method is presented. The characteristic of this algorithm is that the sloping line did not match together with any vertex or edge of polygon, no special situation needs to deal with, the computation time is decreased. First, to make a sloping line from point, and then to count its crossing points with polygon, if the amount of crossing points is odd, then the point is in polygon, otherwise, the point is out of polygon. It is proved that this algorithm is an effective and robust one, and suitable for most cases.