|
Def<Triangle2d> minTriangleAroundConvexPolygonA ( CCArrRef<Vector2d> & inner );Эта функция является реализацией алгоритма описанного в статье "An Optimal Algorithm for Finding Minimal Enclosing Triangles" ( O'Rourke и др. ). • Минимальный прямоугольник по площади и по периметру: Def<Rectangle2d> minRectangleAroundConvexPolygonA ( CCArrRef<Vector2d> & inner ); Def<Rectangle2d> minRectangleAroundConvexPolygonP ( CCArrRef<Vector2d> & inner );• Минимальный по площади параллелограмм: Def<Parallelogram2d> minParallelogramAroundConvexPolygonA ( CCArrRef<Vector2d> & inner );Эта функция сделана на основе статьи А. Д. Вайнштейна "Построение минимального объемлющего параллелограмма". • Минимальная по площади трапеция: bool miTrapezoidAroundConvexPolygonA ( FixArrRef<Vector2d, 4> & outer, CCArrRef<Vector2d> & inner );У всех предыдущих функций время работы зависит линейно от к-во вершин данного многоугольника. • Минимальный по площади N-угольник: bool minNgonAroundConvexPolygonA ( ArrRef<Vector2d> & outer, CCArrRef<Vector2d> & inner );Размер массива outer определяет к-во вершин N-угольника. Если это к-во больше к-ва вершин многоугольника inner, то функция возвращает значение false и не заполняет массив outer. • Минимальный по площади равноугольный многоугольник: bool minEquianglarPolygonAroundConvexPolygonA ( ArrRef<Vector2d> & outer, CCArrRef<Vector2d> & inner );В результате в равноугольнике outer некоторые вершины могут совпадать ( рёбра иметь нулевую длину ). • Теперь рассмотрим поиск минимальных фигур охватывающих произвольные простые многоугольники и наборы точек. В этом случае вначале строится выпуклая оболочка исходных многоугольников или точек, а затем вызывается соответствующая функция для выпуклых многоугольников: Def<Triangle2d> minTriangleAroundPolygonA ( CCArrRef<Vector2d> & inner ); Def<Triangle2d> minTriangleAroundPointsA ( CCArrRef<Vector2d> & inner ); Def<Rectangle2d> minRectangleAroundPolygonA ( CCArrRef<Vector2d> & inner ); Def<Rectangle2d> minRectangleAroundPointsA ( CCArrRef<Vector2d> & inner ); Def<Rectangle2d> minRectangleAroundPolygonP ( CCArrRef<Vector2d> & inner ); Def<Rectangle2d> minRectangleAroundPointsP ( CCArrRef<Vector2d> & inner ); Def<Parallelogram2d> minParallelogramAroundPolygonA ( CCArrRef<Vector2d> & inner ); Def<Parallelogram2d> minParallelogramAroundPointsA ( CCArrRef<Vector2d> & inner ); bool minTrapezoidAroundPolygonA ( FixArrRef<Vector2d, 4> & outer, CCArrRef<Vector2d> & inner ); bool minTrapezoidAroundPointsA ( FixArrRef<Vector2d, 4> & outer, CCArrRef<Vector2d> & inner ); bool minNgonAroundPolygonA ( ArrRef<Vector2d> & outer, CCArrRef<Vector2d> & inner ); bool minNgonAroundPointsA ( ArrRef<Vector2d> & outer, CCArrRef<Vector2d> & inner ); bool minEquianglarPolygonAroundPolygonA ( ArrRef<Vector2d> & outer, CCArrRef<Vector2d> & inner ); bool minEquianglarPolygonAroundPointsA ( ArrRef<Vector2d> & outer, CCArrRef<Vector2d> & inner );• Также имеются функции поиска минимального охватывающие ромба вокруг набора точек ( A - минимум площади, Р - минимум периметра ): Def<Rhombus2d> minRhombusAroundPointsA ( CCArrRef<Vector2d> & inner ); Def<Rhombus2d> minRhombusAroundPointsP ( CCArrRef<Vector2d> & inner ); В приложении DEMO можно посмотреть примеры использования этих функций.
Описание шаблонов классов ArrRef, FixArrRef и CArrRef находится здесь.
|