Come trovare il più grande triangolo nello scafo convesso a parte la ricerca della forza bruta

Dato un poligono convesso, come trovo i 3 punti che definiscono un triangolo con l’area più grande.

Corretto: è vero che il cerchio circoscritto di quel triangolo definirà anche il cerchio limite minimo del poligono?

Sì, puoi fare molto meglio della forza bruta.

Con la forza bruta presumo che intendi controllare tutte le triple di punti e scegliere quella con la massima area. Questo funziona in tempo O (n 3 ) , ma si scopre che è ansible farlo non solo in O (n 2 ) ma in O (n) tempo !

[ Aggiornamento: un documento pubblicato nel 2017 ha mostrato con l’esempio che la soluzione O (n) non funziona per una specifica class di poligoni. Vedi questa risposta per maggiori dettagli. Ma l’algoritmo O (n 2 ) è ancora corretto.]

Prima ordinando i punti / calcolando lo scafo convesso (nel tempo O (n log n)), se necessario, possiamo assumere che abbiamo il poligono / scafo convesso con i punti ordinati ciclicamente nell’ordine in cui appaiono nel poligono. Chiama i punti 1, 2, 3, …, n. Sia i punti (variabili) A, B e C, iniziano come 1, 2 e 3 rispettivamente (nell’ordine ciclico). Ci sposteremo A, B, C fino a quando ABC è il triangolo dell’area massima. (L’idea è simile al metodo dei calibri rotanti , usato quando si calcola il diametro (coppia più lontana) .)

Con A e B fissi, avanza C (es. Inizialmente, con A = 1, B = 2, C è avanzato attraverso C = 3, C = 4, …) finché l’area del triangolo aumenta, cioè fino a quando Area (A, B, C) ≤ Area (A, B, C + 1). Questo punto C sarà quello che massimizza l’Area (ABC) per quelli fissi A e B. (In altre parole, la funzione Area (ABC) non è unimodale come una funzione di C.)

Quindi, fai avanzare B (senza cambiare A e C) se questo aumenta l’area. Se è così, anticipa nuovamente C come sopra. Quindi, se ansible, avanza nuovamente su B, ecc. Questo darà al triangolo area massimo con A uno dei vertici.

(La parte fino a qui dovrebbe essere facile da provare, e semplicemente facendo questo separatamente per ogni A darebbe un algoritmo O (n 2 ).)

Ora avanza nuovamente A, se migliora l’area e così via. (La correttezza di questa parte è più sottile: Dobkin e Snyder hanno dato una dimostrazione nel loro articolo, ma un recente articolo mostra un controesempio: non l’ho ancora capito.)

Anche se questo ha tre loop “annidati”, nota che B e C avanzano sempre “avanti”, e avanzano al massimo 2n volte in totale (allo stesso modo A avanza al massimo n volte), quindi l’intera cosa viene eseguita in tempo O (n) .

Frammento di codice, in Python (la traduzione in C dovrebbe essere semplice):

# 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 

Questo algoritmo è dimostrato in Dobkin e Snyder, in un metodo generale per massimizzare e minimizzare tra alcuni problemi geometrici , FOCS 1979, e il codice sopra è una traduzione diretta del loro codice ALGOL-60. Chiedo scusa per le costruzioni while-if-break; dovrebbe essere ansible trasformarli in più semplici cicli.

rispondendo alla tua domanda correlata:

Il cerchio circoscritto del triangolo non è necessariamente il cerchio limite minimo del poligono. Per vedere questo, considera un triangolo isoscele molto piatto, ad esempio con i vertici in (0,0), (10,0) e (5,1). Il cerchio limite minimo ha centro (5,0) e raggio 5, ma questo cerchio non tocca il vertice in (5,1), quindi non è il circumcircle. (Il circumcircle ha centro (5, -12) e raggio 13)

modificare:

Scegliere il più piccolo circoncello o il cerchio contenente i punti antipodali del diametro del poligono non è sufficiente, perché è ansible build poligoni che hanno punti al di fuori del circonferenza del triangolo massimo. Considera il pentagono con i vertici a:

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

Il triangolo massimo ha vertici in (-4, -1), (5, 0) e (-4, 1). Il suo circumcircle non include il punto in (-5, 0).

Secondo questo articolo, esiste una class di poligoni convessi in cui l’algoritmo citato dalla risposta di ShreevatsaR fallisce. Il documento propone anche un algoritmo di divisione e conquista di O (n log n) per risolvere il problema.

Apparentemente, l’algoritmo O (n 2 ) più semplice in cui si spostano i punti B e C per tutti A è ancora valido.

da http://www.wolframalpha.com/input/?i=triangolo L’area del triangolo = sqrt ((a + bc) (a-b + c) (-a + b + c) * (a + b + c)) / 4 Se si usa c collegato ai punti finali del poligono convesso e se a e b tocchino il poligono convesso si può scorrere attorno al poligono permettendo a a crescere e b di restringersi fino a trovare la propria area massima. Vorrei iniziare a metà punto e provare ogni direzione per un’area più ampia.

So che questo è un vecchio post ma, facendo riferimento alla risposta di cui sopra, sono riuscito a modificare il codice per massimizzare l’area per un poligono n-sided.

Nota: lo scafo convesso è stato trovato utilizzando la libreria Emgu OpenCV . Sto usando il metodo CvInvoke.ContourArea() per calcolare l’area data di un poligono. Questo è scritto in C #. Presume anche che i punti siano disposti in senso orario. Questo può essere specificato nel metodo 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; } 

Il metodo area utilizzato. Questo potrebbe cambiare a seconda di ciò che è necessario per massimizzare.

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