point-in-polygon test method based on center points of grid

ISCAS OpenIR

	point-in-polygon test method based on center points of grid
	Li Jing; Wang Wen-Cheng
	2012
发表期刊	Ruan Jian Xue Bao/Journal of Software
ISSN	1000-9825
卷号	23 期号:9 页码:2481-2488
摘要	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(N^3/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 that 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. © 2012 ISCAS.; 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(N^3/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 that 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. © 2012 ISCAS.
收录类别	EI
关键词	Computer Software Software Engineering
部门归属	(1) State Key Laboratory of Computer Science Institute of Software The Chinese Academy of Sciences Beijing 100190 China
语种	中文
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/15186
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Li Jing,Wang Wen-Cheng. point-in-polygon test method based on center points of grid[J]. Ruan Jian Xue Bao/Journal of Software,2012,23(9):2481-2488.
APA	Li Jing,&Wang Wen-Cheng.(2012).point-in-polygon test method based on center points of grid.Ruan Jian Xue Bao/Journal of Software,23(9),2481-2488.
MLA	Li Jing,et al."point-in-polygon test method based on center points of grid".Ruan Jian Xue Bao/Journal of Software 23.9(2012):2481-2488.