Учитывая выпуклый многоугольник, как найти три точки, которые определяют треугольник с наибольшей площадью.
Связано: Верно ли, что окружность этого треугольника также будет определять минимальную ограничительную окружность многоугольника?
Как найти наибольший треугольник в выпуклом корпусе, кроме поиска грубой силы
Ответ 1
Да, вы можете сделать значительно лучше, чем грубая сила.
По грубой силе я предполагаю, что вы имеете в виду проверку всех троек точек и выбор одного с максимальной площадью. Это выполняется в O (n 3) времени, но оказывается, что это возможно сделать не только O (n 2), , но в O (n) времени!
[ Обновление: Документ, опубликованный в 2017 году, показал на примере, что решение O (n) не работает для определенного класса полигонов. Подробнее см. этот. Но алгоритм O (n 2) по-прежнему правилен.]
Сначала отсортировав точки/вычислив выпуклую оболочку (в 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 будет той, которая максимизирует Area (ABC) для тех фиксированных A и B. (Иными словами, функция Area (ABC) является унимодальной как функция от C.)
Затем, вперед B (без изменения A и C), если это увеличивает площадь. Если это так, снова продвигайте C, как указано выше. Затем, если возможно, продвигайте B снова и т.д. Это даст максимальный треугольник площади с A как одной из вершин.
(Часть здесь должна быть легко доказана, и просто делать это отдельно для каждого А даст алгоритм O (n 2).)
Теперь снова запустите A, если он улучшит область и т.д. (Правильность этой части более тонкая: Добкин и Снайдер дали доказательство в своей статье, но в недавней статье показан контрпример. еще не поняли его.)
Хотя у этого есть три "вложенных" цикла, обратите внимание на то, что B и C всегда продвигают "вперед", и они продвигаются не более чем в 2 раза (в общем случае A достигает максимум n раз), поэтому все происходит в O ( n) время.
Кодовый фрагмент в 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 и приведенный выше код является прямым переводом их кода ALGOL-60. Извинения за конструкции "пока-разломы"; это должно быть возможным, чтобы превратить их в более простые, в то время как петли.
Ответ 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).
Ответ 3
В соответствии с этот документ, существует класс выпуклых многоугольников, в котором алгоритм, приведенный в ответ ShreevatsaR, терпит неудачу. В статье также предлагается алгоритм деления и захвата O (n log n) для решения проблемы.
По-видимому, все еще действует более простой алгоритм O (n 2), в котором вы перемещаете точки B и C для all A.
Ответ 4
from http://www.wolframalpha.com/input/?i=triangle Площадь треугольника = sqrt ((a + b-c) (a-b + c) (- a + b + c) * (a + b + c))/4 Если вы используете c, связанный с конечными точками вашего выпуклого многоугольника и если a и b коснутся вашего выпуклого многоугольника вы можете выполнять итерацию вокруг своего полигона позволяя расти и b, чтобы сжиматься, пока вы не найдете свою максимальную площадь. Я бы начал среднюю точку и пробовал каждое направление для большей области.
Ответ 5
Я знаю, что это старый пост, но, ссылаясь на ответ выше, я смог изменить код, чтобы максимизировать область для n-стороннего многоугольника.
Примечание. Выпуклая оболочка была найдена с использованием библиотеки Emgu OpenCV. Я использую метод CvInvoke.ContourArea() для вычисления данной области многоугольника. Это написано на С#. Он также предполагает, что точки расположены по часовой стрелке. Это можно указать в методе 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);
}