作　　者： ; ; ;

机构地区： 中国科学院沈阳自动化研究所

出　　处： 《机械工程学报》 2006年第3期130-135,共6页

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

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

领　　域： [自动化与计算机技术] [自动化与计算机技术]