Найти пересечение прямых, заданных координатами пар точек на них

Question

Есть 2 отрезка
AB - 1 отрезок
CD - 2 отрезок

На вход поступают следующие данные
A[x1, y1] B[x2, y2]
C[x3, y3] D[x4, y5]

Нужно найти мнимую точку пересечения (Координаты) Картинка ниже (красный кружок), желательно решение на JS

Answer 1

Зададим прямые параметрическими уравнениями. Для первой прямой (пусть будет прямая A, задана точками A0, A1)

x(t) = ax0 + (ax1 - ax0) * t
y(t) = ay0 + (ay1 - ay0) * t

t - это параметр, равный нулю для точки A0, равный единице для точки A1, находится в диапазоне 0..1 для точек внутри отрезка A0A1 и т.д.

Для второй прямой (B)

x(u) = bx0 + (bx1 - bx0) * u
y(u) = by0 + (by1 - by0) * u

Прямые пересекаются в точке, в которой и X- и Y-координаты для обеих прямых совпадают, что приводит к следующей системе линейных уравнений относительно параметров t и u:

ax0 + (ax1 - ax0) * t = bx0 + (bx1 - bx0) * u
ay0 + (ay1 - ay0) * t = by0 + (by1 - by0) * u

Решаем систему, находим t, потом подставляем полученный параметр в первые уравнения для нахождения точки пересечения.

Иногда система может не иметь решений - когда прямые параллельны, или иметь бесконечное количество решений - когда прямые совпадают.

На Python:

def line_intersection(ax0, ay0, ax1, ay1, bx0, by0, bx1, by1):
    adx = ax1 - ax0
    ady = ay1 - ay0
    bdx = bx1 - bx0
    bdy = by1 - by0
    denom = bdy * adx - bdx * ady
    if denom == 0:    #прямые параллельны или совпадают
        return None
    t = (bdx * (ay0 - by0) + bdy * (bx0 - ax0)) / denom
    return (ax0 + adx * t, ay0 + ady * t)

print(line_intersection(0, 0, 1, 1, 3, 0, 2, 1))
print(line_intersection(0, 0, 1, 1, 3, 0, 4, 1))

>>> (1.5, 1.5)
>>> None

Если стоит задача различать совпадение и параллельность прямых, то нужно ещё внутри первого условия проверять

if (bx0 - ax0) * ady == (by0 - ay0) * adx: # прямые совпадают

БЛОГ НА HUSL

Найти пересечение прямых, заданных координатами пар точек на них

Ответы (1 шт):