graham - envolvente convexa c++

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

Question

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

Relacionado: ¿Es cierto que el circuncírculo de ese triángulo también definiría el círculo de delimitación mínimo del polígono?

Answer 1

De acuerdo con this documento, hay 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 ² ) más simple en el que mueves los puntos B y C para todo A sigue siendo válido.

Answer 2

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

Nota: El casco convexo se encontró utilizando 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 dependiendo de lo que se necesita para maximizar.

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

Answer 3

Sí, puedes hacerlo significativamente 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 tiempo O (n ³ ) , pero resulta que es posible hacerlo no solo en O (n ² ) sino en tiempo O (n) .

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

Al ordenar primero los puntos / calcular el casco convexo (en tiempo O (n log n)) si es necesario, podemos asumir que tenemos el polígono / casco convexo con los puntos clasificados cíclicamente en el orden en que aparecen en el polígono. Llama a los puntos 1, 2, 3,…, n. Los puntos (variables) A, B y C comienzan 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 para calcular 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 hasta C = 3, C = 4, ...) siempre que aumente el área del triángulo, es decir, mientras Área (A, B, C) ≤ Área (A, B, C + 1). Este punto C será el que maximice el Área (ABC) para aquellos que están fijos A y B. (En otras palabras, la función Área (ABC) es unimodal como una función de C).

A continuación, avance B (sin cambiar A y C) si eso aumenta el área. Si es así, vuelve a adelantar C como antes. Luego avance B nuevamente, si es posible, etc. Esto le dará al triángulo del área máxima con A como uno de los vértices.

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

Ahora avanza de nuevo A, 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 artículo reciente muestra un contraejemplo. Todavía no lo he entendido).}

Aunque esto tiene tres bucles "anidados", tenga en cuenta que B y C siempre avanzan "adelante", y avanzan como máximo 2n veces en total (de manera similar, A avanza como máximo n veces), por lo que todo funciona en O (n) .

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

 # 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 está probado 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 bucles mientras más simples.

Answer 4

from http://www.wolframalpha.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 a y b tocarían su polígono convexo, podría recorrer su polígono permitiendo que a crezca yb que se contraiga hasta que encuentre su área máxima. Comenzaría en el punto medio e intentaría cada dirección para un área más grande.

Answer 5

respondiendo a su pregunta relacionada:

El circuncírculo del triángulo no es necesariamente el círculo de delimitación mínimo del polígono. Para ver esto, considere 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 el centro (5,0) y el radio 5, pero este círculo no toca el vértice en (5,1), por lo que no es el circuncírculo. (El circuncírculo tiene centro (5, -12) y radio 13)

editar:

La elección del más pequeño del circuncírculo o del círculo que contiene los puntos antípodas del diámetro del polígono tampoco es suficiente, ya que es posible construir polígonos que tengan puntos fuera del circuncírculo del triángulo máximo. Considera 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 no incluye el punto en (-5, 0).