Определение точки пересечения двух отрезков

Пусть даны два отрезка. Первый задан точками P₁(x₁;y₁) и P₂(x₂;y₂). Второй задан точками P₃(x₃;y₃) и P₄(x₄;y₄).

Взаимное расположение отрезков можно проверить с помощью векторных произведений:

Рассмотрим отрезок P₃P₄ и точки P₁ и P₂.

Точка P₁ лежит слева от прямой P₃P₄, для нее векторное произведение v₁ > 0, так как векторы положительно ориентированы.
Точка P₂ расположена справа от прямой, для нее векторное произведение v₂ < 0, так как векторы отрицательно ориентированы.

Для того чтобы точки P₁ и P₂ лежали по разные стороны от прямой P₃P₄, достаточно, чтобы выполнялось условие v₁v₂ < 0 (векторные произведения имели противоположные знаки).

Аналогичные рассуждения можно провести для отрезка P₁P₂ и точек P₃ и P₄.

Итак, если v₁v₂ < 0 и v₃v₄ < 0, то отрезки пересекаются.

Векторное произведение двух векторов вычисляется по формуле:

где:
ax, ay - координаты первого вектора,
bx, by - координаты второго вектора.

Уравнение прямой, проходящей через две различные точки, заданные своими координатами.

Пусть на прямой заданы две не совпадающие точки:P₁ с координатами (x₁;y₁) и P₂ с координатами (x₂; y₂). Соответственно вектор с началом в точке P₁ и концом в точке P₂ имеет координаты (x₂-x₁, y₂-y₁). Если P(x, y) – произвольная точка на прямой, то координаты вектора P₁P равны (x - x₁, y – y₁).

С помощью векторного произведения условие коллинеарности векторов P₁P и P₁P₂ можно записать так:
|P₁P,P₁P₂|=0, т.е. (x-x₁)(y₂-y₁)-(y-y₁)(x₂-x₁)=0
или
(y₂-y₁)x + (x₁-x₂)y + x₁(y₁-y₂) + y₁(x₂-x₁) = 0

Последнее уравнение переписывается следующим образом:
ax + by + c = 0,     (1)
где
a = (y₂-y₁),
b = (x₁-x₂),
c = x₁(y₁-y₂) + y₁(x₂-x₁)

Итак, прямую можно задать уравнением вида (1).

Как найти точку пересечения прямых?
Очевидное решение состоит в том, чтобы решить систему уравнений прямых:

ax₁+by₁=-c₁
ax₂+by₂=-c₂     (2)

Ввести обозначения:

Здесь D – определитель системы, а D_x,D_y - определители, получающиеся в результате замены столбца коэффициентов при соответствующем неизвестном столбцом свободных членов. Если D ≠ 0, то система (2) является определенной, то есть имеет единственное решение. Это решение можно найти по следующим формулам: x₁=D_x/D, y₁=D_y/D, которые называются формулами Крамера. Небольшое напоминание, как вычисляется определитель второго порядка. В определителе различают две диагонали: главную и побочную. Главная диагональ состоит из элементов, взятых по направлению от верхнего левого угла определителя в нижний правый угол. Побочная диагональ – из правого верхнего в нижний левый. Определитель второго порядка равен произведению элементов главной диагонали минус произведение элементов побочной диагонали.