基于网格中心点的点在多边形内的高效判定

CORC > 软件研究所 > 软件所图书馆 > 期刊论文

	基于网格中心点的点在多边形内的高效判定
	李静 ; 王文成
刊名	软件学报
	2012
卷号	23 期号:9 页码:2481-2488
关键词	多边形点包容性检测网格中心点
ISSN号	1000-9825
其他题名	point-in-polygon test method based on center points of grid
中文摘要	提出一种基于均匀网格的点在多边形内的高效判定算法.它首先建立均匀网格,并从左至右依次计算每个网格单元中心点的位置属性.每个单元中心点的位置属性直接依据其左侧邻接单元已知位置属性的中心点快速获得.在判定点的位置时,确定被测点所在单元,并依据该单元中心点的位置属性判定被测点的位置属性.由于预处理和判定时均利用邻近点的已知位置属性来确定未知点位置属性,可以很好地进行局部化的计算.因此,新方法比现有方法快很多,并且其预处理时间复杂度也由同类网格算法的O(N3/2)下降为O(N).同时,新方法可以统一处理含有自相交及重叠边的非流形多边形.实验结果表明,相比于其他基于均匀网格的方法,新方法可将预处理的速度提高几倍,将判断计算的速度提高十几到几十倍.其速度甚至优于具有该问题最低判定计算时间复杂度O(logN)的基于凸剖分的判定算法.
英文摘要	The paper proposes an efficient point-in-polygon test method based on uniform grids. In preprocessing, it constructs uniform grids and processes the center points in a sequence to determine whether they are inside the polygon, when the center points with known inclusion properties are used to quickly determine their adjacent center points. When performing an inclusion query, it first finds the cell that contains the query point and then produces a line segment from the query point to the cell's center point and counts the edges crossed by the line segment for determination. As both the preprocessing and the inclusion tests make use of known information to determine the center points or query points, the computation can run locally for acceleration and the new method can run much faster than existing methods. In most cases, it can reduce the preprocessing time complexity from O(N3/2) to O(N)for the methods based on grids, where N is the number of the polygon edges. Meanwhile, the new method can efficiently treat the non-manifold polygons with self-intersection or overlapping edges. Experimental results show at compared with other similar methods based on uniform grids, the new algorithm can speed up the preprocessing by several times and the query computation by one or several dozens of times, and can move faster than the method by convex decomposition, which has the lowest complexity O(logN) for point-in- polygon tests.
学科主题	Computer Science (provided by Thomson Reuters)
收录类别	CNKI ; CSCD ; WANFANG
资助信息	国家自然科学基金(60873182,60773026,60833007)
语种	中文
CSCD记录号	CSCD:4703522
公开日期	2013-09-17
内容类型	期刊论文
源URL	[http://ir.iscas.ac.cn/handle/311060/15397]
专题	软件研究所_软件所图书馆_期刊论文
推荐引用方式 GB/T 7714	李静,王文成. 基于网格中心点的点在多边形内的高效判定[J]. 软件学报,2012,23(9):2481-2488.
APA	李静,&王文成.(2012).基于网格中心点的点在多边形内的高效判定.软件学报,23(9),2481-2488.
MLA	李静,et al."基于网格中心点的点在多边形内的高效判定".软件学报 23.9(2012):2481-2488.