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

Пусть А, В, С и D - точки на плоскости. Тогда направленные отрезки АВ и CD задаются следующими параметрическими уравнениями:

Если отрезки АВ и CD пересекаются, то Перепишем это векторное соотношение в координатном виде:

Эта система линейных алгебраических уравнений при имеет единственное решение:

Если оба получившихся значения r и s принадлежат отрезку [0,1], то отрезки АВ и CD пересекаются и точка пересечения может быть найдена из параметрических уравнений. В случае, когда оба или одно из полученных значений не принадлежат отрезку [0,1], отрезки АВ и CD не пересекаются, но пересекаются соответствующие прямые. Равенство означает, что отрезки АВ и CD параллельны.