|
|||||
|
|
| 基于凸片段分解和格网的点在多边形中的可见边检测 | |
| 引用本文： | 高天豪,王文成,朱滨海.基于凸片段分解和格网的点在多边形中的可见边检测[J].计算机辅助设计与图形学学报,2013,25(8). |
| 作者姓名： | 高天豪 王文成 朱滨海 |
| 作者单位： | 1. 中国科学院软件研究所计算机科学国家重点实验室 北京 100190;中国科学院大学北京 100049 2. 中国科学院软件研究所计算机科学国家重点实验室 北京 100190 3. Department of Computer Science, Montana State University, Bozeman MT 59717-3880 USA |
| 基金项目： | 国家自然科学基金，中国科学院知识创新工程领域前沿项目 |
| 摘 要： | 检测点在多边形中的可见边是计算几何中的一种基本计算,文中对此提出一种加速算法.首先对多边形进行凸片段分解,以利用点在凸多边形中可见边的快速计算；然后利用格网结构实现由近及远的计算,避免处理被遮挡的凸片段.该算法可基于格网结构方便地进行并行处理,并可统一处理含空洞和不含空洞的多边形,其预处理时间复杂度为O(n),空间复杂度也是很低的O(n),而检测的时间复杂度在O(logn)～O(n)之间自适应变化,其中n为多边形的边数. |
| 关 键 词： | 多边形 可见边 凸片段 格网 并行计算 |
Visibility Queries of Points in Polygons by Decomposed Convex Segments and Grids |
|
| Gao Tianhao , Wang Wencheng , Zhu Binhai.Visibility Queries of Points in Polygons by Decomposed Convex Segments and Grids[J].Journal of Computer-Aided Design & Computer Graphics,2013,25(8). | |
| Authors: | Gao Tianhao Wang Wencheng Zhu Binhai |
| Abstract: | |
| Keywords: | polygon visible edges convex line segments grid parallel computation |
| 本文献已被 万方数据 等数据库收录！ | |