Минимальная охватывающая окружность

Дано конечное множество точек на плоскости. Нужно найти окружность минимального радиуса такую, чтобы данные точки были внутри неё. Следующая функция находит такую окружность:

Def<Circle2d> minCircleAroundPoints ( CArrRef<Vector2d> data, DynArrRef<nat> * index = 0 );

Здесь data - это массив входных точек, а index - указатель на массив, в который будут записаны индексы точек по которым была построена окружность ( в том случае, если указатель не равен 0 ).

Описание алгоритма:
1. Если к-во входных точек равно 0, то возвращаем неопределённую окружность.
2. Если к-во входных точек равно 1, то возвращаем окружность с центром в этой точке и нулевым радиусом.
3. Если к-во входных точек равно 2, то возвращаем окружность с центром в середине между этими точками и соответсвующим радиусом.
4. Находим самую удалённую точку от первой. Если это расстояние будет равно 0, то возвращаем окружность с центром в первой точке и нулевым радиусом. Иначе считаем эти точки опорными и строим по ним окружность, как в пункте 3.
5. Начало цикла.
6. Находим самую удаленную точку от центра текущей окружности. Если это расстояние не больше, чем радиус текущей окружности или индекс самой удалённой точки равен одному из индексов опорных точек, то выходим из цикла. Иначе будем включать эту точку в число опорных, а пока назовём её новой.
7. Найдём среди опорных точек самую удаленную от новой точки и построим текущую окружность по двум точкам ( новой и найденной ).
8. Если к-во опорных точек текущей окружности было равным 3, то переходим к пункту 9. Иначе проверим выходит ли неиспользованная опорная точка за пределы текущей окружности. Если не выходит, то заменяем её на новую точку ( к-во опорных точек останется равным 2 ). Иначе добавляем новую точку в опорные и строим окружность по трём точкам. Переходим к пункту 10.
9. Находим из двух неиспользованных точек самую удаленную от центра текущей окружности. Если эта точка лежит вне круга, то она будет третьей опорной и тогда строим окружность по трём новым опорным точкам. Иначе опорных точек останется две.
10. Если радиус окружности не вырос за время цикла, то конец алгоритма, иначе идём на начало цикла.

Дано конечное множество окружностей на плоскости. Нужно найти окружность минимального радиуса такую, чтобы все данные окружности были внутри неё. Следующая функция находит такую окружность:

Def<Circle2d> minCircleAroundCircles ( CArrRef<Circle2d> data );

Описание этого алгоритма аналогично описанию алгоритма для точек.

Дано конечное множество прямых на плоскости. Нужно найти окружность минимального радиуса такую, чтобы она пересекала все данные прямые. Следующая функция находит такую окружность:

Def<Circle2d> minCircle ( CArrRef<Line2d> data );

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

В приложении DEMO можно посмотреть работу этих алгоритмов.
Исходники алгоритма находятся в файле opti2d.cpp.

Наверх