Выше по иерархии
Другие алгоритмы.

Математика:
Вычислительная геометрия:
Пересекаются ?... А если да, то где ?

Прямая и окружность.

© Кантор И.

Любые уравнения прямой и окружности могут быть приведены к следующему каноническому виду:

(1) Прямая (X-X1)(Y2-Y1)=(Y-Y1)(X2-X1)
(2) и окружность (X-X0)2+(Y-Y0)2=R2

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

Делай 1. Проверяем случай X2 = X1 - тогда прямая вертикальна: (1) имеет вид X = X1.
Подставляем X1 в уравнение (2): (Y-Y0)2=R2 - (X1-X0)2. Решения этого уравнения - координаты по y точки пересечения.

Делай 2. Если X2 =/= X1, то, разделив на это обе части (1), имеем: Y=KX + B - новый вид уравнения прямой. K и B вычислите сами - они выражаются через X1,2 и Y1,2. Подставляете этот Y в (2) - имеете квадратное уравнение относительно X. Находите дискриминант и по его знаку выясняете количество решений-точек пересечения. Если нужно - дорешаете это уравнение и получите сами точки.

IF ( X2 = X1 )
  {
    IF ( R2 > (X1-X0)2 ) 
	       2 пересечения в точках ( X1, Y0 +- SQRT( R2 - (X1-X0)2 ) ).
    IF ( R2 == (X1-X0)2 ) 
	       1 пересечение в точке ( X1, Y0 )
    IF ( R2 < (X1-X0)2 ) 
	       пересечений нет.
  } else
  
{
K = 1 / (X2-X1)(Y2-Y1); 
B = Y1 - X1/(X2-X1)(Y2-Y1);   
 X-координата точки пересечения - решение уравнения 
     (KX+B-Y0)2 = R2-(X-X0)2.
 Y-координата: KX+B.
 
    IF ( R2 > (X1-X0)2 ) 2 пересечения.
    IF ( R2 == (X1-X0)2 ) 1 пересечение.
    IF ( R2 < (X1-X0)2 ) пересечений нет.
}



Вверх по странице, к оглавлению и навигации.