
Hi, I’m Higashi.
Here’s how to estimate the coordinates where two lines intersect.

Start with the coordinates of two points defining each line.
Let’s get started!
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.

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

At an intersection, the points P and Q coincide. The search approximates that point.
Here’s how to do it in Python.
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.

The graph puts the intersection between x = 2 and 3 and y = 5 and 6.
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.
Sample output
Let’s run the program.
Here’s the output.

The variable mean_pos holds the estimated intersection.
Now compare it with the graph.

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

Thanks for reading!


コメント