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

Какой алгоритм позволяет вписать прямоугольник максимальной площади в линейный многоугольник, все углы которого прямые?
spoiler
631b0b21747fa369935400.png
  • Вопрос задан
  • 1099 просмотров
Пригласить эксперта
Ответы на вопрос 4
Adamos
@Adamos
Если все угля прямые - это не многоугольник, а составная фигура из прямоугольников.
Разбить на мельчайшие (первая фигура - на три, вторая - на пять) и комбинаторикой проверить, какие с какими складываются в более крупные, сравнивая результирующую площадь.
Собственно, если оно, как на рисунке, состоит из квадратиков - первый этап уже выполнен.
Ответ написан
Комментировать
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Если результат не должен быть горизонтально-вертикальным по условию, то в оптимальный прямоугольник может быть и наклонен (смотрите замечательный контр-пример от dollar).

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

Но тут слишком много случаев. Это очень сложная задача строк этак на 1000 мозгодробящей геометрии.
Ответ написан
Комментировать
BasiC2k
@BasiC2k
.NET developer (open to job offers)
Попробуйте подумать - а как Вы (как человек) решаете эту задачу (визуально)?
Я:
1. Определил внутреннюю область (точку) многоугольника, которую "видят" как можно больше граней. Это - точка, в которой можно построить наибольшую по площади фигуру. Таких точек может быть несколько;
2. Строю в этой точке прямоугольник с наибольшей площадью (в вертикальной или горизонтальной ориентации);
3. Начинаю вертеть и смещать прямоугольник для достижения максимальной площади.
Уверен, что этот алгоритм можно переложить в программную реализацию.
Ответ написан
@iingvaar
Посмотрите это видео: https://youtu.be/QJC27E9bvqU
В нём дана идея алгоритма. Вкратце - это частный случай гипотезы Тёплица. Для нахождения вписанного прямоугольника можно особым образом "развернуть" фигуру в единичный квадрат и построить на нём функцию расстояний между всеми парами точек контура. Можно сделать это, например, с некоторым малым шагом дискретизации. Точки самопересечения построенной функции дадут координаты углов вписанного прямоугольника.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы