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

В отличие от других предложений, это короткий и не использует внешние библиотеки, такие как 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) 

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

Итак, у нас есть линейная система:

A ₁ * x + B ₁ * y = C ₁
A ₂ * x + B ₂ * y = C ₂

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

x = D _x / D
y = D _y / D

где D – главный определитель системы:

A ₁ B ₁
A ₂ B ₂

и D _x и D _y могут быть найдены из матриц:

C ₁ B ₁
C ₂ B ₂

а также

A ₁ C ₁
A ₂ C ₂

(обратите внимание, так как столбец C заменяет столбцы кодов x и y )

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

для D

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

для D _x

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

для D _y

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

Теперь идите для кодирования:

line – создает коэффициенты A , B , C линейного уравнения на две точки,
intersection – находит точку пересечения (если таковая имеется) из двух линий, предоставляемых коэффициентами.

 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" 

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

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

Линия определяется как y = mx + b OR y = наклон * x + y-перехват

Наклон = превышение пробега = dy / dx = высота / расстояние

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)