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

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

bool minTriangleAroundConvexPolygonA ( FixArrRef<Vector2d, 3> & outer, 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 находит минимальный по площади параллелограмм охватывающий заданный выпуклый многоугольник:
bool minParallelogramAroundConvexPolygonA ( FixArrRef<Vector2d, 4> & outer, 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 некоторые вершины могут совпадать ( рёбра иметь нулевую длину ).

Теперь рассмотрим поиск минимальных фигур охватывающих произвольные простые многоугольники и наборы точек. В этом случае вначале строится выпуклая оболочка исходных многоугольников или точек, а затем вызывается соответствующая функция для выпуклых многоугольников:
bool minTriangleAroundPolygonA ( FixArrRef<Vector2d, 3> & outer, CArrRef<Vector2d> inner );
bool minTriangleAroundPointsA  ( FixArrRef<Vector2d, 3> & outer, CArrRef<Vector2d> inner );
Def<Rectangle2d> minRectangleAroundPolygonA ( CArrRef<Vector2d> inner );
Def<Rectangle2d> minRectangleAroundPolygonP ( CArrRef<Vector2d> inner );
Def<Rectangle2d> minRectangleAroundPointsA  ( CArrRef<Vector2d> inner );
Def<Rectangle2d> minRectangleAroundPointsP  ( CArrRef<Vector2d> inner );
bool minParallelogramAroundPolygonA ( FixArrRef<Vector2d, 4> & outer, CArrRef<Vector2d> inner );
bool minParallelogramAroundPointsA  ( FixArrRef<Vector2d, 4> & outer, 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<Rhomb2d> minRhombAroundPointsA ( CArrRef<Vector2d> inner );
Def<Rhomb2d> minRhombAroundPointsP ( CArrRef<Vector2d> inner );

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

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

Наверх