next up previous

Back to WEBLOG

Shortest Distance between two Line Segments

Franz J. Vesely
May 2002

Model systems made of sticks play a role both in Statistical Mechanics (Hard Spherocylinders, Linear Kihara Molecules) and in Robotics (Robot Arms). The basic exercise in both settings is to determine the shortest distance between two such line segments. The method sketched here was described by Allen et al., Adv. Chem. Phys. Vol. LXXXVI, 1993, p.1.

Shortest distance between two line segments

We divide the problem in two steps: The shortest total distance is then $r_{tot}^{2}=r_{perp}^{2}+r_{in}^{2}$.

Distance between two lines in 3D:
Let $\vec{r}_{1,2}$ and $\vec{e}_{1,2}$ denote the center positions and directional unit vectors of the two segments of lengths $L_{1,2}$. The carrier lines $g_{1,2}$ are then given by $g_{1}:\;\; \vec{v}=\vec{r}_{1}+\lambda \vec{e}_{1}$ and $g_{2}:\;\; \vec{w}=\vec{r}_{2}+\mu \vec{e}_{2}$. The vector between any two points on the two lines is then
\begin{displaymath} \vec{s}'(\lambda,\mu) \equiv \vec{w}-\vec{v}= r_{12} + \mu \vec{e}_2 - \lambda \vec{e}_1 \end{displaymath} (1)

with $\vec{r}_{12}=\vec{r}_{2}-\vec{r}_{1}$. The shortest among these vectors is perpendicular to both lines; thus
$\displaystyle (r_{12} \cdot \vec{e}_1) + \mu_{0} (\vec{e}_1 \cdot \vec{e}_2) - \lambda_{0}$ $\textstyle =$ $\displaystyle 0 \hspace{5 em}$ (2)
$\displaystyle (r_{12} \cdot \vec{e}_2) + \mu_{0} - \lambda_{0} (\vec{e}_1 \cdot \vec{e}_2)$ $\textstyle =$ $\displaystyle 0 \hspace{5 em}$ (3)

Solving for the line parameters we find
$\displaystyle \lambda_{0}$ $\textstyle =$ $\displaystyle \frac{(\vec{r}_{12}\cdot \vec{e}_{1})- (\vec{r}_{12}\cdot \vec{e}_{2})(\vec{e}_{1}\cdot \vec{e}_{2})}{1- (\vec{e}_{1}\cdot \vec{e}_{2})^{2}}$ (4)
$\displaystyle \mu_{0}$ $\textstyle =$ $\displaystyle - \frac{(\vec{r}_{12}\cdot \vec{e}_{2})- (\vec{r}_{12}\cdot \vec{e}_{1})(\vec{e}_{1}\cdot \vec{e}_{2})}{1- (\vec{e}_{1}\cdot \vec{e}_{2})^{2}}$ (5)

(If you suspect that your lines may be nearly parallel, you should take care of the small denominator in some meaningful manner.)

The vector between the proximate points is
\begin{displaymath} \vec{s}=\vec{r}_{12}+\mu_{0} \vec{e}_{2}-\lambda_{0} \vec{e}_{1} \end{displaymath} (6)

and the minimum interline distance is $r_{perp}=\vert \vec{s}\vert$.

Distance between two line segments in 2D:
Think of the two carrier lines being projected down into a plane normal to $\vec{s}$. This projection, being normal to both lines, conserves distances along the lines.

The intersection point is, of course, given by $\lambda_{0}, \mu_{0}$. Taking this as the origin, the lines are now represented by $\vec{v}=\gamma \vec{e}_{1}$ and $\vec{w}=\delta \vec{e}_{2}$. For points on the given segments the parameters $\gamma$ and $\delta$ are confined to $-\lambda_{0}-L_{1}/2 \leq \gamma \leq -\lambda_{0}+L_{1}/2$ and $-\mu_{0}-L_{2}/2 \leq \delta \leq -\mu_{0}+L_{2}/2$ which defines a rectangle in ( $\gamma, \delta$) parameter space. We are now searching for the minimum of $\vert\vec{w}-\vec{v}\vert$ within that parameter region: $\vert r_{in} \vert^{2} = \min \left[f(\gamma,\delta)\right]$ with
\begin{displaymath} f(\gamma,\delta) \equiv \gamma^{2}+\delta^{2}-2 \gamma \delta (\vec{e}_{1}\cdot \vec{e}_{2}) \end{displaymath} (7)

Figure: Finding the minimum of f=gamma**2+delta**2+2*gamma*delta*(e1*e2). The bold sides of the rectangle are the lines gamma_m, delta_m (see text)



If the origin is contained in the rectangle, life is easy: the origin is the minimum, and the in-plane distance is zero!

If not, proceed as follows:
First, find the lines $\gamma_{m}$, $\delta_{m}$ that are nearest to the origin: $\gamma_{m}=-\lambda_{0}\pm L_{1}/2$, $\delta_{m}=-\mu_{0}\pm L_{2}/2$.

Now choose the line $\gamma=\gamma_{m}$ and find the value of $\delta$ that minimizes $f$: $\delta'=\gamma*(\vec{e}_{1} \cdot \vec{e}_{2})$. If $\delta'$ is in the permitted range, we set $\delta=\delta'$; otherwise, we pick the allowed $\delta$ nearest to $\delta'$. The distance at $\gamma, \delta$ is computed: $f_{1}=\gamma^{2}+\delta^{2}-2 \gamma \delta (\vec{e}_{1} \cdot \vec{e}_{2})$

The same steps are taken for $\delta=\delta_{m}$ and its optimal $\gamma$, yielding a trial value $f_{2}$.

With $r_{in}^{2}=\min\{f_{1},f_{2}\}$ we complete the calculation of the shortest total distance,
\begin{displaymath} r_{0}^{2}=r_{perp}^{2}+r_{in}^{2} \end{displaymath} (8)

Here is a skeleton code that does the job: 

	subroutine overlap(i,j)
	
! Given two line segments in space, with center positions r1,r2, 
! direction vectors e1,e2 and segment lengths L1,L2, calculate the 
! shortest distance between the two segments

	implicit double precision (a-h,o-z)
	common side
	common /configuration/x(2),y(2),z(2),ex(2),ey(2)
     1	,ez(2),xlen(2)

! See Allen, Evans, Frenkel, Mulder, Adv. Chem. Phys. Vol. LXXXVI, p. 1
	
! r1:
	x1=x(i) 
	y1=y(i)		
	z1=z(i)		
! r2:
	x2=x(j) 
	y2=y(j)		
	z2=z(j)		
! distance vector between centers:
	x12=x2-x1
	y12=y2-y1
	z12=z2-z1
! In MC/MD it may be appropriate here to apply the nearest image
! convention:
	if (x12.lt.-side/2.) x12=x12+side		
	if (x12.ge.side/2.) x12=x12-side		
	if (y12.lt.-side/2.) y12=y12+side		
	if (y12.ge.side/2.) y12=y12-side		
	if (z12.lt.-side/2.) z12=z12+side		
	if (z12.ge.side/2.) z12=z12-side		

! e1:
	ex1=ex(i) 
	ey1=ey(i)		
	ez1=ez(i)		
! e2:
	ex2=ex(j) 
	ey2=ey(j)
	ez2=ez(j)

! First, find the normal vector en at minimal distance between the 
! carrier lines g1 and g2:
! Since en is normal both to e1 and e2 we have for any normal vector
!
! r12*e1=lam-mu*(e1*e2)
! r12*e2=lam*(e1*e2)-mu

! which yields (excluding the case e1*e2=0) 

! lam0=[(e1*r12)-(e1*e2)(e2*r12)]/[1-(e1*e2)^2]
! mu0=-[(e2*r12)-(e1*e2)(e1*r12)]/[1-(e1*e2)^2]
! 
	e1r=ex1*x12+ey1*y12+ez1*z12
	e2r=ex2*x12+ey2*y12+ez2*z12
	e12=ex1*ex2+ey1*ey2+ez1*ez2
	recipr=1./(1.-e12*e12)
	xla0=recipr*(e1r-e12*e2r)
	xmu0=-recipr*(e2r-e12*e1r)

! Shortest perpendicular distance between carrier lines:
	xx12=x12+xmu0*ex2-xla0*ex1
	yy12=y12+xmu0*ey2-xla0*ey1
	zz12=z12+xmu0*ez2-xla0*ez1
	rnsq=xx12*xx12+yy12*yy12+zz12*zz12
	dd=sqrt(rnsq)


! Now for the squared in-plane distance risq between two line segments:

! Rectangle half lengths h1=L1/2, h2=L2/2	
	xlen1=xlen(i) 
	xlen2=xlen(j)
	h1=0.5*xlen1 
	h2=0.5*xlen2

! If the origin is contained in the rectangle, 
! life is easy: the origin is the minimum, and 
! the in-plane distance is zero!

	if ((xla0*xla0.le.h1*h1).and.(xmu0*xmu0.le.h2*h2)) then
	  risq=0. 	! Simple overlap

	else
! Find minimum of f=gamma^2+delta^2-2*gamma*delta*(e1*e2)
! where gamma, delta are the line parameters reckoned from the intersection
! (=lam0,mu0)


! First, find the lines gamm and delm that are nearest to the origin:
	  gam1=-xla0-h1
	  gam2=-xla0+h1
	  gamm=gam1
	  if (gam1*gam1.gt.gam2*gam2) gamm=gam2
	  del1=-xmu0-h2
	  del2=-xmu0+h2
	  delm=del1
	  if (del1*del1.gt.del2*del2) delm=del2	

! Now choose the line gamma=gamm and optimize delta:
	  gam=gamm	  
	  delms=gam*e12	  
	  aa=xmu0+delms	! look if delms is within [-xmu0+/-L/2]:
	  if (aa*aa.le.h2*h2) then
	    del=delms		! somewhere along the side gam=gamm
	  else
! delms out of range --> corner next to delms!
	    del=del1
	    a1=delms-del1
	    a2=delms-del2
	    if (a1*a1.gt.a2*a2) del=del2
	  endif
! Distance at these gam, del:
	  f1=gam*gam+del*del-2.*gam*del*e12

! Now choose the line delta=deltam and optimize gamma:
	  del=delm	  
	  gamms=del*e12	  
	  aa=xla0+gamms	! look if gamms is within [-xla0+/-L/2]:
	  if (aa*aa.le.h1*h1) then
	    gam=gamms		! somewhere along the side gam=gamm
	  else
! gamms out of range --> corner next to gamms!
	    gam=gam1
	    a1=gamms-gam1
	    a2=gamms-gam2
	    if (a1*a1.gt.a2*a2) gam=gam2
	  endif
! Distance at these gam, del:
	  f2=gam*gam+del*del-2.*gam*del*e12
	  
! Compare f1 and f2 to find risq:
	  risq=f1
	  if(f2.lt.f1) risq=f2
	endif

! Distance of closest approach squared =
! in-plane distance squared + normal distance squared:
	rclsq=rnsq+risq
	rcl=sqrt(rclsq)
	
	return
	end
next up previous
F. J. Vesely / University of Vienna