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

Обход вершин у всех многоугольников должен быть против часовой стрелки.
• Функция 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:

Def<Triangle2d> maxTriangleInConvexPolygonA ( CArrRef<Vector2d> poly );
Этот алгоритм перебирает все тройки вершин многоугольника и выбирает из них лучшую.

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

Def<Parallelogram2d> maxParallelogramInConvexPolygonA ( CArrRef<Vector2d> poly );

• Вписание максимального по площади четырёхугольника в выпуклый многоугольник 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.
Описание классов Triangle2d, Rhomb2d, Rectangle2d и Parallelogram2d находится здесь.
Исходники алгоритмов находятся в файле opti2d_4.cpp.

Наверх