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

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

• Максимальный многоугольник: 

Def<Conform2d> maxPolygonInConvexPolygon ( CCArrRef<Vector2d> & inner, CCArrRef<Vector2d> & outer );
Ответ получатся в виде ортогонального преобразования, которое надо применить к вершинам внутреннего многоугольника ( inner ), чтобы получить оптимальное положение.
Следующая функция делает то же самое, но без вращения: 
Def<Conform2d> maxPolygonInConvexPolygonNR ( CCArrRef<Vector2d> & inner, CCArrRef<Vector2d> & outer );
• Максимальный по площади прямоугольник: 
Def<Rectangle2d> maxRectangleInConvexPolygonA ( CCArrRef<Vector2d> & poly );
Следующая функция делает то же самое, но без вращения: 
Def<Rectangle2d> maxRectangleInConvexPolygonANR ( CCArrRef<Vector2d> & poly );
• Максимальный ромб ( A - максимум площади, P - максимум периметра ): 
Def<Rhombus2d> maxRhombusInConvexPolygonA ( CCArrRef<Vector2d> & poly );
Def<Rhombus2d> maxRhombusInConvexPolygonP ( CCArrRef<Vector2d> & poly );
Без вращения: 
Def<Rhombus2d> maxRhombusInConvexPolygonANR ( CCArrRef<Vector2d> & outer );
• Максимальный параллелограмм ( A - максимум площади, P - максимум периметра ): 
Def<Parallelogram2d> maxParallelogramInConvexPolygonA ( CCArrRef<Vector2d> & poly );
Def<Parallelogram2d> maxParallelogramInConvexPolygonP ( CCArrRef<Vector2d> & poly );

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

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

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

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

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

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

Наверх