Минимальная охватывающая фигура в пространстве

В этом разделе представлены функции, которые находят минимальную фигуру охватывающую данное множество точек в трёхмерном пространстве.

• Сфера и конечное множество точек.

Def<Sphere3d> minSphereAroundPoints ( CArrRef<Vector3d> data );
Описание этого алгоритма:
1. Если к-во входных точек равно 0, то возвращаем неопределённую сферу.
2. Если к-во входных точек равно 1, то возвращаем сферу с центром в этой точке и нулевым радиусом.
3. Если к-во входных точек равно 2, то возвращаем сферу с центром в середине между этими точками и соответсвующим радиусом.
4. Находим самую удалённую точку от первой. Если это расстояние будет равно 0, то возвращаем сферу с центром в первой точке и нулевым радиусом. Иначе считаем эти точки опорными и строим по ним сферу, как в пункте 3.
5. Начало цикла.
6. Находим самую удаленную точку от центра текущей сферы. Если это расстояние не больше, чем радиус текущей сферы или индекс самой удалённой точки равен одному из индексов опорных точек, то выходим из цикла. Иначе будем включать эту точку в число опорных, а пока назовём её новой.
7. Найдём среди старых опорных точек и новой точки путём перебора новый набор опорных точек ( их будет не более четырёх ) и минимальную сферу вокруг них.
8. Если радиус текущей сферы не вырос за время цикла, то конец алгоритма, иначе идём на начало цикла.

• Сфера и конечное множество сфер.

Def<Sphere3d> minSphereAroundSpheres ( CArrRef<Sphere3d> data );
Описание этого алгоритма аналогично описанию алгоритма для точек.

• Сфера пересекающая все данные плоскости или прямые:

Def<Sphere3d> minSphere ( CArrRef<Plane3d> data );
Def<Sphere3d> minSphere ( CArrRef<Line3d> data );
Временная сложность этих алгоритмов практически линейная.

• Эллипсоид и конечное множество точек. Минимум объёма.

Def<Ellipsoid3d> minEllipsoidV ( CArrRef<Vector3d> point );

• Цилиндр и конечное множество точек. Минимум радиуса.

Def<Cylinder3d> minCylinderR ( CArrRef<Vector3d> point );

• Правильный тетраэдр охватывающий данные точки без вращения.

bool minRegularTetrahedronAroundPointsNR ( СCArrRef<Vector3d> & data, 
                                           const Ortho3d & ortho, Polyhedron & poly );

• Правильный тетраэдр охватывающий данные точки.

bool minRegularTetrahedronAroundPoints ( СCArrRef<Vector3d> & data, Polyhedron & poly );

• Прямоугольный параллелепипед охватывающий данные точки без вращения.

Def<Cuboid3d> minCuboidAroundPointsNR ( CArrRef<Vector3d> data );

• Прямоугольный параллелепипед и внутренний многогранник. Минимум по объёму ( V ) и по площади поверхности ( A ):

Def<Cuboid3d> minCuboidAroundConvexPolyhedronV ( const Polyhedron & inner );

Def<Cuboid3d> minCuboidAroundConvexPolyhedronA ( const Polyhedron & inner );
Временная сложность этих алгоритмов опытным путём определена, как O ( n2 log ( n ) ), где n - это к-во рёбер ( вершин или граней ) многогранника ( inner ).
Если же нужно найти минимальный прямоугольный параллелепипед охватывающий данный набор точек, то тогда надо вначале получить выпуклую оболочку этих точек, а затем для выпуклой оболочки найти минимальный охватывающий параллелепипед.

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

Описание шаблона классов CArrRef находится здесь.
Описание шаблона классов Def находится здесь.
Описание класса Vector3d находится здесь.
Описание классов Sphere3d, Ellipsoid3d, Cylinder3d и Cuboid3d находится здесь.
Описание класса Polyhedron находится здесь
Исходники находятся в файле opti3d.cpp.

Наверх