[Home]   [Puzzles & 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 (uncorrected).

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.

Addendum 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.      

Addendum August 2, 2008:  One more case was fixed today where non-intersecting lines were classified as intersecting.   In the previous update I had switched to an "improved" line intersection test function (Intersect) which turned out to have the bug when a vertical line segment shared the X coordinate with one end of the other line but did not intersect it.  I switched back to the older version (LineIntersect) as described above.   The bug in Intersect has been corrected and another newly discovered in LineIntersect  has also been fixed.  Both functions are part of the UGeometry unit which has been reposted in the DFFLibV11 library zip file.   The only known difference between the two now is that LinesIntersect rounds to integer pixel values to decide if two lines intersect, Intersect does not .  So end points of one line lying within 1/2 pixel short of the other line will be classified differently.

Other enhancements to the test program were made primarily to help in testing.  They include:

Addendum August 6, 2008:  Hopefully this is last  update for a long time.   The original "Intersect" routine in our Computation Geometry unit was converted from somewhere.  It's the one that uses unexplained Sameside routine to determine if two end points of either line fall on opposite sides of the other.  It has always worked for most cases but never for all.  I have spent days checking and rechecking the code without correcting the problem.  For that reason, the "LinesIntersect" function was written using slope/intercept ideas was written for this program.  After the latest update, I finally gave up on fixing "Intersect" and converted it call another Intersect routine found in a free source FastGeo unit found at  http://www.partow.net/projects/fastgeo/index.html written by Arash Partow.  FastGeo is an excellent,  comprehensive, computational geometry library that will be the first place I'll check in the future when I have problems of this type.    My Intersect function now calls FastGeoIntersect xtract from the FastGeo library.  Version 3 of IntersectLines  now has a button to generate 1,000,000 random line pairs and call both LinesIntersect and Intersect functions to compare results.  For the first time, they now agree.   The tested functions reside in unit UGeometry in DFFLibV11 which was reposted today, so must be re-downloaded if you want to compile the program.    

Addendum December 3, 2008:  Ok, one more small update, but only to the the test program this time, not the intersect procedures.  Version 3.1 posted today fixes a problem that limited the displayed line end value to 500 pixels.  I also added a button to clear the displayed list of line pairs that had been tested.

Download Programs

Click here to download  source code for 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 DFFLIBV11 or later to recompile this program,  Download current DFF library file, DFFLibV15.

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

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

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