基于凸片段分解和格网的点在多边形中的可见边检测

• 作者: 朱滨海 王文成 高天豪
• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: 多边形 可见边 凸片段 格网 并行计算
• 年，卷（期）: 2013,（8）
• 所属期刊栏目: 图形与可视化
• 页码范围: 1114-1120
• 页数: 7页
• 分类号: TP391
• 字数: 4477字
• 语种: 中文

摘要

检测点在多边形中的可见边是计算几何中的一种基本计算,文中对此提出一种加速算法.首先对多边形进行凸片段分解,以利用点在凸多边形中可见边的快速计算；然后利用格网结构实现由近及远的计算,避免处理被遮挡的凸片段.该算法可基于格网结构方便地进行并行处理,并可统一处理含空洞和不含空洞的多边形,其预处理时间复杂度为O(n),空间复杂度也是很低的O(n),而检测的时间复杂度在O(logn)～O(n)之间自适应变化,其中n为多边形的边数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王文成	中国科学院软件研究所计算机科学国家重点实验室	42	484	13.0	20.0
2	高天豪	中国科学院软件研究所计算机科学国家重点实验室	1	1	1.0	1.0