Dowemo
0 0 0 0


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?


Best Answer:


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



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs