[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 (x1,y1) and (x2,y2), we can determine m and b as follows. From its definition, m = change in y divided by change in x = (y2-y1)/(x2-x1). And since b=y-mx for any point on the line, we can compute b1=y1-mx1. With two line segments, we can derive an equation for each, say y=m1x+b1 and y=m2x+b2. The x and y values at the intersection point must satisfy both, so y = m1x+b1=m2x+b2. If we take the last half of this and solve for x, we get m1x+b1=m2x+b2, or (m1-m2)x=b2-b1 or x=(b2-b1)/(m1-m2). Notice that when m1 equals m2, 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;
var
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. |