The largest quadrangle of many points

Question

I am looking for a way to find the quadrangle with the largest area. I have already calculated the points of the convex hull and sorted them clockwise. I tried brute force, but of course it is too slow. So I found here this algorithm for the largest triangle:

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

It looks very good, so I tried to remake it. I have a function that calculates the area of ​​any quadrangle by dividing it into two triangles (in this function I sort the input points to make sure that I calculate the correct triangles). Here he 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 great and gives good results for my simple tests, but I'm afraid something is wrong. Going further with this reasoning, I could make an algorithm for each polygon with n vertices, but by intuition I think that this is impossible. I'm right?

I am trying to solve the "SHAMAN" problem on spoj and I have the wrong answer. I'm 99% sure that the rest of my program is fine, so something is wrong with the code above. Could you help me improve it? Maybe you have some complex tests that could prove that this algorithm is not working correctly? I will be grateful for any advice!

Answer 1

I would divide the convex hull into two halves, find the largest triangle in each half, calculate the sum - and then rotate the “separator” over 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() - ie 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 am not an excellent mathematician and therefore not entirely sure (I can not prove), you can rotate A and B together like that. I hope someone can fill this gap ... always willingly study :-)