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

Question

Given a convex polygon, how do I find the 3 points that define a triangle with the greatest area.

Related: Is it true that the circumcircle of that triangle would also define the minimum bounding circle of the polygon?

Answer 1

According to this paper, there is a class of convex polygons in which the algorithm cited by ShreevatsaR's answer fails. The paper also proposes a O(n log n) divide and conquer algorithm for solving the problem.

Apparently, the simpler O(n²) algorithm in which you move points B and C for all A is still valid.

Answer 2

answering your related question:

The circumcircle of the triangle is not necessarily the minimum bounding circle of the polygon. To see this, consider a very flat isosceles triangle, say with vertices at (0,0), (10,0) and (5,1). The minimum bounding circle has center (5,0) and radius 5, but this circle doesn't touch the vertex at (5,1), so it's not the circumcircle. (The circumcircle has center (5,-12) and radius 13)

edit:

Choosing the smaller of the circumcircle or the circle containing the antipodal points of the diameter of the polygon also doesn't suffice, because it is possible to construct polygons that have points outside the circumcircle of the maximal triangle. Consider the pentagon with vertices at:

(-5,  0)
(-4, -1)
( 5,  0)
( 4,  1)
(-4,  1)

The maximal triangle has vertices at (-4,-1), (5, 0), and (-4, 1). Its circumcircle does not include the point at (-5, 0).

Answer 3

from http://www.wolframalpha.com/input/?i=triangle The area of the triangle = sqrt((a+b-c)(a-b+c)(-a+b+c)*(a+b+c)) / 4 If you use c connected to the end points of your convex polygon and if a and b would touch your convex polygon you could iterate around your polygon allowing a to grow and b to shrink until you find your maximum area. I would start mid point and try each direction for a larger area.

Answer 4

I know this is an old post but by referencing the answer above I was able to modify the code to maximize the area for an n-sided polygon.

Note: The convex hull was found using Emgu OpenCV library. I'm using CvInvoke.ContourArea() method to calculate the given area of a polygon. This is written in C#. It also assumes that the points are arranged in clockwise order. This can be specified in the method CvInvoke.ConvexHull().

private PointF[] GetMaxPolygon(PointF[] convexHull, int vertices)
{
         // validate inputs
        if(convexHull.Length < vertices)
        {
         return convexHull;
        }
        int numVert = vertices;
        // triangles are the smalles polygon with an area.
        if (vertices < 3)
           numVert = 3;        

        PointF[] best = new PointF[numVert]; // store the best found
        PointF[] next = new PointF[numVert];  // test collection of points to compare
        PointF[] current = new PointF[numVert]; // current search location.

        int[] indexes = new int[numVert]; // map from output to convex hull input.
        int[] nextIndices = new int[numVert];

        //starting values 0,1,2,3...n
        for(int i = 0; i < numVert; i++)
        {
            best[i] = convexHull[i];
            next[i] = convexHull[i];
            current[i] = convexHull[i];
        }

        // starting indexes 0,1,2,3... n
        for(int i = 0; i < numVert; i++)
        {
            nextIndices[i] = i;
            indexes[i] = i;                
        }

        //  starting areas are equal.
        double currentArea = GetArea(current);
        double nextArea = currentArea;
        int exitCounter = 0;

        while(true)
        {
            // equivelant to n-1 nested while loops 
            for(int i = numVert - 1; i > 0; i--)
            {
                while (exitCounter < convexHull.Length)
                {
                    // get the latest area
                    currentArea = GetArea(current);
                    nextIndices[i] = (nextIndices[i] + 1) % convexHull.Length;
                    next[i] = convexHull[nextIndices[i]]; // set the test point
                    nextArea = GetArea(next);
                    if (currentArea <= nextArea) // compare.
                    {
                         indexes[i]= (indexes[i]+1) % convexHull.Length;
                         current[i] = convexHull[indexes[i]];
                         currentArea = GetArea(current);
                         exitCounter++; // avoid infinite loop.
                    }
                    else //stop moving that vertex
                    {
                        for(int j = 0; j< numVert; j++)
                        {
                            nextIndices[j] = indexes[j];
                            next[j] = convexHull[indexes[j]];//reset values.

                        }
                        break;
                    }
                }
            }

            // store the best values so far.  these will be the result.
            if(GetArea(current)> GetArea(best))
            {
                for (int j = 0; j < numVert; j++)
                {
                    best[j] = convexHull[indexes[j]];
                }
            }
            // The first index is the counter.  It should traverse 1 time around.
            indexes[0] = (indexes[0] + 1) % convexHull.Length;

            for(int i = 0; i < vertices-1;i++)
            {
                if(indexes[i] == indexes[i+1])// shift if equal.
                {
                    indexes[i + 1] = (indexes[i + 1] + 1) % convexHull.Length;
                }
            }

            //set new values for current and next.
            for(int i = 0; i < numVert; i++)
            {
                current[i] = convexHull[indexes[i]];
                next[i] = convexHull[indexes[i]];
            }

            // means first vertex finished traversing the whole convex hull.
            if (indexes[0] == 0)
                break;


        }
        return best;
}

The area method used. This could change depending on what is needed to maximize.

private double GetArea(PointF[] points)
{
    return CvInvoke.ContourArea( new Emgu.CV.Util.VectorOfPointF(points),false);
}