判断点与多边形拓扑关系的改进算法

摘要：

为了解决射线法不能有效地判断点在复杂多边形内或外的问题,根据射线与多边形边界相交的特性,分析射线所经过的多边形的不同类型顶点,提出了对顶点数加1、加2和加3的运算方法.通过判断交点个数的奇偶性,改进了射线法,并给出了计算模型和算法的详细步骤,简单有效的将现有的射线法扩展到更复杂的多边形中,能准确的判断点与多边形的位置关系.4种不同算法对比分析结果表明,该算法能解决其它3种算法存在的问题,并且在简单多边形和复杂多边形中都是有效的.

关键词：多边形、点、点与多边形位置、射线法、拓扑关系

所属期刊栏目：35

分类号：TP391(计算技术、计算机技术)

资助基金：2011广西教育厅科研基金项目201106LX868、201106LX864;广西电大中青年基金项目2012ZQN06

在线出版日期：2014-06-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：1732-1737