Как найти самый большой треугольник в выпуклой оболочке, кроме поиска грубой силы

Question

Учитывая выпуклый многоугольник, как мне найти 3 точки, которые определяют треугольник с наибольшей площадью.

Похожие: Правда ли, что окружность этого треугольника также определяет минимальную ограничивающую окружность многоугольника?

Answer 1

Да, вы можете сделать значительно лучше, чем перебор.

Под грубой силой я предполагаю, что вы имеете в виду проверку всех трех точек и выбор одной с максимальной площадью. Это выполняется за O (n ³ ) времени , но оказывается, что это можно сделать не только за O (n ² ) но в O (n) время !

[ Обновление: В статье, опубликованной в 2017 году, на примере показано, что решение O (n) не работает для определенного класса полигонов. См. этот ответ для более подробной информации. Но алгоритм O (n ² ) все еще корректен.]

Сначала отсортировав точки / вычислив выпуклую оболочку (за время O (n log n)), если необходимо, мы можем предположить, что имеем выпуклый многоугольник / оболочку с точками, циклически отсортированными в порядке их появления в многоугольнике. Назовите точки 1, 2, 3,…, n. Пусть (переменные) точки A, B и C начинаются с 1, 2 и 3 соответственно (в циклическом порядке). Мы будем двигаться A, B, C, пока ABC не станет треугольником максимальной площади. (Идея аналогична методу вращающихся суппортов , который используется при расчете диаметра (самая дальняя пара) .)

С фиксированными A и B, продвижение C (например, изначально, с A = 1, B = 2, C продвигается через C = 3, C = 4,…), пока увеличивается площадь треугольника, т.е. пока Площадь (A, B, C) ≤ Площадь (A, B, C + 1). Эта точка C будет той, которая максимизирует площадь (ABC) для фиксированных A и B. (Другими словами, функция Area (ABC) равна унимодально как функция от C.)

Затем продвиньтесь B (не изменяя A и C), если это увеличивает область. Если так, снова продвиньте C как выше. Затем продвиньте B снова, если это возможно, и т. Д. Это даст максимальный площадь треугольника с A в качестве одной из вершин.

(Доказанную часть легко доказать, и простое выполнение этого отдельно для каждого A даст алгоритм O (n ² ).)

Теперь снова продвигайте A, если это улучшает область, и т. Д. _{(Правильность этой части более тонкая: Добкин и Снайдер дали доказательство в своей статье, но недавняя статья показывает контрпример. I еще не поняла.)}

Хотя это имеет три «вложенных» цикла, обратите внимание, что B и C всегда продвигаются «вперед», и они продвигаются в большинстве не более 2n раз (аналогично A продвигается не более n раз), поэтому все это работает в O ( о) время.

Фрагмент кода в Python (перевод на C должен быть простым):

 # 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

Этот алгоритм доказан у Добкина и Снайдера, Об общем методе максимизации и минимизации среди определенных геометрических задач , FOCS 1979, и приведенный выше код является прямым переводом их Код АЛГОЛ-60. Извинения за конструкции while-if-break; должна быть возможность преобразовать их в более простые циклы while.

Answer 2

отвечая на ваш связанный вопрос:

Окружность треугольника не обязательно является минимальной ограничительной окружностью многоугольника. Чтобы увидеть это, рассмотрим очень плоский равнобедренный треугольник, скажем, с вершинами в (0,0), (10,0) и (5,1). Минимальный ограничивающий круг имеет центр (5,0) и радиус 5, но этот круг не касается вершины в (5,1), поэтому это не круг. (Окружность имеет центр (5, -12) и радиус 13)

редактирование:

Выбор меньшего из окружности или окружности, содержащей антиподальные точки диаметра многоугольника, также недостаточен, поскольку можно построить многоугольники, имеющие точки вне окружности максимального треугольника. Рассмотрим пятиугольник с вершинами в:

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

Максимальный треугольник имеет вершины в точках (-4, -1), (5, 0) и (-4, 1). Его окружность не включает точку в (-5, 0).

Answer 3

Согласно этой статье, существует класс выпуклых многоугольников, в котором алгоритм, процитированный ответом Шриеваца, терпит неудачу. В статье также предлагается алгоритм O (n log n) «разделяй и властвуй» для решения задачи.

Очевидно, что более простой алгоритм O (n ² ), в котором вы перемещаете точки B и C для все A, все еще действует.

Answer 4

Я знаю, что это старый пост, но, сославшись на ответ выше , я смог изменить код, чтобы максимально увеличить площадь для n-стороннего многоугольника.

Примечание: выпуклая оболочка была найдена с использованием библиотеки Emgu OpenCV . Я использую CvInvoke.ContourArea() метод для расчета заданной площади многоугольника. Это написано на C #. Также предполагается, что точки расположены по часовой стрелке. Это можно указать в методе 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;
}

Используемый метод площади. Это может измениться в зависимости от того, что необходимо для максимизации.

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

Answer 5

от http://www.wolframalpha.com/input/?i=triangle Площадь треугольника = sqrt ((a + b-c) (a-b + c) (- a + b + c) * (a + b + c)) / 4 Если вы используете c, связанный с конечными точками вашего выпуклого многоугольника и если а и б коснется вашего выпуклого многоугольника Вы можете перебирать свой полигон позволяя a расти и b уменьшаться, пока вы не найдете свою максимальную площадь. Я бы начал середину и попробовал каждое направление для большей области.