从点集中找出最大的四边形

Question

我正在寻找一种方法来找到面积最大的四边形。我已经计算出了凸包的点，并将它们按顺时针排序。我尝试了暴力破解，但当然太慢了。所以我在这里找到了一个用于查找最大三角形的算法： 如何在凸包中找到最大三角形，而不是使用暴力搜索 看起来非常好，所以我试图重制它。我有一个计算任意四边形面积的函数，通过将其分成两个三角形来完成（在此函数中，我对输入点进行排序以确保我计算正确的三角形）。就是这样：

int n = convexHull.size();
int A = 0; int B = 1; int C = 2; int D = 3;
int bestA = A; int bestB = B; int bestC = C; int bestD = D;
while(true) { // loop A
      while(true) { // loop B
        while(true) { // loop C
          while(quadrangleArea(A, B, C, D) <=  quadrangleArea(A, B, C, (D+1)%n) ) { // loop D
              D = (D+1)%n;
          }
          if(quadrangleArea(A, B, C, D) <=  quadrangleArea(A, B, (C+1)%n, D) ) {
              C = (C+1)%n;
              continue;
          }
          else break;
        }
        if(quadrangleArea(A, B, C, D) <=  quadrangleArea(A, (B+1)%n, C, D) ) {
          B = (B+1)%n;
          continue;
        }
        else break;
      }
      if(quadrangleArea(A, B, C, D) >  quadrangleArea(bestA, bestB, bestC, bestD) ) {
        bestA = A; bestB = B; bestC = C; bestD = 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;
}

这个算法在我的简单测试中看起来很好并且给出了良好的结果，但我担心有些地方不对。继续这种推理，我可以为每个有n个顶点的多边形制定算法 - 但凭直觉，我认为这是不可能的。我是正确的吗？

我正在尝试解决spoj上的"SHAMAN"问题，但我得到了错误的答案。我99%确定我程序的其他部分没问题，所以上面的代码肯定有问题。你能帮我改进它吗？也许你有一些棘手的测试可以证明这个算法不能正常工作？我将感激任何提示！

- conradus

---

相关: http://stackoverflow.com/questions/16233959/largest-quadrilateral-from-a-set-of-points - finnw

你应该看一下引用的Dobkin论文http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4567996。他们处理更高阶多边形，但似乎无法证明算法适用于三角形以外的情况。 - agentp

Answer 1

我会将凸包分成两半，找到每一半中最大的三角形，计算它们的和 - 然后沿着凸包旋转“分割线”。就像这样：

size_t n = convexHull.size();
size_t A = 0;
size_t B = n/2;
size_t C, D;
size_t maxarea = 0;
size_t area;
size_t maxQuad[4];

// size_t findLargestTriangle(convHullType c, int& tip);
//    make this search the hull "c" with the assumption
//    that the first and last point in it form the longest
//    possible side, and therefore will be base of the
//    triangle with the largest area. The "other" point
//    will be returned, as will be the size.
while (A < n/2 && B < n) {
    // this is partially pseudocode, as you need to treat
    // the container as "circular list", where indices wrap
    // around at container.size() - i.e. would have
    // to be container[n + x] == container[n]. No ordinary
    // C++ std:: container type behaves like this but it's
    // not too hard to code this.
    // This simply says, "two sub-ranges".
    area =
        findLargestTriangle(convexHull[A..B], C) +
        findLargestTriangle(convexHull[B..A], D);
    if (area > maxarea) {
        maxarea = area;
        maxQuad = { A, B, A + C, B + D };
    }
    A++; B++;
}

我不是一个很擅长数学的人，因此不能完全确定（无法证明）您是否可以像这样一起旋转A和B。希望有人能填补这个空白...我自己总是渴望学习的;-)

- FrankH.