Back to WEBLOG
Shortest Distance between two Line Segments
Franz J. Vesely
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
- Determine the distance in 3D space between
the two ``carrier'' lines of the line segments; keep the vector
between the closest points on the two lines.
Note that this vector is normal to both lines.
- Project the two lines onto a plane normal to .
Since is normal to both lines this projection conserves
distances on the lines.
Now determine the shortest distance within the plane between
the two line segments.
Distance between two lines in 3D:
Let and denote the center positions and
directional unit vectors of the two segments of lengths .
The carrier lines are then given by
The vector between any two points on the two lines is then
. The shortest among these
vectors is perpendicular to both lines; thus
Solving for the line parameters we find
(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
and the minimum interline distance is
Distance between two line segments in 2D:
Think of the two carrier lines being projected down into a plane
normal to . This projection, being normal to both lines,
conserves distances along the lines.
The intersection point is, of course, given by
Taking this as the origin, the lines are now represented
For points on the given segments the parameters and
are confined to
which defines a
rectangle in (
) parameter space. We are now searching
for the minimum of
within that parameter region:
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 , that are nearest to the
Now choose the line
and find the value of that
If is in the permitted range, we set
otherwise, we pick the allowed nearest to .
The distance at
The same steps are taken for
and its optimal ,
yielding a trial value .
we complete the calculation of the
shortest total distance,
Here is a skeleton code that does the job:
! 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)
! See Allen, Evans, Frenkel, Mulder, Adv. Chem. Phys. Vol. LXXXVI, p. 1
! distance vector between centers:
! In MC/MD it may be appropriate here to apply the nearest image
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
! 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
! which yields (excluding the case e1*e2=0)
! Shortest perpendicular distance between carrier lines:
! Now for the squared in-plane distance risq between two line segments:
! Rectangle half lengths h1=L1/2, h2=L2/2
! 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
! Find minimum of f=gamma^2+delta^2-2*gamma*delta*(e1*e2)
! where gamma, delta are the line parameters reckoned from the intersection
! First, find the lines gamm and delm that are nearest to the origin:
if (gam1*gam1.gt.gam2*gam2) gamm=gam2
if (del1*del1.gt.del2*del2) delm=del2
! Now choose the line gamma=gamm and optimize delta:
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
! delms out of range --> corner next to delms!
if (a1*a1.gt.a2*a2) del=del2
! Distance at these gam, del:
! Now choose the line delta=deltam and optimize gamma:
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
! gamms out of range --> corner next to gamms!
if (a1*a1.gt.a2*a2) gam=gam2
! Distance at these gam, del:
! Compare f1 and f2 to find risq:
! Distance of closest approach squared =
! in-plane distance squared + normal distance squared:
F. J. Vesely / University of Vienna