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

#алгоритм #графика

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



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


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


Этот алгоритм работал хорошо для большинства фигур, в том числе и для той, что приведена
на первом рисунке. Но вот столкнулся с фигурой со второго рисунка:



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

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



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

Ответы

Ответ 1

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

Я попробую провести аналогию с методом «вращающегося штангенциркуля» (не знаю хорошего
русского названия).

Рассмотрим охватывающие прямоугольники, у которых основание идёт под некоторым углом
φ к горизонтали. Пусть S(φ) — площадь этого прямоугольника. Наша цель — найти экстремум
этой функции на [0, π/2).

Пускай для начала φ = 0. Рассмотрим охватывающий прямоугольник:



В нашем случае, стороны охватывающего прямоугольника проходят через вершины A₁, A₄
и A₁, A₅ соответственно. Для начала, найдём диапазон значений угла φ, при которых это
всё ещё будет так. Найдём сначала, как далеко можно повернуть нижнее основание, чтобы
нижняя сторона всё ещё опиралась на вершину A₁. Этим углом будет минимальный из углов
лучей A₁A₂, A₁A₃, A₁A₄, A₁A₅. Аналогично находим диапазоны поворота для остальных четырёх
сторон. Пересечение этих диапазонов и даст тот диапазон значений φ, внутри которого
охватывающий прямоугольник опирается на те же вершины.

Для этого диапазона найдём экстремальное значение площади. Пусть угол отрезка A₁A₄
с горизонталью равен φ₁, а угол отрезка A₁A₅ — φ₂. Обозначим d₁ = |A₁A₄|, d₂ = |A₁A₅|
Вертикальная сторона прямоугольника равна d₁ sin(φ − φ₁), горизонтальная — d₂ sin(φ
+ π/2 − φ₂) = d₂ cos(φ − φ₂).

Площадь равна d₁d₂ sin(φ − φ₁) cos(φ − φ₂) = d₁d₂ (sin (2φ − φ₁ − φ₂) + sin (φ₂ −
φ₁))/2. Для того, чтобы найти экстремум этой величины, можно отбросить константы d₁d₂/2
и sin (φ₂ − φ₁), и вспомнить, что минимум у синуса достигается в точке, где аргумент
равен 3π/2 + k · 2π, или на концах отрезка.

Сравнив между собой значение площади на концах отрезка, а также в точках вида 3π/4
+ (φ₁ + φ₂)/2 + k · π (если они попадают на отрезок), получим минимум на этом отрезке.

Окей. Дальше просто. Поворачивая основание дальше, переходим к рассмотрению случая,
когда опорной точкой нижнего основания является A₅, повторяем рассмотрение на этом
отрезке значений φ. Продолжаем до тех пор, пока φ не достигнет величины π/2.

Всё.



Вам понадобится ещё обобщить этот алгоритм для случая кривых сторон. Здесь опорная
точка будет катиться по дуге с изменением φ, что, в принципе, позволяет провести такое
же рассмотрение.

Дерзайте!