Алгоритм определения прохождения прямой через окружность
У меня есть прямая с координатами X1, Y1, X2, Y2. Имеется окружность с координатами X3, Y3 и радиусом R.
Как определить проходит ли эта прямая через окружность? Разрешается использовать только математические формулы, без "функций" различных языков программирования.
Ответы (1 шт):
Зададим прямую параметрически: точка (xt, yt) лежит на прямой при любых t. И наоборот любая точка прямой соответствует какому-то значению t:
xt = X1 + (X2 - X1)t
yt = Y1 + (Y2 - Y1)t
Уравнение окружности в обычном (не параметрическом виде). (x, y) лежит на окружности тогда и только тогда, когда:
(x - X3)2 + (y - Y3)2 = R2
Подставим параметрическое уравнение прямой в уравнение окружности:
(X1 + (X2 - X1)t - X3)2 + (Y1 + (Y2 - Y1)t - Y3)2 = R2
Раскроем скобки и решим уравнение относительно t:
((X2 - X1)t + (X1 - X3))2 + ((Y2 - Y1)t + (Y1 - Y3))2 = R2
(X2 - X1)2t2 + 2(X2 - X1)(X1 - X3)t + (X1 - X3)2 + (Y2 - Y1)2t2 + 2(Y2 - Y1)(Y1 - Y3)t + (Y1 - Y3)2 = R2
((X2 - X1)2 + (Y2 - Y1)2)t2 + 2((X2 - X1)(X1 - X3) + (Y2 - Y1)(Y1 - Y3))t + ((X1 - X3)2 + (Y1 - Y3)2 - R2) = 0
Обозначим:
A = (X2 - X1)2 + (Y2 - Y1)2
B = 2((X2 - X1)(X1 - X3) + (Y2 - Y1)(Y1 - Y3))
C = (X1 - X3)2 + (Y1 - Y3)2 - R2
В этих обозначениях уравнение примет вид:
At2 + Bt + C = 0
Это квадратное уравнение, с определителем D = B2 - 4AC.
- Если D < 0, пересечения нет;
- если D = 0, есть одно пересечение, прямая и окружность касаются;
- если D > 0, прямая и окружность пересекаются в двух точках.
Если вы захотите определить точки пересечения, вам придётся решить уравнение, найти значения параметра t. Чтобы по параметру восстановить точки пересечения, вернитесь к началу ответа.
P.S. Удивительное свойство этого решения ‐ чтобы проверить пересечение не нужно делить и извлекать корни. Всё делается сложением, вычитанием и умножением. А значит, если исходные данные целые, вы узнаете факт пересечения используя только целые числа, то есть точно.