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

Обход вершин у всех многоугольников должен быть против часовой стрелки.
Функция maxPolygonInConvexPolygon находит максимальный многоугольник ( inner ) вписанный в выпуклый многоугольник ( outer ):

Def<Conform2d> maxPolygonInConvexPolygon ( CArrRef<Vector2d> inner, CArrRef<Vector2d> outer );
Многоугольники задаются массивами вершин, а ответ получатся в виде ортогонального преобразования, которое надо применить к вершинам внутреннего многоугольника ( inner ), чтобы получить оптимальное положение.

Функция maxConvexPolygonInPolygon находит такое преобразование, когда первый многоугольник ( inner ) выпуклый, а второй многоугольник ( outer ) может быть невыпуклым:

Def<Conform2d> maxConvexPolygonInPolygon ( CArrRef<Vector2d> inner, CArrRef<Vector2d> outer );

Функция maxConvexPolygonInPolygonNR находит такое преобразование, но без вращения:

Def<Conform2d> maxConvexPolygonInPolygonNR ( CArrRef<Vector2d> inner, CArrRef<Vector2d> outer );

Вписание максимального по площади прямоугольника в выпуклый многоугольник poly:

Def<Rectangle2d> maxRectangleInConvexPolygonA ( CArrRef<Vector2d> poly );
Вписание максимального по площади прямоугольника в невыпуклый многоугольник poly:
Def<Rectangle2d> maxRectangleInPolygonA ( CArrRef<Vector2d> poly );
Вписание максимального ромба в выпуклый многоугольник ( A - максимум площади, P - максимум периметра ):
Def<Rhomb2d> maxRhombInConvexPolygonA ( CArrRef<Vector2d> poly );
Def<Rhomb2d> maxRhombInConvexPolygonP ( CArrRef<Vector2d> poly );
Вписание максимального ромба в невыпуклый многоугольник:
Def<Rhomb2d> maxRhombInPolygonA ( CArrRef<Vector2d> poly );
Def<Rhomb2d> maxRhombInPolygonP ( CArrRef<Vector2d> poly );

Вписание максимального по площади треугольника в выпуклый многоугольник poly:

bool maxTriangleInConvexPolygonA ( FixArrRef<Vector2d, 3> & triangle, CArrRef<Vector2d> poly );
Фиксированный массив из 3-х элементов triangle в случае успешного завершения будет содержать координаты вершин вписанного треугольника. Этот алгоритм перебирает все тройки вершин многоугольника и выбирает из них лучшую.

Вписание максимального по площади параллелограмма в выпуклый многоугольник poly:

bool maxParallelogramInConvexPolygonA ( FixArrRef<Vector2d, 4> & para, CArrRef<Vector2d> poly );
Фиксированный массив из 4-х элементов para в случае успешного завершения будет содержать координаты вершин вписанного параллелограмма.

Вписание максимального по площади четырёхугольника в выпуклый многоугольник poly:

bool maxQuadInConvexPolygonA ( FixArrRef<Vector2d, 4> & quad, CArrRef<Vector2d> poly );
Фиксированный массив из 4-х элементов quad в случае успешного завершения будет содержать координаты вершин вписанного четырёхугольника. Этот алгоритм перебирает все четвёрки вершин многоугольника и выбирает из них лучшую.

Вписание максимального по площади N-угольника inner в выпуклый многоугольник outer:

bool maxNgonInConvexPolygonA ( ArrRef<Vector2d> & inner, CArrRef<Vector2d> outer );
Массив из N элементов inner в случае успешного завершения будет содержать координаты вершин вписанного N-угольника. Этот алгоритм не всегда даёт оптимальное решение.

В приложении DEMO можно посмотреть примеры использования этих функций.

Описание класса Vector2d смотрите в разделе Вектора на плоскости.
Описание класса Conform2d смотрите в разделе Преобразования на плоскости.
Описание шаблонов FixArrRef и CArrRef смотрите в разделе Массивы.
Описание шаблона классов Def смотрите в разделе Шаблон Def.
Описание классов Rhomb2d и Rectangle2d находится здесь.
Исходники алгоритмов находятся в файле opti2d_4.cpp.

Наверх