Point-in-polygon tests by determining grid center points in advance

ISCAS OpenIR

	Point-in-polygon tests by determining grid center points in advance
	Li, Jing (1); Wang, Wencheng (1)
	2013
会议名称	2013 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference, APSIPA 2013
会议日期	October 29, 2013 - November 1, 2013
会议地点	Kaohsiung, Taiwan
收录类别	CPCI ; EI
出版地	IEEE Computer Society, 2001 L Street N.W., Suite 700, Washington, DC 20036-4928, United States
ISBN	9789869000604
部门归属	(1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
摘要	This paper presents a new method for point-inpolygon tests via uniform grids. It consists of two stages, with first to construct a uniform grid and determine the inclusion property of every grid center point, and the second to determine a query point by the center point of its located grid cell. In this way, the simple ray crossing method can be used locally to perform point-in-polygon tests quickly. When O(Ne) grid cells are constructed, as used in many grid-based methods, our new method can considerably reduce the storage requirement and the time on grid construction and determining the grid center points in the first stage, where Ne is the number of polygon edges. As for answering a query point at the second stage, the expected time complexity is O(1) in general. Experiments show that our new method can be several times faster than existing methods at the first stage and an order of magnitude faster at the second stage. Benefited from its high speed and less storage requirement, our new method is very suitable for treating large-scale polygons and dynamic cases, as shown in our experiments. © 2013 APSIPA.; This paper presents a new method for point-inpolygon tests via uniform grids. It consists of two stages, with first to construct a uniform grid and determine the inclusion property of every grid center point, and the second to determine a query point by the center point of its located grid cell. In this way, the simple ray crossing method can be used locally to perform point-in-polygon tests quickly. When O(Ne) grid cells are constructed, as used in many grid-based methods, our new method can considerably reduce the storage requirement and the time on grid construction and determining the grid center points in the first stage, where Ne is the number of polygon edges. As for answering a query point at the second stage, the expected time complexity is O(1) in general. Experiments show that our new method can be several times faster than existing methods at the first stage and an order of magnitude faster at the second stage. Benefited from its high speed and less storage requirement, our new method is very suitable for treating large-scale polygons and dynamic cases, as shown in our experiments. © 2013 APSIPA.
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16506
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Li, Jing ,Wang, Wencheng . Point-in-polygon tests by determining grid center points in advance[C]. IEEE Computer Society, 2001 L Street N.W., Suite 700, Washington, DC 20036-4928, United States,2013.