Python 如何计算两条线的交点？

How do I compute the intersection point of two lines?

提问by bolt19

I have two lines that intersect at a point. I know the endpoints of the two lines. How do I compute the intersection point in 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]

采纳答案by Paul Draper

Unlike other suggestions, this is short and doesn't use external libraries like numpy. (Not that using other libraries is bad...it's nice not need to, especially for such a simple problem.)

与其他建议不同，这很简短，并且不使用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])

    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))

And FYI, I would use tuples instead of lists for your points. E.g.

仅供参考，我会使用元组而不是列表来表示您的观点。例如

A = (X, Y)

---

---

EDIT: Initially there was a typo. That was fixedSept 2014 thanks to @zidik.

编辑：最初有一个错字。这是固定的2014年9月拜@zidik。

This is simply the Python transliteration of the following formula, where the lines are (a1, a2) and (b1, b2) and the intersection is p. (If the denominator is zero, the lines have no unique intersection.)

这只是以下公式的 Python 音译，其中线是 ( a1, a2) 和 ( b1, b2)，交点是p。（如果分母为零，则这些线没有唯一的交点。）

回答by rook

Can't stand aside,

不能袖手旁观，

So we have linear system:

所以我们有线性系统：

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

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

let's do it with Cramer's rule, so solution can be found in determinants:

让我们用克莱默规则来做，所以可以在行列式中找到解决方案：

x = D_x/D
y = D_y/D

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

where Dis main determinant of the system:

其中D是系统的主要决定因素：

A₁B₁
A₂B₂

A ₁B ₁
A ₂B ₂

and D_xand D_ycan be found from matricies:

和D _x和D _y可以从矩阵中找到：

C₁B₁
C₂B₂

C ₁B ₁
C ₂B ₂

and

和

A₁C₁
A₂C₂

A ₁C ₁
A ₂C ₂

(notice, as Ccolumn consequently substitues the coef. columns of xand y)

（注意，因为C列因此替换了x和y的系数列）

So now the python, for clarity for us, to not mess things up let's do mapping between math and python. We will use array Lfor storing our coefs A, B, Cof the line equations and intestead of pretty x, ywe'll have [0], [1], but anyway. Thus, what I wrote above will have the following form further in the code:

所以现在python，为了让我们清楚起见，不要搞砸了，让我们在数学和python之间进行映射。我们将使用数组L来存储我们的线性方程的系数A、B、C，而不是漂亮的x，y我们将有[0], [1]，但无论如何。因此，我上面写的内容将在代码中进一步具有以下形式：

for D

对于D

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

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

for D_x

对于D _x

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

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

for D_y

对于d _ÿ

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

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

Now go for coding:

现在开始编码：

line- produces coefs A, B, Cof line equation by two points provided,
intersection- finds intersection point (if any) of two lines provided by coefs.

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

Usage example:

用法示例：

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"

回答by Kiki Jewell

I didn't find an intuitive explanation on the web, so now that I worked it out, here's my solution. This is for infinite lines (what I needed), not segments.

我在网上没有找到直观的解释，所以现在我解决了，这是我的解决方案。这是用于无限线（我需要的），而不是线段。

Some terms you might remember:

您可能还记得一些术语：

A line is defined as y = mx + b OR y = slope * x + y-intercept

Slope = rise over run = dy / dx = height / distance

Y-intercept is where the line crosses the Y axis, where X = 0

一条线定义为 y = mx + b 或 y = 斜率 * x + y 截距

坡度 = 上升高度 = dy / dx = 高度 / 距离

Y 轴截距是线与 Y 轴的交点，其中 X = 0

Given those definitions, here are some functions:

鉴于这些定义，这里有一些函数：

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

Here's a simple test between two (infinite) lines:

这是两行（无限）之间的简单测试：

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))

Output:

输出：

(2.0, 2.0)

回答by Gabriel Eng

Using formula from: https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

使用以下公式：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]

回答by Paul Chen

If your lines are multiple points instead, you can use this version.

如果您的线条是多个点，则可以使用此版本。

import numpy as np
import matplotlib.pyplot as plt
"""
Sukhbinder
5 April 2017
Based on:    
"""

def _rect_inter_inner(x1,x2):
    n1=x1.shape[0]-1
    n2=x2.shape[0]-1
    X1=np.c_[x1[:-1],x1[1:]]
    X2=np.c_[x2[:-1],x2[1:]]    
    S1=np.tile(X1.min(axis=1),(n2,1)).T
    S2=np.tile(X2.max(axis=1),(n1,1))
    S3=np.tile(X1.max(axis=1),(n2,1)).T
    S4=np.tile(X2.min(axis=1),(n1,1))
    return S1,S2,S3,S4

def _rectangle_intersection_(x1,y1,x2,y2):
    S1,S2,S3,S4=_rect_inter_inner(x1,x2)
    S5,S6,S7,S8=_rect_inter_inner(y1,y2)

    C1=np.less_equal(S1,S2)
    C2=np.greater_equal(S3,S4)
    C3=np.less_equal(S5,S6)
    C4=np.greater_equal(S7,S8)

    ii,jj=np.nonzero(C1 & C2 & C3 & C4)
    return ii,jj

def intersection(x1,y1,x2,y2):
    """
INTERSECTIONS Intersections of curves.
   Computes the (x,y) locations where two curves intersect.  The curves
   can be broken with NaNs or have vertical segments.
usage:
x,y=intersection(x1,y1,x2,y2)
    Example:
    a, b = 1, 2
    phi = np.linspace(3, 10, 100)
    x1 = a*phi - b*np.sin(phi)
    y1 = a - b*np.cos(phi)
    x2=phi    
    y2=np.sin(phi)+2
    x,y=intersection(x1,y1,x2,y2)
    plt.plot(x1,y1,c='r')
    plt.plot(x2,y2,c='g')
    plt.plot(x,y,'*k')
    plt.show()
    """
    ii,jj=_rectangle_intersection_(x1,y1,x2,y2)
    n=len(ii)

    dxy1=np.diff(np.c_[x1,y1],axis=0)
    dxy2=np.diff(np.c_[x2,y2],axis=0)

    T=np.zeros((4,n))
    AA=np.zeros((4,4,n))
    AA[0:2,2,:]=-1
    AA[2:4,3,:]=-1
    AA[0::2,0,:]=dxy1[ii,:].T
    AA[1::2,1,:]=dxy2[jj,:].T

    BB=np.zeros((4,n))
    BB[0,:]=-x1[ii].ravel()
    BB[1,:]=-x2[jj].ravel()
    BB[2,:]=-y1[ii].ravel()
    BB[3,:]=-y2[jj].ravel()

    for i in range(n):
        try:
            T[:,i]=np.linalg.solve(AA[:,:,i],BB[:,i])
        except:
            T[:,i]=np.NaN


    in_range= (T[0,:] >=0) & (T[1,:] >=0) & (T[0,:] <=1) & (T[1,:] <=1)

    xy0=T[2:,in_range]
    xy0=xy0.T
    return xy0[:,0],xy0[:,1]


if __name__ == '__main__':

    # a piece of a prolate cycloid, and am going to find
    a, b = 1, 2
    phi = np.linspace(3, 10, 100)
    x1 = a*phi - b*np.sin(phi)
    y1 = a - b*np.cos(phi)

    x2=phi
    y2=np.sin(phi)+2
    x,y=intersection(x1,y1,x2,y2)
    plt.plot(x1,y1,c='r')
    plt.plot(x2,y2,c='g')
    plt.plot(x,y,'*k')
    plt.show()

回答by user11708734

Here is a solution using the Shapelylibrary. Shapely is often used for GIS work, but is built to be useful for computational geometry. I changed your inputs from lists to tuples.

这是使用Shapely库的解决方案。Shapely 通常用于 GIS 工作，但其构建用于计算几何。我将您的输入从列表更改为元组。

Problem

问题

# 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)

Solution

解决方案

import shapely
from shapely.geometry import LineString, Point

line1 = LineString([A, B])
line2 = LineString([C, D])

int_pt = line1.intersection(line2)
point_of_intersection = int_pt.x, int_pt.y

print(point_of_intersection)

回答by Abdurrhman Sefer

img And You can use this kode

img 你可以使用这个 kode

class Nokta:
def __init__(self,x,y):
    self.x=x
    self.y=y             
class Dogru:
def __init__(self,a,b):
    self.a=a
    self.b=b        

def Kesisim(self,Dogru_b):
    x1= self.a.x
    x2=self.b.x
    x3=Dogru_b.a.x
    x4=Dogru_b.b.x
    y1= self.a.y
    y2=self.b.y
    y3=Dogru_b.a.y
    y4=Dogru_b.b.y                          
    #Notlardaki denklemleri kulland?m
    pay1=((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))      
    pay2=((x2-x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))
    payda=((y4 - y3) *(x2-x1)-(x4 - x3)*(y2 - y1))        

    if pay1==0 and pay2==0 and payda==0:
        print("DO?RULAR B?RB?R?NE ?AKI?IKTIR")

    elif payda==0:               
        print("DO?RULAR B?RB?RNE PARALELD?R")        
    else:                               
        ua=pay1/payda if payda else 0                   
        ub=pay2/payda  if payda else 0  
        #x ve y buldum 
        x=x1+ua*(x2-x1) 
        y=y1+ua*(y2-y1)
        print("DO?RULAR {},{} NOKTASINDA KES??T?".format(x,y))