Нахождение точки пересечения двух отрезков

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

где Р0 и Р1 – начальная и конечная точки отрезка;
u = P1-P0 – вектор, показывающий направление и длину отрезка;
s – координата точки на отрезке (или прямой, содержащей данный отрезок).
При  0 <= s <= 1 мы имеем множество точек, лежащих между точками Р0 и Р1, в противном случае (s < 0 или s > 1) – мы получим все точки, лежащие на прямой, содержащей данный отрезок, но за его границами («левее» и «правее»).
Рассмотрим теперь 2 отрезка, заданных параметрическими уравнениями:

Данные отрезки будут параллельны, если

где c – некоторое число.
Вспомним теперь понятие перпендикулярного скалярного произведения – модификации скалярного произведения, в котором первый вектор заменен его левой нормалью. Важным свойством данного произведения будет его равенство нулю в случае параллельности перемножаемых векторов (вытекает из свойств обычного скалярного произведения векторов), т.е.:

Это все была необходимая вводная информация. Перейдем теперь непосредственно к нахождению точки I пересечения отрезков P(s) и Q(t).

Иллюстрация к нахождению точки пересечения двух отрезков

Проведем вектор w, соединяющий начала отрезков P(s) и Q(t) (т.е. через точки P0 и Q0):

Условием пересечения отрезков P(s) и Q(t) будет перпендикулярность векторов P(s1)-Q0 и левой нормали вектора v  (см. рисунок), т.е. равенство их скалярного произведения нулю:

где

Тогда, подставив в выражение скалярного произведения векторов данные координаты векторов, получим:

Раскрыв скобки и перегруппировав, получим:

отсюда

Выражение в числителе полученной дроби – есть перпендикулярное скалярное произведение векторов v  и w, а выражение в знаменателе – перпендикулярное скалярное произведение векторов v  и u, взятое со знаком «минус». Тогда:

Аналогично найдем значение параметра t1 для отрезка Q(t):

 Таким образом, мы нашли значения параметров s1 и t1. Координаты самой точки пересечения можно найти, подставив значения одного из параметров в соответствующее уравнение отрезка. Например:

 Но полученная таким образом точка может лежать как в границах заданных отрезков, так и за их пределами, и нам необходимо определить лежит ли данная точка в границах отрезков, или нет. Для этого нужно, чтобы выполнялись следующие условия:

 Вот и вся теория необходимая нам для данной операции. Данную статью Вы можете скачать в формате pdf здесь (более читабельна).
Краткое описание алгоритма было взято отсюда. Я его только перевел и подробно расписал.