Расстояния в пространстве

Квадрат расстояния от точки до треугольника:

double getDistance2 ( const Triangle3d & t, const Vector3d & p );

Расстояние от точки до границы эллипсоида:

bool getDistanceEld ( double a, double b, double c, const Vector3d & p, double & d, Vector3d & r );
Здесь a, b и c - это параметры эллипсоида заданного в виде ( x / a )2 + ( y / b )2 + ( z / c )2 = 1,
p - заданная точка,
d - вычисленное расстояние ( отрицательное, если точка находится внутри эллипсоида ),
r - ближайшая точка на границе эллипсоида.
Функция возвращает false, если среди чисел a, b, c есть неположительные.

Пусть дан набор точек ( point ) и нужно найти его диаметр вдоль заданного направления ( dir ). Функция diameterPnt находит его, а также возвращает индексы самой ближней ( imin ) и самой дальней ( imax ) точкек:

typedef unsigned int nat

double diameterPnt ( CArrRef<Vector3d> point, const Vector3d & dir, nat & imin, nat & imax );
inline
double diameterPnt ( CArrRef<Vector3d> point, const Vector3d & dir )
{
    nat imin, imax;
    return diameterPnt ( point, dir, imin, imax );
}

Известно, что минимальный диаметр выпуклого многогранника лежит между двумя параллельными плоскостями, причём возможны два варианта: 1) одна из плоскостей определяется гранью многогранника, а вторая проходит через самую удалённую к ней вершину, 2) плоскости определяются двумя рёбрами многогранника. Предлагается такой алгоритм: вначале перебираются все грани и для них находятся самые удалённые вершины, затем перебираются все пары рёбер и среди них выбираются такие, которые задают параллельные плоскости не пересекающие многогранник. Среди полученных диаметров выбирается минимальный. Временная сложность такого алгоритма равна O ( n2 ), где n - это рёбра, вершины или грани. Следующая функция находит минимальный диаметр по этому алгоритму:

bool minConvexPolyhedronDiameter ( const Polyhedron & poly, Vector3d & dir, double & d1, double & d2 );
inline
double minConvexPolyhedronDiameter ( const Polyhedron & poly )
{
    Vector3d dir;
    double d1, d2;
    if ( ! minConvexPolyhedronDiameter ( poly, dir, d1, d2 ) ) return 0;
    return d2 - d1;
}

Описание класса Vector3d находится здесь.
Описание класса Triangle3d находится здесь,
Описание класса Polyhedron находится здесь,

Исходники алгоритмов находятся в func3d.cpp

Наверх