问题
给定一个多边形的点集，如何找出一个矩形，该矩形可以将整个多边形包住，且矩形的面积最小。
方法
整个问题的求解分为两个过程，如果多边形为凹多边形，需要先将凹多边形转化为凸多边形，紧接着开始寻找凸多边形的最小包络矩形。
将凹多边形转化为凸多边形
如果不了解凹多边形和凸边形如何定义，以及凹多边形转化为凸多边形的具体操作，可以参考文章凹多边形处理成凸多边形
寻找最小包络矩形
尝试将凸多边形的每条边都旋转到水平方向，然后求旋转之后的矩形的水平最小包络矩形，在遍历过程中不断更新最小包络矩形。
/** * 获取多边形的 最小包络矩形 */ public class GetMinimumEnvelopeRectangleApi { /** * 获取多边形的最小包络矩形 * * @param pointList 多边形点集 * @return */ public static Rectangle getMinimumEnvelopeRectangle(List<Point> pointList) { 将凹多边形转化为凸多边形 pointList = new ConcaveToConvexApi().concaveToConvex(pointList); 寻找最小包络矩形 double minRectangleArea = Double.MAX_VALUE; double bestLen = 0; double bestWid = 0; Point[] bestPointArr = new Point[4]; for (int m = 0; m < pointList.size(); m++) { int n = (m + 1) % pointList.size(); float mX = pointList.get(m).getX(); float mY = pointList.get(m).getY(); //求当前边和向量(1,0)的角度 double angle = -MathUtil.calculateAngleOfVector( pointList.get(n).getX() - mX, pointList.get(n).getY() - mY ); ///将除了 点m 之外的每个点绕着 点m 旋转， 然后构造矩形 double minX = mX; double minY = mY; double maxX = mX; double maxY = mY; for (int i = 0; i < pointList.size(); i++) { if (i == m) { continue; } Point pointI = pointList.get(i); //旋转 double[] rotate = MathUtil.rotate(pointI.getX(), pointI.getY(), mX, mY, angle); minX = Math.min(minX, rotate[0]); maxX = Math.max(maxX, rotate[0]); minY = Math.min(minY, rotate[1]); maxY = Math.max(maxY, rotate[1]); } ///如果找到更小的矩形，更新最小矩形 if ((maxX - minX) * (maxY - minY) < minRectangleArea) { minRectangleArea = (maxX - minX) * (maxY - minY); bestLen = maxX - minX; bestWid = maxY - minY; if (bestLen < bestWid) { double temp = bestLen; bestLen = bestWid; bestWid = temp; } //存储矩形的左下角 bestPointArr[0] = new Point((float) minX, (float) minY); //存储矩形的右下角 bestPointArr[1] = new Point((float) maxX, (float) minY); //存储矩形的右上角 bestPointArr[2] = new Point((float) maxX, (float) maxY); //存储矩形的左上角 bestPointArr[3] = new Point((float) minX, (float) maxY); //将矩形的点位旋转回来 for (Point point : bestPointArr) { double[] rotateArr = MathUtil.rotate(point.getX(), point.getY(), mX, mY, -angle); point.setX((float) rotateArr[0]); point.setY((float) rotateArr[1]); } } } List<Float> pointXList = new ArrayList<>(); List<Float> pointYList = new ArrayList<>(); for (Point point : pointList) { pointXList.add(point.getX()); pointYList.add(point.getY()); } pointXList.add(pointList.get(0).getX()); pointYList.add(pointList.get(0).getY()); return new Rectangle((float) bestLen, (float) bestWid, bestPointArr, pointXList, pointYList); } }
package com.dam; /** * 数学工具 */ public class MathUtil { /** * 计算向量的模 * * @param x * @param y * @return */ public static double calculateModulusOfVector(double x, double y) { return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2)); } /** * 求(x,y)的角度（0,360），从x坐标轴正方向开始计算 * * @param x2 * @param y2 * @return */ public static double calculateAngleOfVector(double x2, double y2) { double x1 = 1; double y1 = 0; double radian = Math.acos((x1 * x2 + y1 * y2) / (MathUtil.calculateModulusOfVector(x1, y1) * MathUtil.calculateModulusOfVector(x2, y2))); double angle = Math.toDegrees(radian); return y2 > 0 ? angle : 360 - angle; } /** * 将(x1,y1)绕着(x2,y2)逆时针旋转rotateDegree * * @param x1 * @param y1 * @param x2 * @param y2 * @param rotateDegree * @return */ public static double[] rotate(double x1, double y1, double x2, double y2, double rotateDegree) { double[] arr = new double[2]; //根据角度求弧度 double radian = (rotateDegree * 1.0 / 180) * Math.PI; //旋转 arr[0] = (x1 - x2) * Math.cos(radian) - (y1 - y2) * Math.sin(radian) + x2; arr[1] = (y1 - y2) * Math.cos(radian) + (x1 - x2) * Math.sin(radian) + y2; return arr; } }
测试
参考文献
[1]曹新明,蒋瑞斌.不规则零件最小包络矩形的求解研究[J].科技通报,2007(01):102-105.
