Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (29): 49-51.DOI: 10.3778/j.issn.1002-8331.2009.29.014

• 研究、探讨 • Previous Articles     Next Articles

Point-in-polygon analysis based on trapezoidal decomposition

CUI Can1,WANG Jie-chen2,SHEN Ding-tao3   

  1. Department of Geographic Information Science,Nanjing University,Nanjing 210093,China
  • Received:2008-11-11 Revised:2009-01-19 Online:2009-10-11 Published:2009-10-11
  • Contact: CUI Can

借助梯形分割的点面包含分析

崔 璨1,王结臣2,沈定涛3   

  1. 南京大学 地理信息科学系,南京 210093
  • 通讯作者: 崔 璨

Abstract: Point-in-polygon analysis has a broad range of application in many research fields.Firstly,some existing methods determining whether a point is in a polygon have been analyzed,and then,a new algorithm that based on the trapezoidal decomposition has been proposed.This algorithm decomposes the polygons into a series of trapezoidal units,so that the point-in-polygon analysis has been transformed into the problem of determining whether a point is in a trapezoidal unit.This method has already been applied to a GIS platform software,and the test results prove that this algorithm is of great stability and reliability.Moreover,it can be adapted to any complex polygons(with inner hole),with no need to process the abnormal conditions.

Key words: trapezoidal decomposition, point-in-polygon analysis, spatial analysis, geographic information system

摘要: 在诸多研究领域中,判断点是否在多边形内是一个非常基本的问题。在分析了解决这一问题的传统方法基础上,提出了一种基于梯形分割的点面包含算法。该算法将多边形分割成若干个梯形网格单元,将判断点是否位于多边形内的问题转化为判断点是否位于梯形网格单元中这一问题。算法已用于GIS平台软件相应的包含分析模块,试验结果证明该算法稳定可靠、适用于任意复杂多边形而无需对奇异情况进行单独处理。

关键词: 梯形分割, 点面包含分析, 空间分析, 地理信息系统

CLC Number: