最小面积凸包围盒算法.pdf

第27卷第3期 孝感学院学报 V0L．27 NO．3 2007年5月 JOURNAL OF XIAOGAN UNIVERSITY MAY．2OO7 基于遗传算法的封闭轮廓最小面积 凸包围盒生成算法 刘 云 ，戴光明2，王茂才2 (1．沙洋师范高等专科学校 数理系，湖北 荆门448200；2．中国地质大学 计算机学院，湖北 武汉430074) 摘 要：许多工程应用中需要计算区域最小面积的包围盒。当前工程实践中通常采用的是面积最小的矩 形包围盒，而最小面积矩形包围盒在许多工程实践中由于存在较大误差 因此并不能满足应用需求。本文基于 遗传算法的思想，研究并提出了任意封闭区域(轮廓)最小面积的凸包围盒生成算法。该算法简单，速度快，效 果显著。实际应用表明了该算法的有效性与实用性。 关键词：遗传算法；凸多边形；最小包围盒 ． 中图分类号：TP301．6 文献标识码：A 文章编号：1671—254_4(2007)03—0063一o4 包围盒是计算几何中的基本问题之一…，在 凸壳，由封闭轮廓求凸壳的算法已有许多，本文不 诸如图像处理、模式识别、CAD等领域有着广泛 再论述)，求出一个凸多边形，使该凸多边形包围 的应用。计算凸多边形的最小面积凸多边形包围 给定的凸壳，且该凸多边形的面积在包围给定的 盒问题是该问题的一个特例 。 凸壳的所有凸多边形中面积最小。即： 因问题本身的复杂性及 问题本身的任意性， 已知：i、)，i(i=0，1，…，一1，i、Yi为给定的 在凸多边形最小面积包围盒的研究上 目前还没有 凸 边形各点的横纵坐标)， 有效的方法。当前在包围盒的研究上已取得的进 求解：，、Yi’(i=0，1，…，m一1，i’、)，，为所 展是矩形包围盒。Li等 提出的用旋转方法求任 求的最小面积凸m边形包 围盒各点的横纵坐 意封闭轮廓最小矩形包围盒的研究非常简单有 标)，ITS= 。 效，然而该方法求出的包围盒只能是矩形，许多情 约束条件： 况下误差较大，效果并不是很理想。如何求出任 1) 、)，构成一凸ITS边形K； 意封闭轮廓的最小四边形包围盒一直是人们研究 2)凸ITS边形K包围原始的凸 边形； 的热点。本文基于遗传算法的思想提出了任意封 3)凸 ITS边形 K在包围凸n边形的所有 凸m 闭轮廓的最小凸多边形包围盒的算法实现，算法 边形中面积最小。 简单，速度快，效果显著。实际应用表明了该算法 2 算法思想 的有效性与实用性。 该算法的主要思路是：对于初始群体中的各 1 问题描述 个凸多边形包围盒每个点的坐标，用演化的方法 该问题简单地说就是对于一个凸壳 (对于任 随机产生。首先随机产生多个符合要求的包围 意封闭区域可以先求出其封闭轮廓，然后再求其 盒，即包围原始的凸 边形的凸多边形，然后进行 收稿 日期：2O07一o3一o9 基金项 目：湖北省 自然科学基金项 目(2003ABA045) 作者简介：刘 云(1972一 )，男，湖北公安人，沙洋师范高等专科学校数理系讲师。 戴光明(1964一 )，男，安徽怀宁人，中国地质大学计算机学院教授，博士。 一 63— 刘 云，戴光明，王茂才 随机演化，即根据交叉概率P。和变异概率P 进 点位于同一个象限，则根据顶