中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 期刊论文
Subject: Computer Science (provided by Thomson Reuters)
Title:
基于网格中心点的点在多边形内的高效判定
Alternative Title: point-in-polygon test method based on center points of grid
Author: 李静 ; 王文成
Keyword: 多边形 ; 点包容性检测 ; 网格 ; 中心点
Source: 软件学报
Issued Date: 2012
Volume: 23, Issue:9, Pages:2481-2488
Indexed Type: CNKI ; CSCD ; WANFANG
Department: 中国科学院软件研究所计算机科学国家重点实验室;
Sponsorship: 国家自然科学基金(60873182,60773026,60833007)
Abstract: 提出一种基于均匀网格的点在多边形内的高效判定算法.它首先建立均匀网格,并从左至右依次计算每个网格单元中心点的位置属性.每个单元中心点的位置属性直接依据其左侧邻接单元已知位置属性的中心点快速获得.在判定点的位置时,确定被测点所在单元,并依据该单元中心点的位置属性判定被测点的位置属性.由于预处理和判定时均利用邻近点的已知位置属性来确定未知点位置属性,可以很好地进行局部化的计算.因此,新方法比现有方法快很多,并且其预处理时间复杂度也由同类网格算法的O(N3/2)下降为O(N).同时,新方法可以统一处理含有自相交及重叠边的非流形多边形.实验结果表明,相比于其他基于均匀网格的方法,新方法可将预处理的速度提高几倍,将判断计算的速度提高十几到几十倍.其速度甚至优于具有该问题最低判定计算时间复杂度O(logN)的基于凸剖分的判定算法.
English Abstract: 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(N3/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 at 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.
Language: 中文
Citation statistics:
Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/15397
Appears in Collections:软件所图书馆_期刊论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
李静,王文成. 基于网格中心点的点在多边形内的高效判定[J]. 软件学报,2012-01-01,23(9):2481-2488.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[李静]'s Articles
[王文成]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[李静]‘s Articles
[王文成]‘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