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

[mitrik]

Добрый день всем! Столкнулся с необходимостью поиска прямоугольника максимальной площади, вписанного в многоугольник, заданный координатами. Попробовал прицепиться к стороне, лежащей напротив самой длинной, но нет доказательств, что именно там он будет находится и вообще будет ли параллелен одной из сторон исходного объекта. Дайте, пожалуйста, наводку за что можно зацепиться. Спасибо

[knizhnik]

mitrik в сообщении #1186101 писал(а):

многоугольник, заданный координатами.

А как у вас многоугольник задан координатами и в каком координатном пространстве? Нужно подробнее.
Если фигура достаточно проста, может и можно получить конкретное выражение зависимости в каких-нибудь полярных координатах. Но пока ничего не известно.

mitrik в сообщении #1186101 писал(а):

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

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

[mitrik]

Обычная декартова система координат. Может быть стоит поискать вписанный эллипс, максимальной площади, а потом найти вписанный в него прямоугольник

[knizhnik]

mitrik в сообщении #1186110 писал(а):

Обычная декартова система координат.

$\mathbb{R}^2$ что ли?

mitrik в сообщении #1186110 писал(а):

Может быть стоит поискать вписанный эллипс, максимальной площади, а потом найти вписанный в него прямоугольник

А может быть по другому, когда надо найти описанный вокруг него прямоугольник. Все может быть.
Какой конкретный вид фигуры - не сказали. Секрет?

[Brukvalub]

Я понял задачу так: задан набор координат - вершин многоугольника. Требуется "вписать" в многоугольник прямоугольник наибольшей площади. "Вписать" - это так расположить прямоугольник, чтобы все его вершины лежали на сторонах многоугольника?

[knizhnik]

Я понял по-другому, "вписать" - как расположить внутри. Это все тоже требует уточнения.

[arseniiv]

Ага, и правда, кто сказал, что все вершины прямоугольника максимальной площади, целиком входящего в данную фигуру, должны лежать на сторонах. Я даже уже придумал пример фигуры, в которой ни одна вершина такого прямоугольника не лежит на её сторонах: рассмотрим восьмиугольник, полученный из прямоугольника, к которому добавили по вершине на каждой стороне, фиксируем эти добавленные вершины и немного оттягиваем в стороны от центра старые. Получается «неправильная звезда», и если оттянуть вершины достаточно далеко, никаких других прямоугольников площади, не меньшей площади исходного, в ней содержаться не должно.

[knizhnik]

arseniiv в сообщении #1186192 писал(а):

целиком входящего в данную фигуру

arseniiv, это существенное уточнение. Потому что если понимать так, как говорит Brukvalub, просто располагая вершины на сторонах, то это всегда возможно, хотя и не вполне соответствует общей сути слова "вписать". Тем же способом можно и "описать", и ничего страшного не произойдет.

[arseniiv]

knizhnik в сообщении #1186219 писал(а):

это существенное уточнение

Хм, ну, я подумал, что уж оно-то с самого начала всеми понималось присутствующим, раз уж говорится о площади. А действительно, у ТС не упомянуто.

Интересно спросить ещё и то, не всегда ли многоугольник будет выпуклым. Это точно должно как-то упрощать дела. Хотя бы одна вершина прямоугольника должна будет, по идее, лежать на границе многоугольника, даже если «вписанность» понимать как у меня.

[mitrik]

Отвечаю на все поставленные вопросы.

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

[atlakatl]

В общем случае только численное сканирование.
Для выпуклой фигуры три точки прямоугольника всяко будут лежать на её сторонах. Остаётся аккуратно запрограммировать перебор положения средней точки по периметру фигуры и угла выходящей из неё стороны прямоугольника.

[grizzly]

atlakatl в сообщении #1186321 писал(а):

В общем случае только численное сканирование.

Это должно быть как-то сразу очевидно? (я с ходу не могу сообразить, почему; скажу прямо -- моя интуиция не хочет этому верить на слово :)

[atlakatl]

grizzly
Выпуклый многоугольник - когда "много" очень большое - это в пределе замкнутая кривая, в общем случае иррациональная.
О какой общей формуле может идти речь? Даже интегрируется аналитически ничтожная часть произвольных функций. А здесь схожая задача.

[DeBill]

atlakatl в сообщении #1186321 писал(а):

Для выпуклой фигуры три точки прямоугольника всяко будут лежать на её сторонах

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

[slavav]

DeBill в сообщении #1186335 писал(а):

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

Вы правы. У меня получились такие условия: или квадрат на диаметре (диаметр здесь - длиннейший вписанный отрезок) или три точки на границе.
Первый случай вообще дискретный - надо перебирать конечное число возможностей.
Второй сложнее - имеем площадь как непрерывную кусочно гладкую функцию от направления стороны прямоугольника. Требуется построить все отрезки гладкости, на каждом надо найти максимум. И это ещё дырявое описание.

-- 21.01.2017, 16:28 --

Поспешишь - людей насмешишь. Не квадрат на диаметре, а квадраты на всех опорных парах (их линейное число). Или квадраты на всех диагоналях (их квадратичное число).