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

10 minutos de lectura

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

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

  • No, estoy trabajando en la detección de colisiones de formas poligonales para juegos de iPhone. El círculo límite mínimo me permitiría seleccionar el conjunto de formas potencialmente colisionantes antes de realizar pruebas de intersección polígono-polígono más costosas. En el proceso, estoy aprendiendo algoritmos de geometría computacional y traduciéndolos a Objective-C. En el futuro, probablemente solo use una biblioteca de física, pero quiero saber cómo funciona desde cero.

    – willc2

    25 de octubre de 2009 a las 18:56

  • Descubrí que poner demasiados detalles en una pregunta es malo, ya que las personas tienden a responder las preguntas más interesantes (implícitas) en lugar de la indicada si es “demasiado simple”. Como novato, nada es simple.

    – willc2

    25 de octubre de 2009 a las 19:01

  • Anote la respuesta de la pregunta secundaria pero no la principal. Lamento llamarte Stephan, es mi culpa por intentar un doble.

    – willc2

    25 de octubre de 2009 a las 19:13

avatar de usuario
ShreevatsaR

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

Por fuerza bruta, supongo que te refieres a verificar todos los triples de puntos y elegir el que tiene el área máxima. esto corre en En3) horapero resulta que es posible hacerlo no solo en O(n2) pero en A tiempo!

[Update: A paper published in 2017 showed by example that the O(n) solution doesn’t work for a specific class of polygons. See this answer for more details. But the O(n2) algorithm is still correct.]

Al ordenar primero los puntos/calcular el casco convexo (en 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 a la pinzas giratorias método, tal como se utiliza al calcular el diámetro (par más lejano).)

Con A y B fijos, avance C (por ejemplo, inicialmente, con A=1, B=2, C se avanza a través de 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 los fijos A y B. (En otras palabras, la función Área(ABC) es unimodal en función de C.)

A continuación, avance B (sin cambiar A y C) si eso aumenta el área. Si es así, vuelva a avanzar C como se indicó anteriormente. Luego avance B nuevamente si es posible, etc. Esto dará el triángulo de á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 O(n2) algoritmo.)

Ahora avanza A de nuevo, 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 “hacia adelante”, y avanzan como máximo 2n veces en total (de manera similar, A 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 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 se prueba en Dobkin y Snyder, Sobre 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 while más simples.

  • ¿Esto es realmente O(n)?

    – Ninja420

    24/08/2013 a las 19:31


  • @Ninja420: Sí, lo es. Ya he dado una prueba en la respuesta anterior; también puede leer el documento vinculado para obtener uno más detallado.

    – ShreevatsaR

    25 de agosto de 2013 a las 9:34

  • Pregunta relacionada, sería bueno si pudiera proporcionar una descripción detallada aquí, stackoverflow.com/questions/18423040/…

    – Ninja420

    25 de agosto de 2013 a las 14:12

  • @Ninja420: Ah, ya veo. Sí, el hecho de que B y C avancen solo 2n veces cada uno debe haberme parecido obvio cuando escribí la respuesta, pero ahora parece sutil … ¡claramente me estoy haciendo mayor! Lo pensaré y publicaré una respuesta en la otra pregunta cuando vuelva a estar claro para mí.

    – ShreevatsaR

    26 de agosto de 2013 a las 9:54

  • @VikashB No, eso no es cierto. Por ejemplo, si observa la figura del papel (vea esta respuesta), no parece ser el caso de que el diámetro del polígono sea un lado de cualquiera de los tres “máximos locales anclados”. De manera más general, imagine un n-ágono regular para n grande, de modo que casi se asemeje a un círculo. El triángulo de área máxima es un triángulo equilátero, no un triángulo que tiene el diámetro como uno de los lados.

    – ShreevatsaR

    30/09/2016 a las 16:45

De acuerdo a esta papel, hay una clase de polígonos convexos en los que falla el algoritmo citado por la respuesta de ShreevatsaR. El artículo también propone un algoritmo de dividir y vencer O(n log n) para resolver el problema.

Aparentemente, cuanto más simple es O(n2) algoritmo en el que se mueven los puntos B y C para todos A sigue siendo válido.

  • Dado que esto no responde a la pregunta en sí, probablemente debería ir como un comentario sobre la respuesta de @ShreevatsaR

    – B.Eckles

    2 de junio de 2017 a las 19:26

  • @B.Eckles Lo siento, es la primera vez que contribuyo. Desafortunadamente, no tengo suficiente reputación para comentar la respuesta. Y dado que el documento vinculado proponía un algoritmo para resolver el problema, pensé que mi publicación calificaba como una respuesta.

    – Tomasf

    2 de junio de 2017 a las 19:58

  • ¡Tiene sentido para mi!

    – B.Eckles

    5 jun 2017 a las 16:50

  • Gracias por la corrección. De alguna manera me perdí esto antes. Todavía no he probado ni entendido el contraejemplo, pero es bueno saber que está en disputa.

    – ShreevatsaR

    6 de marzo de 2018 a las 2:18

avatar de usuario
Esteban Canon

respondiendo a su pregunta relacionada:

El circuncírculo del triángulo no es necesariamente el círculo límite 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 límite 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 el círculo circunscrito. (El circuncírculo tiene centro (5,-12) y radio 13)

editar:

Elegir el más pequeño del circuncírculo o el círculo que contiene los puntos antípodas del diámetro del polígono tampoco es suficiente, porque es posible construir polígonos que tengan puntos fuera del circuncírculo 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).

  • ¿Qué tal si tomo el menor de: el Circuncírculo (del triángulo más grande) o un círculo centrado entre los puntos antípodas?

    – willc2

    25 de octubre de 2009 a las 19:28

  • Genial, ese es un ingenioso contraejemplo. Sospeché que tal existiría, pero no se me ocurrió ninguno… Por cierto, creo que es posible probar que el círculo delimitador mínimo tendrá algún par como diámetro, o será el circuncírculo de algunos triángulo.

    – ShreevatsaR

    25 de octubre de 2009 a las 20:47

  • Sí, creo que eso es cierto.

    – Esteban Canon

    25 de octubre de 2009 a las 21:25

desde 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 tocan su polígono convexo, podría iterar alrededor de su polígono permitiendo un para crecer y b para encoger hasta encontrar su área máxima. Comenzaría en el punto medio y probaría cada dirección para un área más grande.

avatar de usuario
Félix Castor

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 Biblioteca Emgu OpenCV. Estoy usando CvInvoke.ContourArea() método para calcular el área dada de un polígono. Esto está escrito en C#. También supone que los puntos están dispuestos 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 del área utilizado. Esto podría cambiar dependiendo de lo que se necesite maximizar.

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

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad