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

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

typedef unsigned int nat;

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

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

Следующие функции находят диаметры у выпуклых многоугольников.

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

double maxConvexPolygonDiameter ( CCArrRef<Vector2d> & vert, nat & ix1, nat & ix2 );

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

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

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

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

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

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

double minConvexPolygonDiameter ( CCArrRef<Vector2d> & vert, Vector2d dir, double angle, Vector2d & res );

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

double maxConvexPolygonDiameter ( CCArrRef<Vector2d> & vert, Vector2d dir, double angle, Vector2d & res );

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

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

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

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

Наверх