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

Improved algorithm to determine topological relationship between point and polygon

作　　者：向俊[1] 王静[2] 夏幼明[3] 

机构地区：[1]广西广播电视大学教学资源与技术中心,广西南宁530022 [2]中国电信集团山东分公司网络中心,山东济南250101 [3]云南师范大学信息学院,云南昆明650092

出　　处：《计算机工程与设计》2014年第5期1732-1737,共6页Computer Engineering and Design

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

摘　　要：为了解决射线法不能有效地判断点在复杂多边形内或外的问题,根据射线与多边形边界相交的特性,分析射线所经过的多边形的不同类型顶点,提出了对顶点数加1、加2和加3的运算方法。通过判断交点个数的奇偶性,改进了射线法,并给出了计算模型和算法的详细步骤,简单有效的将现有的射线法扩展到更复杂的多边形中,能准确的判断点与多边形的位置关系。4种不同算法对比分析结果表明,该算法能解决其它3种算法存在的问题,并且在简单多边形和复杂多边形中都是有效的。To resolve the problem of ray-algorithm can＇t determine whether a point is inside a polygon effectively, according to the characteristic of Ray intersect with bound of polygon, and the type of vertex is analyzed, which is the ray have traversed. The method of adding one, adding two and adding three operations is proposed by determining the parity of the number of inter- sections, and the ray-algorithm is improved. The computational model and the detailed steps of the algorithm execution at the same time, and it is extended are given into the more complexity of polygon simply and effectively. A topological relation between point and polygon is analyzed accurately. It shows that the result of four different algorithms compared, the algorithm can solve the problem of other algorithms, and it is effective to simple and complicated of polygons.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]