So finden größte Dreieck in der konvexen Hülle abgesehen von brute-force-Suche

Ja, das kannst du deutlich besser als brute-force.

Durch brute-force-ich nehme an, du meinst die überprüfung alle Tripel von Punkten, und Kommissionierung die mit den maximalen Bereich. Diese läuft in O(n³) Zeit, aber es stellt sich heraus, dass es möglich ist, es zu tun, nicht nur an O(n²) aber in O(n) Zeit!

[Update: Ein Papier veröffentlicht im Jahr 2017 zeigte durch sein Beispiel, dass die O(n) Lösung funktioniert nicht für eine bestimmte Klasse von Polygonen. Sehen diese Antwort für weitere details. Aber die O(n²) - Algorithmus ist dennoch korrekt.]

Durch die erste Sortierung der Punkte /Berechnung der konvexen Hülle (in O(n log n) Zeit), wenn nötig, können wir davon ausgehen, haben wir die konvexe Fläche/Rumpf mit den Punkten zyklisch sortiert in der Reihenfolge erscheinen Sie in dem polygon. Rufen Sie die Punkte 1, 2, 3, ... , n. Let (Variablen) die Punkte A, B, und C, start (1, 2 und 3 jeweils (in der zyklischen Ordnung). Wir bewegen A, B, C, bis ABC ist der maximum-Fläche Dreieck. (Die Idee ist ähnlich zu der rotierende Bremssättel Methode, wie Sie bei der Berechnung der Durchmesser (farthest-pair-Mädchen).)

Mit A-und B-Feste, advance C (z.B. zunächst mit A=1, B=2, C ist erweitert durch C=3, C=4, ...), solange die Fläche eines Dreiecks erhöht, d.h., solange die Fläche(A,B,C) ≤ Area(A,B,C+1). Dieser Punkt C wird die eine, die maximiert die Fläche(ABC) für diejenigen, die festen A und B. (In anderen Worten, die Funktion Area(ABC) ist unimodalen als Funktion der C.)

Weiter Voraus B (ohne änderung der Ein-und C) wenn, das erhöht die Gegend. Wenn dem so ist, wiederum Voraus, C wie oben. Dann fahren Sie B erneut, wenn möglich, etc. Diese geben die maximale Fläche Dreieck mit A als einer der Eckpunkte.

(Den Teil bis hier sollte einfach sein, zu beweisen, und einfach tun dies separat für jede Eine würde geben, ein O(n²) - Algorithmus.)

Nun vorab wieder Ein, wenn es verbessert den Bereich, und so weiter._{(Die Richtigkeit dieses Teil ist subtiler: Dobkin und Snyder gab einen Nachweis in Ihrem Papier, aber eine aktuelle Papier zeigt ein Gegenbeispiel. Ich habe nicht verstanden es noch nicht.)}

Obwohl diese drei "verschachtelten" Schleifen, beachten Sie, dass B und C immer Voraus "vorwärts", und steigen Sie auf höchstens 2n-mal insgesamt (ähnlich Einem Fortschritt bei den meisten n-mal), also das ganze Ding läuft in O(n) Zeit.

Code-fragment, das in Python (übersetzung nach C sollte einfach sein):

 # Assume points have been sorted already, as 0...(n-1)
 A = 0; B = 1; C = 2
 bA= A; bB= B; bC= C #The "best" triple of points
 while True: #loop A

   while True: #loop B
     while area(A, B, C) <= area(A, B, (C+1)%n): #loop C
       C = (C+1)%n
     if area(A, B, C) <= area(A, (B+1)%n, C): 
       B = (B+1)%n
       continue
     else:
       break

   if area(A, B, C) > area(bA, bB, bC):
     bA = A; bB = B; bC = C

   A = (A+1)%n
   if A==B: B = (B+1)%n
   if B==C: C = (C+1)%n
   if A==0: break

Dieser Algorithmus erwies sich in Dobkin und Snyder, Auf eine Allgemeine Methode für die Maximierung und Minimierung unter bestimmten geometrischen Problemen, FOCS 1979, und der code oben ist eine direkte übersetzung Ihrer ALGOL-60-code. Entschuldigung für die while-if-break-Konstruktionen; es sollte möglich sein, Sie zu verwandeln in einfacher while-Schleifen.

Laut diese Papier, es gibt eine Klasse von konvexen Polygonen, in die der Algorithmus zitiert nach ShreevatsaR die Antwort ausfällt. Das Papier schlägt auch eine O(n log n) divide and conquer Algorithmus für die Lösung des Problems.

Scheinbar einfacher O(n²) - Algorithmus, in dem Sie bewegen Sie die Punkte B und C für alle Ein noch gültig ist.

Ich weiß, dies ist eine alte post, aber durch einen Verweis auf die Antwort oben ich war in der Lage, den code zu modifizieren, die zur Maximierung der Fläche für eine n-sided polygon.

Beachten Sie: Die konvexe Hülle wurde gefunden mit Emgu OpenCV-Bibliothek. Ich bin mit CvInvoke.ContourArea() Methode zum berechnen des gegebenen Fläche eines Polygons. Dies ist in C# geschrieben. Es wird auch davon ausgegangen, dass die Punkte angeordnet sind, im Uhrzeigersinn. Dies kann angegeben werden in der Methode 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;
}

Bereich Methode verwendet. Das könnte sich ändern, je nachdem, was notwendig ist, zu maximieren.

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