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

夏仁波1, 2  刘伟军1  王越超1

(1．中国科学院沈阳自动化研究所  沈阳  110016；2．中国科学院研究生院  北京  100039)

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

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

中图分类号：TP391.4

国家863计划资助项目(2002AA420060-1)。20050120收到初稿，20050631收到修改稿