2010-06-11

How to determine if two line segments intersect (in 2D)?

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:

Tommy said...

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.

Petar said...

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?

pts said...
This comment has been removed by the author.
pts said...

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

PavanJJ said...

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

PavanJJ said...

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

telengard said...

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

pts said...

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

ma3at said...

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

Md. Ezharul said...

Thanks ..

3M said...

Worked like a charm

MB said...

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

MB said...
This comment has been removed by a blog administrator.
pts said...

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