[Python] Find the Intersection of Two Lines

Python
higashi
higashi

Hi, I’m Higashi.

 

Here’s how to estimate the coordinates where two lines intersect.

Illustration of calculate intersection coordinates

Start with the coordinates of two points defining each line.

 

Let’s get started!

 

Sponsored Links

How the search finds an intersection

The diagrams show the search process.

 

Start with a candidate point on each line.

Calculate the distance between those points.

how to calculate the intersection coordinates

Repeat this for different pairs and look for the smallest distance.

how to calculate the intersection coordinates

At an intersection, the points P and Q coincide. The search approximates that point.

 

Here’s how to do it in Python.

 

Sponsored Links

Define the two lines

First, choose two points for each line.

 

I’ll use the following coordinates:

a=[1,2]
b=[4,8]
c=[1,7]
d=[7,2]

Here’s how the lines look on a graph.

graph image of two lines

The graph puts the intersection between x = 2 and 3 and y = 5 and 6.

 

Sponsored Links

Sample program for estimating the intersection

Here’s the program.

#import library
import numpy as np

#designate the coordinates of two lines.
a=[1,2]
b=[4,8]
c=[1,7]
d=[7,2]
#set the vector of two lines
line1=[a,b]
line2=[c,d]
a,b=line1[0],line1[1]
c,d=line2[0],line2[1]
ABbec=np.array([b[0]-a[0],b[1]-a[1]])
CDbec=np.array([d[0]-c[0],d[1]-c[1]])

#function of calculate two point distance
def calc_distance(s,t):
    PQbec=(c+CDbec*s)-(a+ABbec*t)
    distance=np.linalg.norm(PQbec)
    return distance
#function of calculate point coordinates
def calc_pos(s,t):
    Qpos=(c+CDbec*s)
    Ppos=(a+ABbec*t)
    return Ppos,Qpos
    
#function of searching minimun distance
def make_map(ss,tt):
    z_list=[]
    ij_list=[]
    st_list=[]
    for i in range(len(ss)):
        for j in range(len(tt)):
            s,t=ss[i],tt[j]
            z=calc_distance(s,t)
            z_list.append(z)
            ij_list.append([i,j])
            st_list.append([s,t])
    return z_list,ij_list,st_list

#explore a large area
ini_max=2000
ini_min=-2000
delta=200
num_search=7
ss=np.linspace(ini_min,ini_max,delta)
tt=np.linspace(ini_min,ini_max,delta)
z,ij,st=make_map(ss,tt)
min_val=np.amin(np.array(z))
min_index=z.index(min_val)

#explore a neighborhood area of goal
minz_list=[]
for k in range(num_search):
    i,j=ij[min_index][0],ij[min_index][1]
    smax,smin=min(ss[i+2],ini_max),max(ss[i-2],ini_min)
    tmax,tmin=min(tt[j+2],ini_max),max(tt[j-2],ini_min)
    ss=np.linspace(smin,smax,delta)
    tt=np.linspace(tmin,tmax,delta)
    z,ij,st=make_map(ss,tt)
    min_val=np.amin(np.array(z))
    min_index=z.index(min_val)
    minz_list.append(min_val)
    Ppos,Qpos=calc_pos(st[min_index][0],st[min_index][1])
print('Ppos=')
print(Ppos)
print('Qpos=')
print(Qpos)
print('mean_pos=')
print((Qpos+Ppos)/2)

 

The program searches a range of candidate points.

Set that search range before running the program.

Use ini_min and ini_max to set the initial bounds.

Use delta and num_search to set the step size and number of search iterations.

 

Adjust these values to suit the lines you’re working with.

A wider or more detailed search can take longer.

 

Sponsored Links

Sample output

Let’s run the program.

Here’s the output.

Result of sample program

The variable mean_pos holds the estimated intersection.

Now compare it with the graph.

graph image of two lines

The estimated coordinates agree with the intersection shown on the graph.

 

higashi
higashi

 

Thanks for reading!

コメント