| Title: | Point-in-polygon tests by determining grid center points in advance |
| Author: | Li, Jing (1)
; Wang, Wencheng (1)
|
| Conference Name: | 2013 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference, APSIPA 2013
|
| Conference Date: | October 29, 2013 - November 1, 2013
|
| Issued Date: | 2013
|
| Conference Place: | Kaohsiung, Taiwan
|
| Publish Place: | IEEE Computer Society, 2001 L Street N.W., Suite 700, Washington, DC 20036-4928, United States
|
| Indexed Type: | CPCI
; EI
|
| ISBN: | 9789869000604
|
| Department: | (1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
|
| 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. |
| 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. |
| Language: | 英语
|
| Content Type: | 会议论文
|
| URI: | http://ir.iscas.ac.cn/handle/311060/16506
|
| Appears in Collections: | 软件所图书馆_会议论文
|
|
There are no files associated with this item.
|
| Recommended Citation: | |
Li, Jing ,Wang, Wencheng . Point-in-polygon tests by determining grid center points in advance[C]. 见:2013 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference, APSIPA 2013. Kaohsiung, Taiwan. October 29, 2013 - November 1, 2013.
|
|
|
