| Point-in-polygon tests by determining grid center points in advance |
| Li, Jing (1); Wang, Wencheng (1)
|
| 2013
|
| Conference Name | 2013 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference, APSIPA 2013
|
| Conference Date | October 29, 2013 - November 1, 2013
|
| Conference Place | Kaohsiung, Taiwan
|
| Indexed Type | CPCI
; EI
|
| Publish Place | IEEE Computer Society, 2001 L Street N.W., Suite 700, Washington, DC 20036-4928, United States
|
| ISBN | 9789869000604
|
| Department | (1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
|
| English Abstract | 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. |
| Language | 英语
|
| Content Type | 会议论文
|
| URI | http://ir.iscas.ac.cn/handle/311060/16506
|
| Collection | 中国科学院软件研究所
|
Recommended Citation
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.
|
| Files in This Item: |
|
There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment