中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 期刊论文
Title:
基于凸片段分解和格网的点在多边形中的可见边检测
Alternative Title: Visibility queries of points in polygons by decomposed convex segments and grids
Author: 高天豪 ; 王文成 ; 朱滨海
Corresponding Author: Wang, W.(whn@ios.ac.cn)
Keyword: 多边形 ; 可见边 ; 凸片段 ; 格网 ; 并行计算
Source: 计算机辅助设计与图形学学报
Issued Date: 2013
Volume: 25, Issue:8, Pages:1114-1120
Indexed Type: EI ; CSCD
Department: 高天豪, 中国科学院软件研究所, 计算机科学国家重点实验室, 北京 100190, 中国. 王文成, 中国科学院软件研究所, 计算机科学国家重点实验室, 北京 100190, 中国. 朱滨海, Department of Computer Science,Montana State University, Bozeman, 59717-3880, USA.
Abstract: 检测点在多边形中的可见边是计算几何中的一种基本计算,文中对此提出一种加速算法.首先对多边形进行凸片段分解,以利用点在凸多边形中可见边的快速计算; 然后利用格网结构实现由近及远的计算,避免处理被遮挡的凸片段.该算法可基于格网结构方便地进行并行处理,并可统一处理含空洞和不含空洞的多边形,其预处 理时间复杂度为O(n),空间复杂度也是很低的O(n),而检测的时间复杂度在O(logn)~O(n)之间自适应变化,其中n为多边形的边数.
English Abstract: It is a basic operation in computational geometry to detect the visible edges of a point in a polygon. With regard to this, this paper presents a new algorithm for acceleration. Firstly, it decomposes the polygon into convex segments, to take the advantage that it is fast to compute the visible edges of a point in a convex polygon. Then, it uses a grid to treat convex segments from near to far, to avoid treating those occluded ones. Also by the grid, the new algorithm can be easily implemented in parallel. The new algorithm treats the polygons with or without holes uniformly. It has a lower time complexity O(n) on preprocessing to construct a data structure in O(n) storage, while finds visible edges of a point in O(log n)~O(n) time adaptively, where n is the number of polygon edges.
Language: 中文
Citation statistics:
Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/16816
Appears in Collections:软件所图书馆_期刊论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
高天豪,王文成,朱滨海. 基于凸片段分解和格网的点在多边形中的可见边检测[J]. 计算机辅助设计与图形学学报,2013-01-01,25(8):1114-1120.
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
[朱滨海]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[高天豪]‘s Articles
[王文成]‘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