中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 会议论文
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:软件所图书馆_会议论文

Files in This Item:

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.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Li, Jing (1)]'s Articles
[Wang, Wencheng (1)]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Li, Jing (1)]‘s Articles
[Wang, Wencheng (1)]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2019  中国科学院软件研究所 - Feedback
Powered by CSpace