欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
检测点在多边形中的可见边是计算几何中的一种基本计算，文中对此提出一种加速算法．首先对多边形进行凸片段分解，以利用点在凸多边形中可见边的快速计算；然后利用格网结构实现由近及远的计算，避免处理被遮挡的凸片段．该算法可基于格网结构方便地进行并行处理，并可统一处理含空洞和不含空洞的多边形，其预处理时间复杂度为O（n），空间复杂度也是很低的0（n），而检测的时间复杂度在0（10gn）～O（n）之间自适应变化，其中n为多边形的边数．
英文摘要：
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.
同期刊论文项目
同项目期刊论文
期刊信息
位置：