求多边形的最小包络矩形【java实现+原理讲解】

问题

给定一个多边形的点集，如何找出一个矩形，该矩形可以将整个多边形包住，且矩形的面积最小。

方法

整个问题的求解分为两个过程，如果多边形为凹多边形，需要先将凹多边形转化为凸多边形，紧接着开始寻找凸多边形的最小包络矩形。

将凹多边形转化为凸多边形

如果不了解凹多边形和凸边形如何定义，以及凹多边形转化为凸多边形的具体操作，可以参考文章凹多边形处理成凸多边形

寻找最小包络矩形

尝试将凸多边形的每条边都旋转到水平方向，然后求旋转之后的矩形的水平最小包络矩形，在遍历过程中不断更新最小包络矩形。

/**
 * 获取多边形的 最小包络矩形
 */
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);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

测试

参考文献

[1]曹新明,蒋瑞斌.不规则零件最小包络矩形的求解研究[J].科技通报,2007(01):102-105.