• 求最小外接矩形的原理
• C++实现代码

求最小外接矩形的原理

最近在做课程设计的过程中遇到了一个问题，需要求出一幅图像中物体的矩形度，但是求解矩形度需要用到该物体的最小外接矩形的面积。所以我查了各种资料想要写一个求解物体最小外接矩形的代码。

首先我们来看一下求解的原理。一个物体的与x轴和y轴平行的外接矩形就是这个物体的简单外接矩形，显然，物体的简单外接矩形是比较容易计算面积的。那么我们只需要将物体旋转一定的角度，再求出旋转后的简单外接矩形，最后得到最小的简单外接矩形的面积就行了，而旋转的角度在正负90°之间，以1°为1个间隔。

因为我们只要求解面积而不需要将这个矩形画出来，所以可以采用C++中的set容器来实现，set容器具有自动排序的功能。

大致实现算法如下：

C++实现代码

// 求解最小外接矩形面积
long lengthAndWidth(LPSTR lpSrcStartBits, long lSrcWidth, long lSrcHeight, int label)
{
	unsigned char* lpSrc;
	int* pixel = new int[2];
	pixel[0] = pixel[1] = 0;
	long lLineBytes = WIDTHBYTES(lSrcWidth * 8);
	// 旋转角度（弧度）
	float	fRotateAngle;
	// 旋转角度的正弦和余弦
	float fSina, fCosa;
	int rotate = 0;
	long x0, y0;
	std::set<int> setx,sety;
	long min = 10000000;
	long square = 0;
	for (rotate = -90;rotate <= 90;rotate++)
	{
		// 将旋转角度从度转换到弧度
		fRotateAngle = (float)((rotate)*PI / 180.0);
		// 计算旋转角度的正弦
		fSina = (float)sin((double)fRotateAngle);
		// 计算旋转角度的余弦
		fCosa = (float)cos((double)fRotateAngle);
		for (long i = 0;i < lSrcHeight;i++)//旋转
		{
			for (long j = 0;j < lSrcWidth;j++)
			{
				lpSrc = (unsigned char*)lpSrcStartBits + lLineBytes * (lSrcHeight - 1 - i) + j;
				if (*lpSrc == label)
				{
					x0 = j * fCosa - i * fSina + 0.5;
					y0 = j * fSina + i * fCosa + 0.5;
					setx.insert(x0);
					sety.insert(y0);
				}
			}
		}
		square = abs((*setx.rbegin() - *setx.begin() + 1) * (*sety.rbegin() - *sety.begin() + 1));
		if(min > square)
		{
			min = square;
			pixel[0] = *setx.rbegin() - *setx.begin() + 1;
			pixel[1] = *sety.rbegin() - *sety.begin() + 1;
		}
		setx.clear();sety.clear();
	}
	return (pixel[0]*pixel[1]);
 }

当然这份代码只对8位图像有效，我们也可以参照算法把它改成适用于24位图像的代码。

参考文章：
https://zhuanlan.zhihu.com/p/97855964.