计算凸包的最大内接N边形

凸包可以用一组点简要的描绘轮廓的形状，在计算机视觉中有广泛的应用。解算凸包最大内接N边形也是常见的问题。这篇博客介（摘）绍（抄）这一问题的一种解法。

算法出处

很老的一篇文章，算法在文章最后

https://ieeexplore.ieee.org/document/4567996?tp=&arnumber=4567996&url=http:%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D4567996

算法伪代码

算法说明

凸包N边形的顶点一定再凸包上，N边形顶点一定是凸包点。计算最大N边形的过程，需要不断移动和改变顶点，不断比较面积。

移动点的策略就是，首先移动最末尾P(n)（这里的最末尾指N变形顺时针方向的最后一个点），当移动后比移动前N边形面积更大时，就可以移动P（n-1）了。然后同样的策略移动P(n-1)，每次移动P(n-1)之后都需要再移动P(n)，这样一直向上到P(1)。多重循环退出的含义是，不再有任何顶点的移动，导致凸包N边形面积更大。

代码实现

对于四边形来说，代码实现是这样子的。其中Area为凸包面积函数，可以对应于opencv中的ContourArea函数。

private static double getQuad(Point[] z) {
        Point A = z[0], B = z[1], C = z[2], D = z[3];
        int a = 0, b = 1, c = 2, d = 3;
        int n = z.length;
        while (true) {
            while (true) {
                while (true) {
                    while (Area(z[a], z[b], z[c], z[d]) <= Area(z[a], z[b], z[c], z[(d + 1) % n])) {
                        d = (d + 1) % n;
                    }
                    if (Area(z[a], z[b], z[c], z[d]) > Area(z[a], z[b], z[(c + 1) % n], z[d])) {
                        break;
                    }
                    c = (c + 1) % n;
                }
                if (Area(z[a], z[b], z[c], z[d]) > Area(z[a], z[(b + 1) % n], z[c], z[d])) {
                    break;
                }
                b = (b + 1) % n;
            }
            if (Area(z[a], z[b], z[c], z[d]) > Area(A, B, C, D)) {
                A = z[a];
                B = z[b];
                C = z[c];
                D = z[d];
            }
            a = (a + 1) % n;
            if (a == b) {
                b = (b + 1) % n;
            }
            if (b == c) {
                c = (c + 1) % n;
            }
            if (c == d) {
                d = (d + 1) % n;
            }
            if (a == 0) {
                break;
            }
        }

        return Area(A, B, C, D);
    }