[Home]   [Projects]    [Delphi Techniques]   [Math Topics]   [Library]   [Utilities]

Determining if two arbitrary line segments intersect is a task that again makes me appreciate the human  brain.  What is trivial for our visual processing  system is surprisingly complicated for a computer program.   It's necessary for many simulation tasks though, for example simulated  movement of a robot or other object.  If it reaches a wall and passes right through, the reality effect is  lost.   I understand that ray tracing routines used to simulate lighting in 3D scene simulations must detect objects in order to bounce the ray.  And in the immediate case, our cannonball needs to know when it hits the target.

There are a number of published intersection algorithms using determinants (which I'm sure I  used to understand) but the logic behind them is not obvious.  I decided to go back to high school algebra basics: we'll determine the equations of the 2 lines, find out where they intersect (unless they're parallel, they will intersect somewhere), then determine if the intersection point is between the endpoints of each segment.

A refresher: 

 The general equation of a line is usually written as y=mx + b where m is the slope of the line and b is the intercept.   Slope is how much the vertical (y) coordinate changes for each unit of change in the horizontal direction (x).   Intercept is where the line crosses the y-axis, i.e. the value of y when x=0.  

If we know two points on a line (x₁,y₁) and (x₂,y₂), we can determine m and b as follows.  From its definition,  m = change in y divided by change in x = (y₂-y₁)/(x₂-x₁). And since b=y-mx for any point on the line, we can compute b₁=y₁-mx₁.  

With two line segments, we can derive an equation for each, say y=m₁x+b₁ and y=m₂x+b₂.   The x and y values at the  intersection point must satisfy both, so y = m₁x+b₁=m₂x+b₂.  If we take the last half of this and solve for x, we get m₁x+b₁=m₂x+b₂, or (m₁-m₂)x=b₂-b₁ or x=(b₂-b₁)/(m₁-m₂).   Notice that when m₁ equals m₂, the lines are parallel and they will never intersect.  (unless b1 also equals b2 in which case the lines are co-linear). 

The final test is to see if the intersection point is between the endpoints of each line segment.   This just involves making sure that our x is greater   than (or equal to) the smallest x endpoint value and smaller than (or equal to)  the largest endpoint x value for each line.   

The code:

Here's the pertinent Delphi code extract that does this.

Type

  Tline=array[1..2] of TPoint; {starting and ending points of a line segment}

...............

function Linesintersect(line1,line2:TLine):boolean;
{local procedure: getequation}
procedure getequation(line:TLine;var slope,intercept:extended);
begin
If line.p1.x<>line.p2.x
then slope:=(line.p2.y-line.p1.y)/ (line.p2.x-line.p1.x)
else slope:=1E100;
intercept:=line.p1.y-slope*line.p1.x;
end;

function overlap(const x,y:extended; const line:TLine):boolean;
{return true if passed x and y are within the range of the endpoints of the
passed line}
begin
If (x>=min(line.p1.x,line.p2.x))
and (x<=max(line.p1.x,line.p2.x))
and (y>=min(line.p1.y,line.p2.y))
and (y<=max(line.p1.y,line.p2.y))
then result:=true
else result:=false;
end;

var
m1,m2,b1,b2:extended;
x,y:extended;

begin
{Method -
a. find the equations of the lines,
b. find where they intersect
c. if the point is between the line segment end points for both lines,
then they do intersect, otherwise not.
}
result:=false;
{general equation of line: y=mx+b}
getequation(line1,m1,b1);
getequation(line2,m2,b2);

{intersection condition
any point (x,y) on line1 satisfies y=m1*x+b1, the intersection
point also satisfies the line2 equation y=m2*x+b2,
so y=m1*x+b1=m2*x+b2

solve for X -
m1*x+b1=m2*x+b2
x=(b2-b1)/(m1-m2)
}
if m1<>m2 then
begin
x:=round((b2-b1)/(m1-m2));
if abs(m1) < abs(m2) then
y:=round(m1*x+b1) {try to get y intercept from smallest slope}
else y:=round(m2*x+b2); {but try the other equation}
{for intersection, x and y must lie between the endpoints of both lines}

if ( (line1.p1.x-x)*(x-line1.p2.x) >= 0 )
and ( (line1.p1.y-y)*(y-line1.p2.y) >= 0 )
and ( (line2.p1.x-x)*(x-line2.p2.x) >= 0 )
and ( (line2.p1.y-y)*(y-line2.p2.y) >= 0 )
then result:=true;
//* x,y is between x1,y1 and x2,y2 */
end
else if b1=b2 then {slopes and intercepts are equal}
begin {lines are colinear }
{if either end of line 1 is within the x and y range of line2, or
either end of line2 is with the x,y range of line1, then
then the lines overlap. For simplicity, we'll just call it an intersection}

with line1.p1 do result:=overlap(x,y, line2);
If not result then with line1.p2 do result:=overlap(x,y,Line2);
if not result then with line2.p1 do result:=overlap(x,y,line1);
if not result then with line2.p2 do result:=overlap(x,y,line1);
end;
{otherwise, slopes are equal and intercepts unequal
==> parallel lines ==> no intersection}
end;

Addendum: April 6, 2005:  The original of this program was posted 4 years ago and user Ian just found the first bug!   The intersection test code above checked if the X values of the intersection point lies with the line segment bounds.  We also need to check that the Y value for the intersection is within the bounds of both line segments.  A fixed version was posted today.

Addendum July 7, 2005:  One more bug - they're coming hot and heavy now!  Another viewer recently found that parallel line segments were not identified as intersecting even if they overlapped.    Now they are  identified correctly.

Addendum: December 29, 2005:  Still one more problem fixed thanks to sharp eyed viewer Lewie D. .  Co-linear line segments were called intersecting if either end of line segment 1  fell between the end points of line segment 2.  But i forgot about the case where  line segment 2 lies completely within line segment 1.  Today's change does the test both ways, line 1 overlapping line 2 or line 2 overlapping line1.   Function LinesIntersect has been moved into a common UGeometry unit which is now included our library unit  (DFFVLIBV04 or later).  For simplicity, it has also been included in the source code zip file for this program.

June 13, 2006:  Last month, a correction was made to the Overlap function in UGeometry used by this program and the unit was moved to our library zip file, DFFLIBV06.  But, the intersecting lines test now resides in the computational geometry program and I missed updating this page and the corresponding zip files to use the library version.  That was corrected today so you will have to do a one-time download of the latest library file to recompile this program.  See this page for more information about the library concept.      

Click here to download  the source for program IntersectLines which tests the function by letting you graphically define a pair of lines and telling you if they intersect.    You will need a one-time download of the library file DFFLIBV06 or later to recompile this program,  Download current DFF library file, DFFLibV11.

If you just want to help test it, click here to download the executable test program 

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2008, Gary Darby    All rights reserved.