Минимальный охватывающий многоугольник

Вначале рассмотрим фигуры охватывающие выпуклые многоугольники с обходом вершин против часовой стрелки.

• Функция minTriangleAroundConvexPolygonA находит минимальный по площади треугольник охватывающий данный выпуклый многоугольник inner:

Def<Triangle2d> minTriangleAroundConvexPolygonA ( CArrRef<Vector2d> inner );
Эта функция является реализацией алгоритма описанного в статье "An Optimal Algorithm for Finding Minimal Enclosing Triangles" ( O'Rourke и др. ).

• Функции minRectangleAroundConvexPolygonA и minRectangleAroundConvexPolygonP находят минимальный прямоугольник по площади и по периметру соответственно:
Def<Rectangle2d> minRectangleAroundConvexPolygonA ( CArrRef<Vector2d> inner );
Def<Rectangle2d> minRectangleAroundConvexPolygonP ( CArrRef<Vector2d> inner );
• Функция minParallelogramAroundConvexPolygonA находит минимальный по площади параллелограмм охватывающий заданный выпуклый многоугольник:
Def<Parallelogram2d> minParallelogramAroundConvexPolygonA ( CArrRef<Vector2d> inner );
Эта функция сделана на основе статьи А. Д. Вайнштейна "Построение минимального объемлющего параллелограмма".

• Функция minTrapezoidAroundConvexPolygonA находит минимальную по площади трапецию охватывающую заданный выпуклый многоугольник при условии, что одна из её параллельных сторон лежит на стороне внутреннего многоугольника:
bool miTrapezoidAroundConvexPolygonA ( FixArrRef<Vector2d, 4> & outer, CArrRef<Vector2d> inner );
У всех предыдущих функций время работы зависит линейно от к-во вершин данного многоугольника.

• Функция minNgonAroundConvexPolygonA находит минимальный по площади N-угольник охватывающий заданный выпуклый многоугольник:
bool minNgonAroundConvexPolygonA ( ArrRef<Vector2d> outer, CArrRef<Vector2d> inner );
Размер массива outer определяет к-во вершин N-угольника. Если это к-во больше к-ва вершин многоугольника inner, то функция возвращает значение false и не заполняет массив outer.

• Функция minEquianglarPolygonAroundConvexPolygonA находит минимальный по площади равноугольный многоугольник охватывающий заданный выпуклый многоугольник:
bool minEquianglarPolygonAroundConvexPolygonA ( ArrRef<Vector2d> outer, CArrRef<Vector2d> inner );
В результате в равноугольнике outer некоторые вершины могут совпадать ( рёбра иметь нулевую длину ).

• Теперь рассмотрим поиск минимальных фигур охватывающих произвольные простые многоугольники и наборы точек. В этом случае вначале строится выпуклая оболочка исходных многоугольников или точек, а затем вызывается соответствующая функция для выпуклых многоугольников:
Def<Triangle2d>  minTriangleAroundPolygonA  ( CArrRef<Vector2d> inner );
Def<Triangle2d>  minTriangleAroundPointsA   ( CArrRef<Vector2d> inner );
Def<Rectangle2d> minRectangleAroundPolygonA ( CArrRef<Vector2d> inner );
Def<Rectangle2d> minRectangleAroundPointsA  ( CArrRef<Vector2d> inner );
Def<Rectangle2d> minRectangleAroundPolygonP ( CArrRef<Vector2d> inner );
Def<Rectangle2d> minRectangleAroundPointsP  ( CArrRef<Vector2d> inner );
Def<Parallelogram2d> minParallelogramAroundPolygonA ( CArrRef<Vector2d> inner );
Def<Parallelogram2d> minParallelogramAroundPointsA  ( CArrRef<Vector2d> inner );
bool minTrapezoidAroundPolygonA  ( FixArrRef<Vector2d, 4> & outer, CArrRef<Vector2d> inner );
bool minTrapezoidAroundPointsA   ( FixArrRef<Vector2d, 4> & outer, CArrRef<Vector2d> inner );
bool minNgonAroundPolygonA       ( ArrRef<Vector2d> outer, CArrRef<Vector2d> inner );
bool minNgonAroundPointsA        ( ArrRef<Vector2d> outer, CArrRef<Vector2d> inner );
bool minEquianglarPolygonAroundPolygonA ( ArrRef<Vector2d> outer, CArrRef<Vector2d> inner );
bool minEquianglarPolygonAroundPointsA  ( ArrRef<Vector2d> outer, CArrRef<Vector2d> inner );
• Также имеются функции поиска минимального охватывающие ромба вокруг набора точек ( A - минимум площади, Р - минимум периметра ):
Def<Rhombus2d> minRhombusAroundPointsA ( CArrRef<Vector2d> inner );
Def<Rhombus2d> minRhombusAroundPointsP ( CArrRef<Vector2d> inner );

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

Описание шаблонов классов ArrRef, FixArrRef и CArrRef находится здесь.
Описание шаблона классов Def находится здесь.
Описание класса Vector2d находится здесь.
Описание классов Triangle2d, Rhombus2d, Rectangle2d и Parallelogram2d находится здесь.
Исходники алгоритмов находятся в файле opti2d.cpp.

Наверх