Dowemo


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