|
Вначале рассмотрим фигуры охватывающие выпуклые многоугольники с обходом вершин против часовой стрелки.
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 находится здесь.
|