一种任意形状多边形的最小矩形包围盒生成算法

摘要：

　　针对在排样、路径规划、碰撞检测和视区裁剪等应用中常常涉及到的包围盒生成问题，给出了一种任意形状多边形的最小面积矩形包围盒的生成算法。首先根据组成多边形的各顶点的相邻三个顶点的相对位置确定各外侧顶点，并依序相连求得任意形状多边形的凸包；然后根据凸包多边形矩形包围盒中的至少一条边与凸包的一条边共线的原理，逐一取每条边构造对应的矩形包围盒，求得面积最小者为求解结果。文中通过实例验证了算法的有效性。

关键词： 矩形包围盒 生成算法 凸包多边形 优化排样

作者: DONG Fangmin 董方敏 JIA Dan 贾丹 LI Qian 李倩

作者单位: College of Electrical Engineering and Information Technology,China Three Gorges University,Yichang 4 三峡大学电气信息学院,宜昌,443002

会议类型: 国内会议

会议名称: 第19届全国计算机新科技与计算机教育学术大会

会议地点: 黄山

会议语种:中文

页码: 433-436

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