Как вычислить точку пересечения двух строк в Python?

Question

У меня есть две линии, которые пересекаются в точке. Я знаю конечные точки двух линий. Как вычислить точку пересечения в Python?

# Given these endpoints 
#line 1 
A = [X, Y] 
B = [X, Y] 

#line 2 
C = [X, Y] 
D = [X, Y] 

# Compute this: 
point_of_intersection = [X, Y] 

Answer 1

В отличие от других предложений, это короткий и не использовать внешние библиотеки, как numpy. (Не то, чтобы с помощью других библиотек плохо ... это приятно не нужно, особенно для такой простой задачи.)

def line_intersection(line1, line2): 
    xdiff = (line1[0][0] - line1[1][0], line2[0][0] - line2[1][0]) 
    ydiff = (line1[0][1] - line1[1][1], line2[0][1] - line2[1][1]) #Typo was here 

    def det(a, b): 
     return a[0] * b[1] - a[1] * b[0] 

    div = det(xdiff, ydiff) 
    if div == 0: 
     raise Exception('lines do not intersect') 

    d = (det(*line1), det(*line2)) 
    x = det(d, xdiff)/div 
    y = det(d, ydiff)/div 
    return x, y 

print line_intersection((A, B), (C, D)) 

И FYI, я хотел бы использовать кортежи вместо списков для точек. Например.

A = (X, Y) 

Answer 2

не может стоять в стороне,

Итак, мы имеем линейную систему:

* х + B * у = C 1
* x + B * y = C

давайте делать это с правилом Крамера, поэтому решение может быть найдено в определителей:

х = D _х/D
у = D _у/D

, где D является основным определителем системы:

Б
Б

и Д _х и D _у можно найти из матриц,:

С Б
С Б

и

С
С

(уведомление, а С колонку, следовательно, Substitues на коэф. Столбцы х и у)

Так что теперь питон, для ясности для нас, чтобы не натворить давайте отображение между математикой и питоном.Мы будем использовать массив L для хранения нашего coefs , B, C уравнений линии и intestead красивой x, y мы будем иметь [0], [1], но в любом случае. Таким образом, то, что я написал выше, будет иметь следующий вид дальше в коде:

для D

L1 [0] L1 [1]
L2 [0] L2 [1]

для D _х

L1 [2] L1 [1]
L2 [2] L2 [1]

для Д _у

L1 [0] L1 [2]
L2 [ 0] L2 [2]

Сейчас идут для кодирования:

- производит coefs A, B, C уравнения линию по двум точкам при условии,
intersection - находит точку пересечения (если таковые имеются) из двух линий обеспечивается coefs.

from __future__ import division 

def line(p1, p2): 
    A = (p1[1] - p2[1]) 
    B = (p2[0] - p1[0]) 
    C = (p1[0]*p2[1] - p2[0]*p1[1]) 
    return A, B, -C 

def intersection(L1, L2): 
    D = L1[0] * L2[1] - L1[1] * L2[0] 
    Dx = L1[2] * L2[1] - L1[1] * L2[2] 
    Dy = L1[0] * L2[2] - L1[2] * L2[0] 
    if D != 0: 
     x = Dx/D 
     y = Dy/D 
     return x,y 
    else: 
     return False 

Пример использования:

L1 = line([0,1], [2,3]) 
L2 = line([2,3], [0,4]) 

R = intersection(L1, L2) 
if R: 
    print "Intersection detected:", R 
else: 
    print "No single intersection point detected" 

Answer 3

я не нашел интуитивное объяснение в Интернете, так что теперь, когда я работал его, вот мое решение. Это для бесконечных линий (что мне нужно), а не для сегментов.

Некоторые термины, которые вы, возможно, помните:

линия определяется как у = х + Ь OR у = наклон * х + у-перехватывать

Slope = подъем над перспективе = ду/дх = высота/расстояние

Y-перехват, где линия пересекает ось Y, где X = 0

с учетом этих определений, вот некоторые функции:

def slope(P1, P2): 
    # dy/dx 
    # (y2 - y1)/(x2 - x1) 
    return(P2[1] - P1[1])/(P2[0] - P1[0]) 

def y_intercept(P1, slope): 
    # y = mx + b 
    # b = y - mx 
    # b = P1[1] - slope * P1[0] 
    return P1[1] - slope * P1[0] 

def line_intersect(m1, b1, m2, b2): 
    if m1 == m2: 
     print ("These lines are parallel!!!") 
     return None 
    # y = mx + b 
    # Set both lines equal to find the intersection point in the x direction 
    # m1 * x + b1 = m2 * x + b2 
    # m1 * x - m2 * x = b2 - b1 
    # x * (m1 - m2) = b2 - b1 
    # x = (b2 - b1)/(m1 - m2) 
    x = (b2 - b1)/(m1 - m2) 
    # Now solve for y -- use either line, because they are equal here 
    # y = mx + b 
    y = m1 * x + b1 
    return x,y 

Вот простой тест между двумя (бесконечными) линий:

A1 = [1,1] 
A2 = [3,3] 
B1 = [1,3] 
B2 = [3,1] 
slope_A = slope(A1, A2) 
slope_B = slope(B1, B2) 
y_int_A = y_intercept(A1, slope_A) 
y_int_B = y_intercept(B1, slope_B) 
print(line_intersect(slope_A, y_int_A, slope_B, y_int_B)) 

Выход:

(2.0, 2.0)