Как найти прямоугольник максимальной площади внутри выпуклого многоугольника?

21

В этом посте мы ищем алгоритмы / идеи о том, как найти прямоугольник максимальной площади внутри выпуклого многоугольника .

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

Редактировать:

У нас нет четкого представления о том, как бороться с упомянутой проблемой, поэтому мы задали этот вопрос здесь. Тем не менее, мы предполагаем, что прямоугольник с максимальной площадью может быть одним из тех, у которых одно ребро выровнено по краю (конечно, не обязательно по длине одинаковой длины) ребра многоугольника.

введите описание изображения здесь

разработчик
источник
1
Не могли бы вы указать, какое программное обеспечение вы используете? Кроме того, опубликуйте свою работу так далеко, или общий подход, который вы разработали, чтобы решить эту проблему. Может быть, кто-то может улучшить то, что вы уже сделали. По моему опыту, это приведет к гораздо более полезным ответам, чем просто вопрос «на ровном месте».
Мартин
1
Тесно связанные: gis.stackexchange.com/questions/22895/… .
whuber
@Martin Software: программирование Pythonбудет включено, Fortranесли потребуется. У нас есть предположение , что , основываясь на нашем предыдущем посте здесь также упоминалось выше, whuberэто может быть прямоугольник с краем общего с полигона будет ответ.
Разработчик
1
Ваша проблема действительно интересная, и я думаю, что мне удалось найти алгоритм решения здесь и здесь .
nickves
1
@nickves Спасибо за ссылки. Не могли бы вы поставить эту информацию в качестве ответа с небольшим объяснением алгоритмов? Это будет потенциально хороший ответ, который будет принят.
Разработчик

Ответы:

4

Некоторые заметки слишком велики, чтобы помещать их в комментарии (хотя это не предполагает очевидного алгоритма):

Штриховая линия (РЕДАКТИРОВАНИЕ) : По крайней мере две вершины прямоугольника максимальной площади должны лежать на границе многоугольника (то есть вдоль края или в вершине). И если прямоугольник максимальной площади не является квадратом, то по крайней мере три вершины должны лежать на границе многоугольника.

Я доказал это себе в четыре этапа:

Примечание № 1 : По крайней мере одна вершина прямоугольника максимальной площади всегда будет лежать на границе многоугольника. Это довольно очевидно, но доказательство может выглядеть следующим образом (противоречие): предположим, у вас был «максимальный» прямоугольник без вершины на границе многоугольника. Это означает, что вокруг каждой его вершины будет хотя бы небольшое пространство. Таким образом, вы можете немного расширить свой прямоугольник, что противоречит его максимальности.

Примечание № 2 : По крайней мере две вершины прямоугольника максимальной площади всегда будут лежать на границе многоугольника. Доказательство может выглядеть следующим образом (опять противоречие). Предположим, у вас был «максимальный» прямоугольник с единственной вершиной на границе (гарантируется примечанием № 1). Рассмотрим два ребра, не смежные с этой вершиной. Поскольку их конечные точки НЕ находятся на границе, вокруг каждого есть небольшое пространство. Таким образом, любой из этих ребер можно немного «выдавливать», расширяя площадь многоугольника и противореча его максимальности.

Примечание № 3 : Есть две противоположные по диагонали вершины прямоугольника максимальной площади, которые лежат на границе многоугольника. (Мы знаем из примечания № 2, что есть по крайней мере два, но не обязательно, что они находятся напротив друг друга.) Но опять-таки из-за противоречия, если только две граничные вершины были смежными, то противоположный край (ни одна из вершин которого находятся на границе), может немного выдавливаться, увеличивая площадь прямоугольника и противореча его максимальности.

Примечание № 4 : (ИЗМЕНЕНО). Если прямоугольник максимальной площади не является квадратом, то три его вершины будут лежать на границе многоугольника.

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

Назовите вершины прямоугольника A, B, C, и D. Без ограничения общности предположим, что Bи Dте два, которые находятся на границе многоугольника. Так Aи Cнаходятся на внутренней стороне многоугольника, есть какой - то пространство для маневра вокруг них (представлен с кругами вокруг Aи Cв картине ниже). Теперь нарисуйте круг вокруг прямоугольника, и сдвиньте точки Aи Cнемного вокруг круга на одинаковую величину (чтобы сделать A'и C', как показано ниже), чтобы новый прямоугольникA'BC'Dявляется более квадратным, чем исходный прямоугольник. Этот процесс создает новый прямоугольник, который также находится внутри исходного многоугольника и имеет большую площадь. Это противоречие, поэтому доказательство сделано.

Построение нового прямоугольника

Чтобы верить этому доказательству, вы должны убедить себя в том, что площадь прямоугольника, вписанного в круг, увеличивается, когда он становится «более квадратным» (т. Е. Разница между длинами ребер уменьшается). Вам также нужно, чтобы многоугольник был выпуклым, чтобы все новые линии были внутри него. И, возможно, есть и другие мелкие детали, скрывающиеся под ковром, но я уверен, что все они сработают.

CSD
источник
Примечание № 4 подозрительно, потому что «покачивание» двух других вершин создаст не прямоугольники.
whuber
Правда. Однако ваша визуализация 4-го примера не совсем верна (если 2 вершины находятся на границе многоугольника, вы не можете растянуть его дальше). Хотя я не могу точно найти, как это объяснить (пытался написать комментарий, но слишком запутался), но я верю, что вы правы.
Сарык
Я считаю, что есть контрпримеры к примечанию № 4. Однако те, которые я нашел, требуют некоторых вычислений; самое простое - это возмущение неправильного шестиугольника (квадрат со слегка срезанными двумя противоположными углами).
whuber
Согласился, что Примечание № 4 подозрительно. Сегодня вечером я посмотрю поближе и либо исправлю, либо уберу.
csd
+1 Это хорошее разрешение трудности. Спасибо за редактирование!
whuber
3

Я сделал очень быстрый и отвратительный набросок о вашей зеленой заметке в вопросе. Я не мог опубликовать его как комментарий, поэтому мне пришлось написать ответ, даже если он не один.
Я считаю, что на изображении ниже у нас есть прямоугольник с максимальной площадью (не идеальный, это просто эскиз, сделанный на Paint, чтобы дать идею), и я не думаю, что вы можете найти больший, который будет иметь общую сторону с границы черного плигона ...
Однако я могу ошибаться, в этом случае у вас есть все мои извинения.
Быстрый эскиз, который я сделал на Paint

сарык
источник
3
Хорошая точка (+1). Однако существует гораздо более простой контрпример: рассмотрим проблему вписывания прямоугольника максимальной площади в правильный восьмиугольник. Легко увидеть (и легко доказать, сначала найдя максимальный квадрат внутри окружности восьмиугольника), что углы решения совпадают с чередующимися вершинами восьмиугольника и что это решение существенно больше любого вписанного в ребро вписанного прямоугольника.
whuber
На самом деле (сейчас у меня есть большие сомнения), внешний маленький прямоугольник (из этого поста ) этого многоугольника не имеет ту же ориентацию, что и одна из сторон, верно ? (Я бы увидел ту же ориентацию, что и мой красный прямоугольник)
Сарык,
3
Кстати, этот многоугольник не выпуклый. Оригинальный вопрос ограничивается выпуклыми многоугольниками.
csd
2
@csd Это отличный момент, но Сарык все еще прав, как показывает мой контрпример. Сарык, нет проблем с ограничивающим прямоугольником минимальной площади: легко доказать (строго), что он должен включать в себя сторону выпуклой оболочки. Я считаю, что максимальная площадь вписанного прямоугольника (выпуклого многоугольника) должна иметь только две вершины, соприкасающиеся с границей, не более.
whuber
2

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

Тем не менее, в статье Knauer et al. Самые большие вписанные прямоугольники в выпуклых многоугольниках . al., описывает алгоритм аппроксимации, который приблизит вас к правильному ответу.

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

lreeder
источник
Возможно ли опечатка в первом предложении? Не может быть алгоритма O (log (n)), потому что простое чтение в координатах - это операция O (n)!
whuber
Ссылка мертва
опасно
1
@dangerousdave - нашел альтернативную ссылку на
сколько угодно