基于单调链的简单多边形距离算法

• 作者: 吴介一 周之平 张少博 张飒兵
• 来源期刊: 计算机应用研究
• 关键词: 简单多边形 单调链 层次树 AABB 包围盒 可见性
• 年，卷（期）: 2007,（1）
• 所属期刊栏目: 研究探讨
• 页码范围: 136-139
• 页数: 4页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2007.01.042

摘要

简单多边形的距离问题是计算机图形学中的一个研究难点,为了能快速地获得距离信息,提出一种基于单调链的简单多边形距离算法.算法先对多边形边界进行关于坐标轴的单调链分割,然后根据可见性原则确定候选链对,再结合层次树理论和分支限界策略计算链对距离以求解多边形的最近距离.试验结果表明,该算法性能优于其他同类算法.