Дано конечное множество точек в трёхмерном пространстве. Нужно построить сферу минимального радиуса такую, чтобы все данные точки лежали внутри сферы. Следующая функция находит такую сферу: 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 ); Входным параметром для функции minEllipsoidV является ссылка на массив точек point. Возвращаемое значение - это объект содержащий параметры эллипсоида. Следующая функция находит цилиндр минимального радиуса охватывающий заданные точки: Def<Cylinder3d> minCylinderR ( CArrRef<Vector3d> point ); Следующая функция находит минимальный правильный тетраэдр охватывающий данные точки без вращения: bool minRegularTetrahedronAroundPointsNR ( CArrRef<Vector3d> data, Polyhedron & poly );Следующая функция находит минимальный параллелепипед охватывающий данные точки без вращения: Def<Cuboid3d> minCuboidAroundPointsNR ( CArrRef<Vector3d> data );Теперь рассмотрим получение минимального прямоугольного параллелепипеда ( outer ) охватывающего данный выпуклый многогранник ( inner ). Минимум будем искать по объёму ( V ) и по площади поверхности ( A ): Def<Cuboid3d> minCuboidAroundConvexPolyhedronV ( const Polyhedron & inner ); Def<Cuboid3d> minCuboidAroundConvexPolyhedronA ( const Polyhedron & inner );Временная сложность алгоритмов поиска минимального прямоугольного параллелепипеда опытным путём определена, как O ( n2 log ( n ) ), где n - это к-во рёбер ( вершин или граней ) многогранника ( inner ). Если же нужно найти минимальный прямоугольный параллелепипед охватывающий данный набор точек, то тогда надо вначале получить выпуклую оболочку этих точек, а затем для выпуклой оболочки найти минимальный охватывающий параллелепипед. Примеры использования этих функций можно посмотреть в приложении DEMO. Описание шаблона классов CArrRef находится здесь.
|