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

摘要：

　　点在多边形中的可见边的检测，是计算几何中研究的基本问题之一，在图形学、可视化、运动规划等许多方面有着重要的应用需求。本文对此提出一种加速算法，一方面，它对多边形进行凸片段分解，以利用点在凸多边形中可见边的快速计算，另一方面，它利用格网结构以实现由近及远的计算，避免处理被遮挡的凸片段。新算法可统一处理含空洞和不含空洞的多边形。

关键词： 凸片段分解 多边形 可见边检测 格网结构 加速算法

作者: 高天豪 王文成 朱滨海

作者单位: 中国科学院软件研究所计算机科学国家重点实验室 北京 100190 Department of Computer Science， Montana State University， Bozeman MT 59717-3880 USA

会议类型: 国内会议

会议名称: 第九届中国计算机图形学大会(Chinagraph‘2012)

会议地点: 成都

会议语种:中文

页码: 192

在线出版日期: 2012-10-22（万方平台首次上网日期，不代表论文的发表时间）