This blog post gives the C++ implementation of the fast schoolbook algorithm for determining if two (finite) line segments on a 2D plane intersect (cross).

static bool IsOnSegment(double xi, double yi, double xj, double yj, double xk, double yk) { return (xi <= xk || xj <= xk) && (xk <= xi || xk <= xj) && (yi <= yk || yj <= yk) && (yk <= yi || yk <= yj); } static char ComputeDirection(double xi, double yi, double xj, double yj, double xk, double yk) { double a = (xk - xi) * (yj - yi); double b = (xj - xi) * (yk - yi); return a < b ? -1 : a > b ? 1 : 0; } /** Do line segments (x1, y1)--(x2, y2) and (x3, y3)--(x4, y4) intersect? */ bool DoLineSegmentsIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) { char d1 = ComputeDirection(x3, y3, x4, y4, x1, y1); char d2 = ComputeDirection(x3, y3, x4, y4, x2, y2); char d3 = ComputeDirection(x1, y1, x2, y2, x3, y3); char d4 = ComputeDirection(x1, y1, x2, y2, x4, y4); return (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) || (d1 == 0 && IsOnSegment(x3, y3, x4, y4, x1, y1)) || (d2 == 0 && IsOnSegment(x3, y3, x4, y4, x2, y2)) || (d3 == 0 && IsOnSegment(x1, y1, x2, y2, x3, y3)) || (d4 == 0 && IsOnSegment(x1, y1, x2, y2, x4, y4)); }

The algorithm above does 8 multiplications, 16 subtractions and 52 comparisons in the worst case. But it doesn't do any divisions or square roots. If the input coordinates are integers, and the multiplications and subtractions don't yield an overflow, then the whole algorithm can be performed only with integer arithmetic.

The algorithm above doesn't return the coordinates of the intersection point. To find the intersection point of two intersecting line segments, see the formula on http://en.wikipedia.org/wiki/Line-line_intersection.

If there are many line segments and we are interested in all intersections, calling the above algorithm for all pairs is slow (quadratic). See faster algorithms (O(n*log(n))) on http://en.wikipedia.org/wiki/Line_segment_intersection

## 14 comments:

Thanks for this! It really helped me out. An explanation of what makes this black magic work would be great, but I'm just glad that it actually does work.

Something is wrong here.

As a result i get that lines (6,4,0,0) and (1,1,6,4) intersect where line (0,0,6,4) and (1,1,6,4) do not.

Any thoughts?

@Petar: Thank you for the test case. There used to be a typo in IsOnSegment. I've just fixed it, now it's working as expected: line segments (6,4)--(0,0) and (1,1)--(6,4) intersect, and line segments (0,0)--(6,4) and (1,1)--(6,4) also intersect.

Dude....

Thanx a lot ... it works like magic !!! no hassles involved . . . thanx man

Thanks a lot man .... you made my day .... it works like magic!!!!

Does this handle the case of the line segments overlapping? i.e. same slope and y intercept.

@telengrad: Yes, it works in that case too. The function returns true iff there is a point which is on both line segments.

Hi. thnx for your algorithm.

This is the implementation for the wikipedia algorithm

http://en.wikipedia.org/wiki/Line-line_intersection

But this is for the (infinite) line segments, not the finite one

It says so explicitly on wikipedia

regards

Thanks ..

Worked like a charm

What is the mathematical formula or reference in which this algorithm is based?

Thanks.

@MB: I've read the algorithm in a school textbook.

Post a Comment