关键词: Flooding操作, 多边形, 轮廓腐蚀, 内外点判断, 栅格化

Abstract: 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.

Key words: Flooding operation, Contour erosion, Point in-out test, Polygon, Rasterization