Здравствуйте, LameFox, Вы писали:
LF>Существует множество точек на плоскости, заданных координатами (X,Y).
LF>Подскажите плиз способ нахождения координат центра (CX,CY) и минимального радиуса (R) окружности,
LF>которая включала бы в себя все эти точки.
Все сильно зависит от того, какая сложность вас устроит.
1. Дебильный вариант: перебираем все возможные пары точек как кандидатов
в диаметры, кроме того пробуем около всякой тройки точек описать окружность.
Время работы O(N^4).
Никогда так не делайте!
2. Стандартный вариант: ну диаметры можно по-прежнему перебирать, это даст
O(N^3), а перебор троек можно оптимизировать. Именно фиксируем пару точек
A и B. Возможны два случая расположения центра -- в верхней относительно AB
полуплоскости и в нижней. Для каждого, случая рассмотрев оставшиеся точки,
несложно вычислить требования к радиусу окружности: оценки снизу и сверху.
Наконец еще за один проход можно выяснить, есть ли подходящая третья точка.
Получится сложность O(N^3), кроме того тут еще море возможностей для
оптимизаций и вариаций.
3. Если точек очень много.. ну тогда нам поможет диаграма Вороного.
Ссылка из Handbook of Theoretical Computer Science, vol A., p. 363,
sec. 6.3.3 "Smallest enclosing circle".
Smahos and Hoey [200] exhibited the first O(n log n) solution by
ovservising that the smallest enclosing circle is either determined by the diameter
of the set of centered at a vertex of the furthest-point Voronoi diagram.
Если интересно, что такое [200], то это:
Shamos, M.I. and D. Hoey, Closest-point problems, in: Proc. 16th IEEE Ann.
Symp. Found. Comput. Sci. (1975), 151-162