“Python” Calculate Minimum Distance & Closest Coordinate from Two Lines.

higashi

Hi, I’m higashi.

This time, I introduce how to calculate minimum distance and closest coordinate from two lines that has not intersection as shown below.

*Python is used for this calculation in this page.

★Rough sketch of how to calculate minimum distance of two lines

★Rough sketch of how to calculate closest coordinate of two lines

Just only you should do is designate 2 line’s start and end point coordinate (a, b, c, d).

OK, let’s get started!!

Image of How to Calculate

These calculation shown above is easy for human but difficult for computer.

How computer calculate these problem?

The answer is exhaustive calculation.

Below picture is the image of calculation.

1st.step : Add point on each lines at random.

2nd.step : Move points and search minimum distance points by exhaustive calculation.

Anyway, let’s start coding!!

Sample Code of Calculate Distance & Closest Point Coordinate from Two Lines

The below code can calculate distance & closest point coordinate from two designated lines.

#import library
import numpy as np
import matplotlib.pyplot as plt 
from mpl_toolkits.mplot3d import Axes3D

#designate two line's(ab,cd) start & end point coordinate
a=[0,0,0]
b=[1,2,3]
c=[4,5,-6]
d=[7,8,9]
line1=[a,b]
line2=[c,d]
a,b=line1[0],line1[1]
c,d=line2[0],line2[1]
ABvec=np.array([b[0]-a[0],b[1]-a[1],b[2]-a[2]])
CDvec=np.array([d[0]-c[0],d[1]-c[1],d[2]-c[2]])

#function of calculate distance
def calc_distance(s,t):
    a,b=line1[0],line1[1]
    c,d=line2[0],line2[1]
    ABvec=np.array([b[0]-a[0],b[1]-a[1],b[2]-a[2]])
    CDvec=np.array([d[0]-c[0],d[1]-c[1],d[2]-c[2]])
    PQvec=(c+CDvec*s)-(a+ABvec*t)
    distance=np.linalg.norm(PQvec)
    return distance

#function of calculate position on line
def calc_pos(s,t):
    Qpos=(c+CDvec*s)
    Ppos=(a+ABvec*t)
    return Ppos,Qpos
#function for search
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

#setting for search
ini_max=2000
ini_min=-2000
delta=200
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)

#main program
minz_list=[]
for k in range(7):
    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('min_distance=', min_val)
print('mean_pos=', (Qpos+Ppos)/2)

Just you should do is input coordinate of 4 point (7~10 line of code).

Result of Sample Code

Below result is shown by conducted above code.

I confirm this is almost correct by manual calculation with formula.

That’s all. Thank you!!