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