本文共 4232 字，大约阅读时间需要 14 分钟。

最小外接矩形问题是在给出一个多边形（或一群点），求出面积最小且外接多边形的矩形的问题。这个问题看起来并不难，但是具体实现并不简单。除了调用现有的公开库之外，这里给出一种简单且易理解的方法。

算法的主要思想是：

（1）先实现多边形的简单外接矩形的算法。简单外接矩形是指边平行于x轴或y轴的外接矩形。简单外接矩形很有可能不是最小外接矩形，却是非常容易求得的外接矩形，这为后面做铺垫。

（2）实现平面上某一点绕固定点旋转某一角度的算法。数学基础是，设平面上点（x1，y1）绕另一点（x0，y0）逆时针旋转A角度后的点为（x2，y2），则有

x2 =(x1-x0)*cosA-(y1-y0)*sinA+x0

y2 =(x1-x0)*sinA+(y1-y0)*cosA+y0

顺时针时，A改写成-A即可。

（3）旋转原始多边形（循环，0-90°，间距设为1°），求旋转每个度数后的多边形的简单外接矩形，记录简单外接矩形的面积、顶点坐标以及此时旋转的度数。

（4）比较在旋转过程中多边形求得的所有简单外接矩形，得到面积最小的简单外接矩形，获取该简单外接矩形的顶点坐标和旋转的角度。

（5）旋转外接矩形。将上一步获得面积最小的简单外接矩形反方向（与第3步方向相反）旋转相同的角度，即得最小外接矩形。

实现过程

（1）寻找多边形的中心

多边形的中心就是多边形的重心，各个坐标点之和求平均即可

CPoint* CGeoPolygon::FindCenter(vector
   
     ptsArray){	double tempX,tempY;	double sumX = 0;	double sumY = 0;	int size = ptsArray.size();	for(int i = 0;i
    
     x;		sumY = sumY + ptsArray[i]->y;	}	tempX = sumX/size;	tempY = sumY/size;	CPoint* pt = new CPoint(tempX,tempY);	return pt;}
    
   

（2）旋转多边形，针对每个点实现绕中心点旋转

旋转的算法见下，注意角度要转换成弧度。

// 某一点pt绕center旋转theta角度，zf,0706CPoint* CGeoPolygon::rotate(CPoint* pt, CPoint* center, double theta){	double x1 = pt->x;	double y1 = pt->y;	double x0 = center->x;	double y0 = center->y;	double Q = theta / 180 * 3.1415926;  //角度	double x2,y2;	x2 = (x1-x0)*cos(Q)-(y1-y0)*sin(Q)+x0;   //旋转公式	y2 = (x1-x0)*sin(Q)+(y1-y0)*cos(Q)+y0;	CPoint* rotatePoint = new CPoint(x2,y2);	//CPoint* rotatePoint = new CPoint((x1+10,y1+10));	return rotatePoint;}

（3）多边形旋转后求简单外接矩形，简单外接矩形算法见下

void CGeoPolygon::FindRectangle(vector
   
     pts){	//AfxMessageBox("一般的外接矩形!");	int size = pts.size();	if(size == 0)		AfxMessageBox("该环为空");	else	{		double Xmax = 0;		double Ymax = 0;		double Xmin = 60000000;  //最小值不能初始为0，		double Ymin = 1000000000;  //最小值不能初始为0，		for(int i = 0;i
    
     Getx();			double tempy = pts[i]->Gety();			if(tempx>=Xmax) Xmax = tempx;  //最大x，			if(tempy>=Ymax) Ymax = tempy;  //最大y，			if(tempx<=Xmin) Xmin = tempx;  //最小x			if(tempy<=Ymin) Ymin = tempy;  //最小y		}		CPoint *pt1 = new CPoint(Xmax,Ymax);  //左上		CPoint *pt2 = new CPoint(Xmax,Ymin);		CPoint *pt3 = new CPoint(Xmin,Ymin);		CPoint *pt4 = new CPoint(Xmin,Ymax);		rectangleArray.push_back(pt1);		rectangleArray.push_back(pt2);		rectangleArray.push_back(pt3);		rectangleArray.push_back(pt4);	}}
    
   

这里的rectangleArray是我自己工程的数组，可以换成自己的。

上述三步为第一大步。

            vector
   
     temp = FindRectangle(tempArray); //-----------2---------求旋转后的外接矩形            if(temp.size() == 0)                AfxMessageBox("简单外接矩形获取失败！");            else            {                MBR_ZF *tempRect = new MBR_ZF();   //某个旋转角度时的外接矩形指针                for(int count = 0;count
    
     vertices.push_back(temp[count]);                double deltaX,deltaY,tempS;                     //求每个外接矩形的面积                deltaX = tempRect->vertices[0]->x - tempRect->vertices[2]->x;                deltaY = tempRect->vertices[0]->y - tempRect->vertices[2]->y;                tempS = deltaY * deltaX;                tempRect->area = tempS;                tempRect->ID = angle;                circles[i]->mbr.push_back(tempRect);  //mbr是用于存储旋转过程中每个外接矩形的数组，单组成元是每个对象的指针            }
    
   

（5）比较每个外接矩形，确定每个环面积最小的外接矩形。

                //------3-----------比较每个外接矩形，确定每个环面积最小的外接矩形		int finalID;		double compare = 600000000;		for(int num = 0;num
   
    mbr.size();num++)		{			if(compare >= circles[i]->mbr[num]->area)			{				finalID = circles[i]->mbr[num]->ID;				compare = circles[i]->mbr[num]->area;			}		}		for(int num = 0;num
    
     mbr.size();num++)		{			if(circles[i]->mbr[num]->ID == finalID)			{				circles[i]->finalMBR.area = circles[i]->mbr[num]->area;				circles[i]->finalMBR.ID = circles[i]->mbr[num]->ID;				for(int pointNum = 0; pointNum
     
      mbr[num]->vertices.size();pointNum++)					circles[i]->finalMBR.vertices.push_back(circles[i]->mbr[num]->vertices[pointNum]);			}		}
     
    
   

（6）将外接矩形旋转回来。外接矩形朝相反的方向旋转相同度数。

//----------4-------将外接矩形朝相反的方向旋转相同度数        int finalAngle = circles[i]->finalMBR.ID;        for(int final = 0;final
   
    finalMBR.vertices.size();final++)            rectangleRotate.push_back(rotate(circles[i]->finalMBR.vertices[final],center,-finalAngle));  //！！！此处角度相反
   

ID就是旋转的角度。

最终效果：

简单外接矩形

最小外接矩形

总结：理解算法的思路很重要，我的代码只是一个例子。这个方法不需要旋转外接矩形，只需要旋转多边形求简单外接矩形，思路上更容易理解。

PS：很感谢我的室友杨某给我的帮助，此方法受他启发。

转载地址：https://blog.csdn.net/Fan_z_0802/article/details/80960790 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！