Кратко — конструкция, критерий и разбор устойчивости + сравнение алгоритмов.
Шаги построения (дано $A(x_a,y_a),B(x_b,y_b),C(x_c,y_c)$, точки неколлинеарны):
1) Вычислите квадраты сторон
$$a^2=(x_b-x_c{)}^2+(y_b-y_c{)}^2,b^2=(x_c-x_a{)}^2+(y_c-y_a{)}^2,c^2=(x_a-x_b{)}^2+(y_a-y_b{)}^2.$$
2) Найдите наибольшую сторону, пусть это сторона с длиной $c$. Если
$$c^2\ge a^2+b^2,$$ то треугольник прямой или тупой относительно этой стороны — минимальная окружность имеет диаметр эту сторону. Центр и радиус:
$$O=\frac{A+B}{2}=(\frac{x_a+x_b}{2},\frac{y_a+y_b}{2}),R=\frac{\sqrt{c^2}}{2}.$$
(Если наибольшая сторона — не $AB$, подставьте соответствующие вершины.)
3) Иначе (треугольник острый) минимальная окружность — описанная окружность. Найдите её центр как пересечение серединных перпендикуляров; в явной форме:
$$D=2(x_a(y_b-y_c)+x_b(y_c-y_a)+x_c(y_a-y_b)),$$ $$O_x=\frac{(x_a^2+y_a^2)(y_b-y_c)+(x_b^2+y_b^2)(y_c-y_a)+(x_c^2+y_c^2)(y_a-y_b)}{D},$$ $$O_y=\frac{(x_a^2+y_a^2)(x_c-x_b)+(x_b^2+y_b^2)(x_a-x_c)+(x_c^2+y_c^2)(x_b-x_a)}{D},$$ радиус $R=|O-A|$.
Устойчивость при малых возмущениях:
- Решение меняется непрерывно, но чувствительность может быть большой. Для кругов, полученных как описанная окружность, радиус можно записать
$$R=\frac{abc}{4\Delta },$$ где площадь Δ=12∣(B−A)×(C−A)∣\Delta=\tfrac12\big|(B-A)\times(C-A)\big|Δ=21 (B−A)×(C−A) . При малой площади (точки почти коллинеарны) $R$ становится большим — малые возмущения координат дают большой относительный сдвиг центра и радиуса.
- Переход между случаями (диаметр = longest side) и описанной окружностью происходит при границе $c^2=a^2+b^2$ (прямой угол). Если треугольник близок к этой границе, малое возмущение может изменить тип решения, но значения радиусов слева и справа близки (на границе они совпадают).
- Практически: в численных реализациях используйте порог $\epsilon$ для проверки коллинеарности/прямого угла (например $\Delta <\epsilon$ или $|c^2-(a^2+b^2)|<\epsilon$), и переключайтесь на надёжную схему (например выбирать диаметр при малой площади) чтобы избежать деления на малые числа.
Сравнение алгоритмов и их сложность:
- Для именно трёх точек оптимально использовать вышеописённую явную конструкцию — вычисления требуют константное число операций, сложность $O(1)$. Это и точнее, и быстрее любых общих алгоритмов.
- Для общего множества из $n$ точек классический оптимальный ожидаемый алгоритм — случайный алгоритм Welzl с ожидаемой сложностью $O(n)$. Существуют детерминированные алгоритмы со сложностью $O(n)$, но реализация сложнее.
- Численная устойчивость: у явной формулы для описанной окружности при почти коллинеарных точках плохая обусловленность (деление на малое $D$), поэтому лучше заранее обрабатывать пары крайних точек и использовать оценку площади/порог.
Резюме: для трёх неколлинеарных точек — проверить условие $c^2\ge a^2+b^2$; если да, центр — середина наибольшей стороны, иначе вычислить описанный центр по формулам выше. Для реализации учитывать пороги и использовать более устойчивые численные приёмы при малой площади.