Line Segment Intersection

We want to determine if two line segments, $s_1$ and $s_2$ , intersect and if they do intersect, the point of intersection. First we analyze the problem. Case five in the list below is difficult to analyze which is why we leave it to the end.

The segments are not parallel (easy)
The segments are parallel and do not intersect (easy)
The segments are collinear and do not intersect (easy)
The segments are collinear and do intersect (easy)
The segments are nearly parallel or nearly collinear (hard)

In this post I handle cases one through four. I leave case five for later posts.

For the problem setup let segment 1 be given by

$s_1 = p + t \cdot r$ where $0 <= t <= 1$ and p, r are 2d vectors, similarly let segment 2 be given by

$s_2 = q + u \cdot s$ where $0 <= u <= 1$ and q, s are 2d vectors.

This representation of the line segments yields a very natural method for computing their intersection.

Computing cross products is the heart of the algorithm for determining intersections. The two dimensional cross product of $p_1 \times p_2$ is given by

$\textrm{det} \left( \begin{array} {cc} x_1 & x_2 \\ y_1 & y_2\end{array} \right) = x_1y_2 - x_2y_1 = -p_2 \times p_1$

If the cross product is zero then the two vectors are collinear that is pointing in either the same direction or in opposite directions.

The two lines intersect when $p + t \cdot r = q + u \cdot s$ , by crossing both sides with $s$ we get

$(p + t \cdot r) \times s = (q + u \cdot s) \times s = q \times s + u \cdot s \times s = q \times s.$

From this we solve for $t$ obtaining

$t = \frac{(q - p) \times s}{r \times s}.$

We can similarly solve for $u$ , obtaining

$u = \frac{(q -p) \times r}{r \times s}.$

If both t and u are between 0 and 1, then the two line segments intersect and the intersection point is given by $p + t \cdot r,$ where the value of t is the one we solved for. If either t or u are not between 0 and 1 then the line segments do not intersect.

But suppose $r \times s = 0$ , then we can’t solve for t and u. This is because $r \times s = 0$ means that r and s are parallel which means the two line segments are parallel. Please also note that $r \times s = 0$ implies that $r$ and $s$ are scalar multiplies of each other. If $(p -q) \times r \not= 0$ then the segments are parallel but not collinear hence they do not intersect. If $(p -q) \times r = 0$ then the segments are collinear and we can simply project both of them onto to x-axis and determine if their projections intersect.

For case 5 when $r \times s$ is close to zero the analysis needs to be well thought out and I’ll leave it to future posts.

I’ve posted a sample implementation in Javascript using the html5 canvas at http://cloud.github.com/downloads/bjwbell/canvas-geolib/main.html (please note it won’t work in internet explorer since it doesn’t support the canvas element).

Credit Gareth Rees for his post at stackoverflow.com which is based on the method for 3D line intersection algorithm from the article “Intersection of two lines in three-space” by Ronald Graham, published in Graphics Gems, page 304.

About these ads

11 thoughts on “Line Segment Intersection”

Well done demonstration! Just what I was looking for when I searched “javascript intersect lines”. My problem is simple: given a line set and a box return a new line set where each member line falls inside the box. Your “intersect” function works well and provides a good example for using Javascript objects. Thanks!

Bryan Bell

June 4, 2009 at 4:56 am

Thank you for the compliment

Reply

You have

(P + t . R) x S = Q x S

… solve for t ….

t = ((P – Q) x S) / (R x S)

But wouldn’t it be…

t = ((Q – P) x S) / (R x S)

Specifically…
(P + t . R) x S = Q x S
PxS + t(RxS) = QxS
t(RxS) = QxS – PxS
t = ((Q-P)xS) / (RxS)

Am I doing something wrong there? (I’m rusty, hence my visit to this site. )

No you’re correct it’s a typo. I’ve updated the post.

You have to project both onto X and Y axes, X alone is not enough.

Pingback: 2010 in review « Math and More

Well done, and very useful. I noticed in the JS example, your function never returns either of the two collinear constants, COLINEAR_DONT_INTERSECT and COLINEAR_INTERSECT. I was wondering how you would work those in there.

Bryan Bell

September 12, 2012 at 9:41 am

Hi Bradley, to use the COLINEAR_DONT_INTERSECT and COLINEAR_INTERSECT you need to expand the if check @
” if(rCrossS = -1 * epsilon){
return PARALLEL_DONT_INTERSECT;
}”

Replace the statement “return PARALLEL_DONT_INTERSECT” with the following pseudo code
“if (cross(p-q, r) -epsilon){
// the segments are colinear, you need to check if they intersect or not and return COLINEAR_INTERSECT or COLINEAR_DONT_INTERSECT, respectively.
}else{
return PARALLEL_DONT_INTERSECT
}”.

Hope that helps.

Reply

Pingback: Contest | aandrew99

Pingback: Contest 23/3/2013 | aandrew99

Math and More

Problem solving at its best

Line Segment Intersection

11 thoughts on “Line Segment Intersection”

Leave a Reply Cancel reply

Follow “Math and More”

Share this:

Like this:

11 thoughts on “Line Segment Intersection”

Leave a Reply Cancel reply

Follow “Math and More”