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

Question

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

У меня есть две линии, которые пересекаются в одной точке. Я знаю конечные точки этих двух линий. Как вычислить точку пересечения в 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]

5261 6

python lines

6 ответов:

Comments

Reply

Sergey 5 лет назад

<pre>
<code>необходимо учесть случай деления на ноль
def slope(P1, P2):
# dy/dx
# (y2 - y1) / (x2 - x1)
# divide zero
</code></pre>

 if (P2[0] - P1[0]) == 0:

 return 0

 else:

 return(P2[1] - P1[1]) / (P2[0] - P1[0])<code> </code>

<pre>
<code>
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</code></pre>

Reply

Sergey 5 лет назад

# для отрезков

# intersection lines

def slope(P1, P2):

 # dy/dx

 # (y2 - y1) / (x2 - x1)

 if (P2[0] - P1[0]) == 0:

 return 0

 else:

 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

 

def otrezok(a,b):

 if ( ((a[0]>b[0]) and (a[1]>b[1]) ) or ((a[0]<b[0]) and (a[1]<b[1]) ) ):

 print("Lines short")

 return None

A1 = [10,1]

A2 = [30,30]

B1 = [21,16]

B2 = [21,6]

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)

d=line_intersect(slope_A, y_int_A, slope_B, y_int_B)

print(type(d))#line_intersect(slope_A, y_int_A, slope_B, y_int_B))

print(d)

print(otrezok(A1,d))

Paul Draper · Accepted Answer · 2014-09-13 00:45:16

В отличие от других предложений, он короткий и не использует внешние библиотеки, такие как numpy. (Не то, чтобы использование других библиотек является bad...it приятно не надо, особенно для такой простой задачи.)
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))
И к вашему сведению, я бы использовал кортежи вместо списков для ваших очков. Например,
A = (X, Y)

rook · Accepted Answer · 2013-12-19 12:46:47

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

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

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

Давайте сделаем это с помощью правила Крамера, чтобы решение можно было найти в детерминантах:

X = D _x/D
y = D _y/D

Где D - главный детерминант системы:

A₁ B₁
А₂ B₂

И D _x и D _y можно найти из matricies:

C₁ B₁
С₂ B₂

И

A₁ С₁
А₂ С₂

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

Итак, теперь python, для ясности для нас, чтобы не испортить вещи, давайте сделаем отображение между math и python. Мы будем использовать массив L для хранения наших coefs A, B, C линейных уравнений и intestead 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 - производит 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"

Kiki Jewell · Accepted Answer · 2017-09-19 00:50:17

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

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

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

Наклон = подъем = ду / ДХ = высота / расстояние

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)

Gabriel Eng · Accepted Answer · 2018-07-02 02:31:52

Используя формулу из: https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

 def findIntersection(x1,y1,x2,y2,x3,y3,x4,y4):
        px= ( (x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4) ) / ( (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4) ) 
        py= ( (x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4) ) / ( (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4) )
        return [px, py]