点在平面多边形内外的判断方法

在诸多研究领域中,判断点是否在多边形内是一个非常基本的问题。首先分析了解决这一问题的传统方法, 然后提出一种边界代数跟踪法对多边形进行栅格化,在此基础上设计出Flooding操作和轮廓腐蚀算法进行多边形内外点的判断。试验结果表明该方法具有健壮性好、适用于任意复杂多边形而无需对奇异情况进行单独处理等优点。

METHOD FOR DETERMINING WHETHER A CERTAIN POINT IS INSIDE A POLYGON IN PLANE

A very natural problem in many research fields is to determine whether a certain point is located inside a given arbitrary polygon. First, some well-known algorithms are analyzed to answer this question. Then, based on the rasterization of polygon by boundary algebra tracing technique, designing the Flooding operation which is similar to the ideas of seed fill, and combining the contour erosion algorithm, a new algorithm is proposed to decide whether a point is in a simple polygon, a self-intersected polygon and a ring. Experimental results demonstrate that the new algorithm is robust and is valid for any kind polygon without need of peculiar cases processing.