Максимальный эллипс вписанный в многоугольник


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

Def<Ellipse2d> maxFixEllipseInConvexPolygon ( double ext, CArrRef<Vector2d> poly );
Входные параметры: ext - удлинение эллипса ( 1e-6 <= ext <= 0.99 ) и poly - массив вершин многоугольника.

Функция maxFixEllipseInPolygon вписывает эллипс с заданным удлинением в невыпуклый многоугольник:
Def<Ellipse2d> maxFixEllipseInPolygon ( double ext, CArrRef<Vector2d> poly );
Входные параметры: ext - удлинение эллипса ( 1/64 <= ext <= 64 ) и poly - массив вершин многоугольника.

Функция maxEllipseInConvexPolygonA находит эллипс максимальной площади вписанный в выпуклый многоугольник:
Def<Ellipse2d> maxEllipseInConvexPolygonA ( CArrRef<Vector2d> poly );
Краткое описание этого алгоритма:
1. Если к-во вершин многоугольника меньше трёх, то выходим из программы.
2. По каждого ребра многоугольника строим прямую.
3. Из полученных прямых выбираем минимальное к-во таких, чтобы они образовали ограниченную фигуру.
4. Для этих прямых находим максимальный эллипс. Сами прямые, по которым строится эллипс, назовём опорными.
5. Начало цикла.
6. Находим прямую за пределы которой выходит текущий эллипс. Если таких прямых нет, то конец алгоритма.
7. Включаем эту прямую в набор опорных. Для этого перебором этих прямых строим новый эллипс, который не выходит за пределы данных опорных прямых. К-во новых опорных прямых будет от трёх до пяти ( к-во степеней свободы для эллипса ).
8. Идём в начало цикла.

Функция maxEllipseInPolygonA находит эллипс максимальной площади вписанный в невыпуклый многоугольник:
Def<Ellipse2d> maxEllipseInPolygonA ( CArrRef<Vector2d> poly );

В приложении DEMO показано, как применять эти функции.

Описание шаблона классов CArrRef находится здесь.
Описание шаблона классов Def находится здесь.
Описание класса Vector2d находится здесь.
Описание класса Ellipse2d находится здесь.
Исходники алгоритма находятся в файле opti2d.cpp.

Наверх