Cómo encontrar el triángulo más grande en el casco convexo aparte de la búsqueda de fuerza bruta

Dado un polígono convexo, ¿cómo encuentro los 3 puntos que definen un triángulo con el área más grande?

Relacionado: ¿Es verdad que la circunferencia circunscrita de ese triángulo también definiría el círculo delimitador mínimo del polígono?

Sí, puedes hacer mucho mejor que la fuerza bruta.

Por fuerza bruta, supongo que te refieres a verificar todos los triples de puntos y elegir el que tenga el área máxima. Esto se ejecuta en el tiempo O (n 3 ) , pero resulta que es posible hacerlo no solo en O (n 2 ) sino en O (n) tiempo .

[ Actualización: un documento publicado en 2017 mostró por ejemplo que la solución O (n) no funciona para una clase específica de polígonos. Vea esta respuesta para más detalles. Pero el algoritmo O (n 2 ) sigue siendo correcto.]

Primero ordenando los puntos / calculando el casco convexo (en el tiempo O (n log n)) si es necesario, podemos suponer que tenemos el polígono / casco convexo con los puntos ordenados cíclicamente en el orden en que aparecen en el polígono. Llame a los puntos 1, 2, 3, …, n. Deje que los puntos (variable) A, B y C comiencen como 1, 2 y 3 respectivamente (en el orden cíclico). Moveremos A, B, C hasta que ABC sea el triángulo de área máxima. (La idea es similar al método de calibradores giratorios , como se usa cuando se calcula el diámetro (el par más lejano) .)

Con A y B fijos, avance C (por ejemplo, inicialmente, con A = 1, B = 2, C avanza a través de C = 3, C = 4, …) siempre que el área del triángulo aumente, es decir, siempre que Área (A, B, C) ≤ Área (A, B, C + 1). Este punto C será el que maximice el Área (ABC) para aquellos A y B fijos (en otras palabras, el Área de función (ABC) es unimodal como una función de C.)

Luego, avance B (sin cambiar A y C) si eso aumenta el área. Si es así, nuevamente avance C como arriba. Luego, avance B de ser posible, etc. Esto dará el triángulo de área máximo con A como uno de los vértices.

(La parte hasta aquí debe ser fácil de probar, y simplemente hacer esto por separado para cada A daría un algoritmo O (n 2 ).)

Ahora avance A nuevamente, si mejora el área, y así sucesivamente. (La corrección de esta parte es más sutil: Dobkin y Snyder dieron una prueba en su artículo, pero un documento reciente muestra un contraejemplo. Todavía no lo he entendido).

Aunque esto tiene tres bucles “nesteds”, tenga en cuenta que B y C siempre avanzan “adelante”, y avanzan como máximo 2n veces en total (de manera similar, avanza como máximo n veces), por lo que todo se ejecuta en O (n) tiempo .

Fragmento de código, en Python (la traducción a C debería ser directa):

# 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 

Este algoritmo se demuestra en Dobkin y Snyder, en un método general para maximizar y minimizar entre ciertos problemas geométricos , FOCS 1979, y el código anterior es una traducción directa de su código ALGOL-60. Disculpas por las construcciones while-if-break; debería ser posible transformarlos en ciclos más simples.

respondiendo su pregunta relacionada:

La circunferencia circunscrita del triángulo no es necesariamente el círculo delimitador mínimo del polígono. Para ver esto, considera un triángulo isósceles muy plano, digamos con vértices en (0,0), (10,0) y (5,1). El círculo delimitador mínimo tiene centro (5,0) y radio 5, pero este círculo no toca el vértice en (5,1), por lo que no es circunferencia circunscrita. (La circunferencia circunscrita tiene el centro (5, -12) y el radio 13)

editar:

Tampoco es suficiente elegir el círculo circunscrito más pequeño o el círculo que contiene los puntos antipodales del diámetro del polígono, ya que es posible construir polígonos que tengan puntos fuera del circunferencia circunscrita del triángulo máximo. Considere el pentágono con vértices en:

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

El triángulo máximo tiene vértices en (-4, -1), (5, 0) y (-4, 1). Su circunferencia circunscrita no incluye el punto en (-5, 0).

Según este artículo, existe una clase de polígonos convexos en los que falla el algoritmo citado por la respuesta de ShreevatsaR. El documento también propone un algoritmo de división y conquista O (n log n) para resolver el problema.

Aparentemente, el algoritmo O (n 2 ) más simple en el que mueve los puntos B y C para todos los A sigue siendo válido.

desde http://www.wolftwiglpha.com/input/?i=triangle El área del triángulo = sqrt ((a + bc) (a-b + c) (-a + b + c) * (a + b + c)) / 4 Si usa c conectado a los puntos finales de su polígono convexo y si ayb tocarían su polígono convexo, podría iterar alrededor de su polígono permitiendo que crezca y b encoja hasta que encuentre su área máxima. Comenzaría en el punto medio y probaría cada dirección para un área más grande.

Sé que esta es una publicación anterior, pero al hacer referencia a la respuesta anterior , pude modificar el código para maximizar el área de un polígono de n lados.

Nota: El casco convexo se encontró usando la biblioteca Emgu OpenCV . Estoy usando el método CvInvoke.ContourArea() para calcular el área dada de un polígono. Esto está escrito en C #. También supone que los puntos están ordenados en el sentido de las agujas del reloj. Esto se puede especificar en el método 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; } 

El método de área utilizado. Esto podría cambiar según lo que se necesite para maximizar.

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