Largest quadrangle from set of points

Question

I'm looking for a way to find quadrangle with largest area. I have already computed points of convex hull and got them sorted clockwise. I tried brute force but of course it's too slow. So I've found here this algorithm for largest triangle:

How to find largest triangle in convex hull aside from brute force search

It looks really nice, so I tried to remake it. I've got function that computes area of any quadrangle by dividing it to two triangles (in this function I'm sorting input points to be sure I'm calculating right triangles). Here it is:

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;
}

It looks fine and gives good results for my simple tests, but I'm afraid something is not right. Going further with this reasoning, I could make algorithm for every polygon with n vertices - but by intuition I think it's impossible. Am I right?

I'm trying to solve "SHAMAN" problem on spoj, and I've got wrong answer. I'm 99% sure rest of my program is OK, so something is wrong with code above. Could you help me to improve it? Maybe you've got some tricky tests that could prove this algorithm doesn't work properly? I'll be grateful for any tips!

Related: http://stackoverflow.com/questions/16233959/largest-quadrilateral-from-a-set-of-points — finnw, May 28 '13 at 11:46
You should look at the referenced Dobkin paper http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4567996. They treat higher order polygons but It seems could not proove the algorithm for other than triangles. — agentp, May 28 '13 at 20:42

score 0 · Answer 1 · answered May 28 '13 at 12:23

I'd subdivide the convex hull into two halves, find the largest triangle in each half, calculate the sum - and then rotate the "divider" across the convex hull. Like this:

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++;
}

I'm not a great math guy and therefore not entirely sure (can't prove) you can rotate A and B together like this. Hope someone can fill that gap in ... always eager to learn myself ;-)

Largest quadrangle from set of points

1 Answers1