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

Question

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

90

我有两条相交的线段，并知道它们的端点。如何在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]

- bolt19

9

这些是线段还是直线？ - user2357112

4

这个问题主要归结为“算数题”。你可以使用代数运算来找到交点坐标的表达式，然后将该表达式插入到你的程序中。不过首先要记得检查是否存在平行线。 - user2357112

在提问之前请先搜索stackoverflow：答案 - Cao Manh Dat

4

“我知道如何在纸上做这个。”那么你的问题确切是什么？这只是纯数学，你需要在这里应用它。Python 是你的计算器。你尝试了什么？ - poke

可能是重复的问题：如何检查两条线段是否相交？ - Jerry Coffin

11个回答

91

无法置身事外，所以我们有线性系统：

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 之间进行映射。我们将使用数组 L 存储线方程的系数 A、B、C，而不是漂亮的 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"

- rook

12

此解决方案报告两条线段可能相交的位置，假设它们有无限长度。 - firelynx

7

我认为你混淆了「直线」和「线段」这两个术语。OP 要求查找直线的交点（可能是有意为之，也可能是由于不理解两者的区别）。在检查两条直线是否相交时，必须考虑到直线是无限延伸的，即从其中点（由定义它的两个点的坐标给出）向两个方向发出的射线。而在线段相交的情况下，只需检查连接给定点的线段部分是否相交，忽略其无限延伸的部分。 - rbaleksandar

3

顺便问一下，重合的线怎么办？使用上述算法，对于两条重合的线它会返回 true，但显然这种情况下不能返回一个交点（因为从数学上讲，这种情况下有无限多个交点）。我认为算法需要将其作为单独的情况处理，因为相交和重合的线是两种非常不同的情况。 - rbaleksandar

1

抱歉打扰一下，但我不明白第一种方法中A、B和C的值是如何确定的。有人可以详细解释一下吗？谢谢！ - Applecow

1

@Applecow：C 是直线的决定因素。请参考 Paul Draper 的答案（https://dev59.com/smIj5IYBdhLWcg3wERJx#20677983）。 - mrdaliri

显示剩余2条评论

28

这里有一个使用Shapely库的解决方案。Shapely通常用于GIS工作，但是它也被构建为计算几何学中有用的一部分。我将您的输入从列表更改为元组。

问题

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

解决方案

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)

- user11708734

5

重要提醒：这个解决方案仅在交点位于定义的端点之间时有效，因为Shapely仅查找线段的交点，而不是对应的无限直线的交点。 - jarlemag

23

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

- Gabriel Eng

1

我正在成功地使用这段代码。然而，我正在努力构建一个机制来告诉我点是否实际上与有限线段相交，而不是想象中的无限线。因此，我需要找到点x，y是否在（x1，y1，x2，y2）的空间内。有什么想法吗？ - Mars

@Mars，你能找到判断点是否相交的机制吗？ - Osama Naeem

@OsamaNaeem 抱歉，我不知道。那是很久以前的事了。我找到了一个解决方案，但我记不起来了。 - Mars

12

如果你的线条是多个点，你可以使用这个版本。

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

- John Paul Qiang Chen

需要使用 list 或者 nd.array 吗？ - Mir.Emad

7

我在网上没有找到一个直观的解释，所以现在我已经理解了，这是我的解决方案。这是针对无限线（我需要的），而不是线段。

您可能记得一些术语：

一条线被定义为 y = mx + b 或 y = slope * x + y-intercept

斜率 = 上升 / 下降 = 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)

- Kiki Jewell

你可以尝试使用以下这些点：A1 = [1,1] A2 = [1,3] B1 = [1,3] B2 = [3,1] - Charlie Burns

任何代表 y = ax + b 的直线都会与竖直线相撞。 - Mehdi

6

我找到的最简洁的解决方案使用了 Sympy：https://www.geeksforgeeks.org/python-sympy-line-intersection-method/。

# import sympy and Point, Line 
from sympy import Point, Line 
  
p1, p2, p3 = Point(0, 0), Point(1, 1), Point(7, 7) 
l1 = Line(p1, p2) 
  
# using intersection() method 
showIntersection = l1.intersection(p3) 
  
print(showIntersection)

- jarlemag

点类非常慢，它正在转换为分数。 - undefined

3

使用scikit-spatial库，您可以轻松地按以下方式完成：

import matplotlib.pyplot as plt

from skspatial.objects import Line

# Define the two lines.
line_1 = Line.from_points([3, -2], [5, 4])
line_2 = Line.from_points([-1, 0], [3, 2])

# Compute the intersection point
intersection_point = line_1.intersect_line(line_2)

# Plot
_, ax = plt.subplots()
line_1.plot_2d(ax, t_1=-2, t_2=3, c="k")
line_2.plot_2d(ax, t_1=-2, t_2=3, c="k")
intersection_point.plot_2d(ax, c="r", s=100)
grid = ax.grid()

- blunova

2

已经有一个答案使用了来自维基百科的公式，但是它没有任何检查点来检查线段是否实际相交，所以在这里为您提供了以下内容：

def line_intersection(a, b, c, d):
    t = ((a[0] - c[0]) * (c[1] - d[1]) - (a[1] - c[1]) * (c[0] - d[0])) / ((a[0] - b[0]) * (c[1] - d[1]) - (a[1] - b[1]) * (c[0] - d[0]))
    u = ((a[0] - c[0]) * (a[1] - b[1]) - (a[1] - c[1]) * (a[0] - b[0])) / ((a[0] - b[0]) * (c[1] - d[1]) - (a[1] - b[1]) * (c[0] - d[0]))

    # check if line actually intersect
    if (0 <= t and t <= 1 and 0 <= u and u <= 1):
        return [a[0] + t * (b[0] - a[0]), a[1] + t * (b[1] - a[1])]
    else: 
        return False
    
#usage
print(line_intersection([0,0], [10, 10], [0, 10], [10,0]))

#result [5.0, 5.0]

- Bob

如果您检查此问题的更易读和被接受的答案，您可能会认识到它通过计算x和y差的行列式来检查线是否相交。 - MaKaNu

我在谈论的是那个没有检查点的维基百科公式 @MaKaNu。 - Bob

在这种情况下，您应该添加到您想要改进的答案的链接。您可以使用答案中的共享按钮来实现此目的。 - MaKaNu

我在谈论 https://dev59.com/smIj5IYBdhLWcg3wERJx#51127674 @MaKaNu - Bob

1

是的，我已经在您上一条评论后理解了这个问题。但是，这里有几个答案。您应该编辑您的回答，或者更好的方式是提供一个编辑（如果可能的话）到原始回答中，而不是将链接放入另一个评论中。 - MaKaNu

这个方案完美地运作了，我更喜欢这个方案而不是前面的那个。 - مهند عبد الجليل

0

img你可以使用这段代码

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

- Abdurrhman Sefer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul Draper · Accepted Answer

与其他建议不同的是，这个建议很简短，不使用像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))

顺便说一句，我会使用元组来代替列表来表示你的点。例如：

A = (X, Y)

编辑：最初有个错别字。感谢@zidik，该问题已在2014年9月得到修复。

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

$\mathbf{p} = \frac{ \begin{vmatrix} \begin{vmatrix}\mathbf{a_1} & \mathbf{a_2}\end{vmatrix} & \mathbf{a_1} - \mathbf{a_2} \\ \begin{vmatrix}\mathbf{b_1} & \mathbf{b_2}\end{vmatrix} & \mathbf{b_1} - \mathbf{b_2} \end{vmatrix} }{\begin{vmatrix}\mathbf{a_1} - \mathbf{a_2} & \mathbf{b_1} - \mathbf{b_2}\end{vmatrix}}$