§ Графически-аналитически

На самом деле, тема очень простая. Необходимо рассчитать, где и каким образом пересекутся две прямые, с заданными векторами направления. Представим, что существует вектор AB и вектор CD. Необходимо найти точку пересечения M.

§ Задание линии параметрически

Задаем обе линии параметрическим методом.
Первая линия:

x = A.x + u(B.x - A.x)
y = A.y + u(B.y - A.y)

Вторая линия:

x = C.x + v(D.x - C.x)
y = C.y + v(D.y - C.y)

§ Решение уравнения

Потом приравниваем уравнения. Как можно заметить, существует некоторая общая точка (x,y), которая должна совпасть, когда у нас будет необходимый u, v. Приравниваем их:

A.x + u(B.x - A.x) = C.x + v(D.x - C.x)
A.y + u(B.y - A.y) = C.y + v(D.y - C.y)

Теперь переносим все неизвестные влево, а известные - вправо:

u(B.x - A.x) - v(D.x - C.x) = C.x - A.x
u(B.y - A.y) - v(D.y - C.y) = C.y - A.y

Заменим:

B.x-A.x = AB.x; D.x-C.x = CD.x; C.x-A.x = AC.x
B.y-A.y = AB.y; D.y-C.y = CD.y; C.y-A.y = AC.y

И вот что получилось:

u*AB.x - v*CD.x = AC.x
u*AB.y - v*CD.y = AC.y

§ Нахождение u, v, x, y

Как можно заметить, на самом деле это получилось обычное линейное уравнение, которое легко решается методом Крамера. Первым делом найдем определитель:

D = AB.y*CD.x - AB.x*CD.y

Если определитель равен 0, это означает только то, что линии параллельны и не имеют точек соприкосновения. Если же нет, то рассчитаем u. Для этого столбец справа, где AC, надо подставить в столбец слева, где AB и рассчитать определитель. После чего поделить на D.

| AC.x - CD.x | = AC.y*CD.x - AC.x*CD.y
| AC.y - CD.y |

Значит, что u будет равен вот этому выражению:

    AC.y*CD.x - AC.x*CD.y
u = ---------------------
    AB.y*CD.x - AB.x*CD.y

А также бывает полезно рассчитать v:

    AB.x*AC.y - AB.y*AC.x
v = ---------------------
    AB.y*CD.x - AB.x*CD.y

Зная u, v, легко рассчитать x, y:

x = A.x + u*AB.x | x = C.x + v*CD.x
y = A.y + u*AB.y | y = C.y + v*CD.y

Вот и всё. Точно так же получается и с v - разницы нет, они все равно пересекаются. Интересный факт - если v лежит в диапазоне от 0 до 1, то точка лежит на отрезке CD, точно та же как и u=[0,1] лежит на отрезке AB.

§ Реализация на QB

1SCREEN 13
2
3Ax = 100: Ay = 50: Bx = 250: By = 100
4Cx = 150: Cy = 25: Dx = 200: Dy = 150
5
6' ----------
7LINE (Ax, Ay)-(Bx, By), 2
8LINE (Cx, Cy)-(Dx, Dy), 10
9
10' ----------
11ABx = Bx - Ax: ABy = By - Ay
12ACx = Cx - Ax: ACy = Cy - Ay
13CDx = Dx - Cx: CDy = Dy - Cy
14
15D = (ABy * CDx - ABx * CDy)
16u = (ACy * CDx - ACx * CDy) / D
17v = (ABy * ACx - ABx * ACy) / D
18
19x = Ax + u * ABx
20y = Ay + u * ABy
21
22' ------------------
23CIRCLE (x, y), 1, 15