Диаметры наборов точек и многоугольников

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

typedef unsigned int nat;

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

Можно искать минимальный диаметр множества точек вдоль заданного сектора направлений. Сектор задаётся средним направлением dir и половинным углом в градусах angle. Также в градусах указывается точность eps. Ответ получаем в виде возвращаемого диаметра, минимального направления res и пары индексов исходных точек imin и imax:

double minDiameterPnt ( CArrRef<Vector2d> point, const Vector2d & dir, double angle,
                        double eps, Vector2d & res, nat & imin, nat & imax );
inline
double minDiameterPnt ( CArrRef<Vector2d> point, const Vector2d & dir, double angle,
                        double eps, Vector2d & res )
{
    nat imin, imax;
    return minDiameterPnt ( point, dir, angle, eps, res, imin, imax );
}
inline
double minDiameterPnt ( CArrRef<Vector2d> point, const Vector2d & dir, double angle,
                        double eps )
{
    Vector2d res;
    nat imin, imax;
    return minDiameterPnt ( point, dir, angle, eps, res, imin, imax );
}

Аналогично находим максимальный диаметр:

double maxDiameterPnt ( CArrRef<Vector2d> point, const Vector2d & dir, double angle,
                        double eps, Vector2d & res, nat & imin, nat & imax );
inline
double maxDiameterPnt ( CArrRef<Vector2d> point, const Vector2d & dir, double angle,
                        double eps, Vector2d & res )
{
    nat imin, imax;
    return maxDiameterPnt ( point, dir, angle, eps, res, imin, imax );
}
inline
double maxDiameterPnt ( CArrRef<Vector2d> point, const Vector2d & dir, double angle,
                        double eps )
{
    Vector2d res;
    nat imin, imax;
    return maxDiameterPnt ( point, dir, angle, eps, res, imin, imax );
}

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

Следующие функции находят диаметры у многоугольников.
Функции maxConvexPolygonDiameter находят максимальный диаметр ( первая из них ещё и индексы наиболее удалённых вершин ) для выпуклого многоугольника:

double maxConvexPolygonDiameter ( CArrRef<Vector2d> vert, nat & ix1, nat & ix2 );
inline
double maxConvexPolygonDiameter ( CArrRef<Vector2d> vert )
{
    nat ix1, ix2;
    return maxConvexPolygonDiameter ( n, vert, ix1, ix2 );
}

Функции minConvexPolygonDiameter находят минимальный диаметр ( первые две из них ещё и направление вдоль которого этот дииаметр вычислялся ) для выпуклого многоугольника:

double minConvexPolygonDiameter ( CArrRef<Vector2d> vert, Vector2d & dir, nat & i1, nat & i2 );

inline
double minConvexPolygonDiameter ( CArrRef<Vector2d> vert, Vector2d & dir )
{
    nat i1, i2;
    return minConvexPolygonDiameter ( vert, dir, i1, i2 );
}

inline
double minConvexPolygonDiameter ( CArrRef<Vector2d> vert )
{
    nat i1, i2;
    Vector2d dir;
    return minConvexPolygonDiameter ( vert, dir, i1, i2 );
}

Входной параметр для всех этих функций - это ссылка на массив, где расположены вершины многоугольника. Как обычно обход вершин полагается против часовой стрелки. Время работы всех этих фукций зависит линейно от к-ва вершин

Известно, что для простого многоугольника можно построить выпуклую оболочку за время O(n) ( смотрите раздел Выпуклая оболочка на плоскости ). Отсюда следует, что диаметры простого многоугольника можно найти за время O(n).

Для трёхмерного случая неизвестны подобные по эффективности алгоритмы, поэтому там целесообразно применять простой перебор вершин.

Описание класса Vector2d находится здесь.
Описание шаблона классов CArrRef находится здесь.

Исходники алгоритма находятся в файле func2d.cpp.

Наверх