Martin Thoma

You have to line segments and you want to know if they intersect. I’ll give you an algorithm how to do it.

Test cases

First of all, we should think about how lines can be arranged:

Bounding boxes

You can draw boxes around line segments such that the edges of the boxes are in parallel to the coordinate axes:

Two line segments with their bounding boxes

With this image in mind, it is obvious that the bounding boxes need to intersect if the lines should intersect. At this point you have to make a decision: If the endpoint of one line is on the other line, is this an intersection? I think so. If two lines have at least one point in common, they intersect. If two bounding boxes have at least one point in common, they intersect.

It is much easier to check if two bounding boxes intersect. It’s simply:

/**
 * Check if bounding boxes do intersect. If one bounding box
 * touches the other, they do intersect.
 * @param a first bounding box
 * @param b second bounding box
 * @return <code>true</code> if they intersect,
 *         <code>false</code> otherwise.
 */
public boolean doBoundingBoxesIntersect(Point[] a, Point[] b) {
    return a[0].x <= b[1].x 
        && a[1].x >= b[0].x 
        && a[0].y <= b[1].y
        && a[1].y >= b[0].y;
}

If you have difficulties to understand why this works, take a look at this great animation for this formula.

The algorithm

Flowchart how to check if two lines intersect

Looks quite simple, doesn’t it?

Cross product

Well, you might notice that you need to check if one line intersects with a given line segment. To check this, you have to understand one cool idea:

You can definie a cross product for points:
\(\begin{align}
\times_P&: Point \times Point \rightarrow \mathbb{R}\\
\times_P(a, b) &:= a.x \cdot b.y – b.x \cdot a.y;
\end{align}\)

This cross product has one nice characteristics:
\(a \times_P b = 0 \Leftrightarrow a\) and \(b\) are on one line through origin

You can verify this. If you take two points on a line through origin, they have the same slope \(\frac{\Delta y}{\Delta x}\):
\(
\begin{align}
0 &= a \times_P b\\
\Leftrightarrow 0 &= a.x \cdot b.y – b.x \cdot a.y\\
\Leftrightarrow b.x \cdot a.y &= a.x \cdot b.y\\
\Leftrightarrow \frac{a.y}{a.x} &= \frac{b.y}{b.x}
\end{align}
\)

Ok, now you can check if a point is on a line:

    /**
     * Checks if a Point is on a line
     * @param a line (interpreted as line, although given as line
     *                segment)
     * @param b point
     * @return <code>true</code> if point is on line, otherwise
     *         <code>false</code>
     */
    public boolean isPointOnLine(LineSegment a, Point b) {
        // Move the image, so that a.first is on (0|0)
        LineSegment aTmp = new LineSegment(new Point(0, 0), new Point(
                a.second.x - a.first.x, a.second.y - a.first.y));
        Point bTmp = new Point(b.x - a.first.x, b.y - a.first.y);
        double r = crossProduct(aTmp.second, bTmp);
        return Math.abs(r) < EPSILON;
    }

The second cool characteristic of the cross product is that it can be used to determine if a point b is left or right of the line through the origin and a point a:

    /**
     * Checks if a point is right of a line. If the point is on the
     * line, it is not right of the line.
     * @param a line segment interpreted as a line
     * @param b the point
     * @return <code>true</code> if the point is right of the line,
     *         <code>false</code> otherwise
     */
    public boolean isPointRightOfLine(LineSegment a, Point b) {
        // Move the image, so that a.first is on (0|0)
        LineSegment aTmp = new LineSegment(new Point(0, 0), new Point(
                a.second.x - a.first.x, a.second.y - a.first.y));
        Point bTmp = new Point(b.x - a.first.x, b.y - a.first.y);
        return crossProduct(aTmp.second, bTmp) < 0;
    }

When we have one line \(a\) through the origin and one line segment \(b\), you can check if \(b\) crosses \(a\) by checking if the end points of \(b\) are on different sides of \(a\):

    /**
     * Check if line segment first touches or crosses the line that is 
     * defined by line segment second.
     *
     * @param first line segment interpreted as line
     * @param second line segment
     * @return <code>true</code> if line segment first touches or
     *                           crosses line second,
     *         <code>false</code> otherwise.
     */
    public boolean lineSegmentTouchesOrCrossesLine(LineSegment a,
            LineSegment b) {
        return isPointOnLine(a, b.first)
                || isPointOnLine(a, b.second)
                || (isPointRightOfLine(a, b.first) ^ 
                    isPointRightOfLine(a, b.second));
    }

Now you have everything you need:

    /**
     * Check if line segments intersect
     * @param a first line segment
     * @param b second line segment
     * @return <code>true</code> if lines do intersect,
     *         <code>false</code> otherwise
     */
    public boolean doLinesIntersect(LineSegment a, LineSegment b) {
        Point[] box1 = a.getBoundingBox();
        Point[] box2 = b.getBoundingBox();
        return doBoundingBoxesIntersect(box1, box2)
                && lineSegmentTouchesOrCrossesLine(a, b)
                && lineSegmentTouchesOrCrossesLine(b, a);
    }

By the way, testcase F5 is the only reason why you need doBoundingBoxesIntersect(box1, box2). All other tests still pass if you remove this function.

Where do two line segments intersect?

Assume you know that two line segments intersect, none of them is parallel to the y-axis and they only have one point in common. When you want to know where those two line segments intersect, you can apply some math:

Every point \((x | y)\) on a line that is not parallel to the y-axis can get expressed with this formula:
\(y = m \cdot x + t, \;~~~ m, t \in \mathbb{R}\)
where \(m\) and \(t\) are constants.

How do you calculate those, when you only have the starting point \((x_{1,s}|y_{1,s}), (x_{2,s}|y_{2,s})\) and end points \((x_{1,e}|y_{1,e}), (x_{2,e}|y_{2,e})\) of both line segments?

Now you can use the starting point or the endpoint to get \(t\):
\(t_1 = y – m_1 \cdot x = y – \frac{y_{1,s}-y_{1,e}}{x_{1,s}-x_{1,e}} \cdot x = y_{1,s} – \frac{y_{1,s}-y_{1,e}}{x_{1,s}-x_{1,e}} \cdot x_{1,s}\)

Now your equation looks like this:
\(y = \frac{y_{1,s}-y_{1,e}}{x_{1,s}-x_{1,e}} \cdot x + (y_{1,s} – \frac{y_{1,s}-y_{1,e}}{x_{1,s}-x_{1,e}} \cdot x_{1,s})\)

Now you can get one big equation and solve for \(x\). This \(x\) will be the point where both lines intersect:

Doesn’t look very nice, does it? Additionally, you have to watch out if you divide by 0.

TL;DR

The complete, tested code is on GitHub. Here is the most important part:

public class Geometry {

    public static final double EPSILON = 0.000001;

    /**
     * Calculate the cross product of two points.
     * @param a first point
     * @param b second point
     * @return the value of the cross product
     */
    public static double crossProduct(Point a, Point b) {
        return a.x * b.y - b.x * a.y;
    }

    /**
     * Check if bounding boxes do intersect. If one bounding box
     * touches the other, they do intersect.
     * @param a first bounding box
     * @param b second bounding box
     * @return <code>true</code> if they intersect,
     *         <code>false</code> otherwise.
     */
    public static boolean doBoundingBoxesIntersect(Point[] a, Point[] b) {
        return a[0].x <= b[1].x && a[1].x >= b[0].x && a[0].y <= b[1].y
                && a[1].y >= b[0].y;
    }

    /**
     * Checks if a Point is on a line
     * @param a line (interpreted as line, although given as line
     *                segment)
     * @param b point
     * @return <code>true</code> if point is on line, otherwise
     *         <code>false</code>
     */
    public static boolean isPointOnLine(LineSegment a, Point b) {
        // Move the image, so that a.first is on (0|0)
        LineSegment aTmp = new LineSegment(new Point(0, 0), new Point(
                a.second.x - a.first.x, a.second.y - a.first.y));
        Point bTmp = new Point(b.x - a.first.x, b.y - a.first.y);
        double r = crossProduct(aTmp.second, bTmp);
        return Math.abs(r) < EPSILON;
    }

    /**
     * Checks if a point is right of a line. If the point is on the
     * line, it is not right of the line.
     * @param a line segment interpreted as a line
     * @param b the point
     * @return <code>true</code> if the point is right of the line,
     *         <code>false</code> otherwise
     */
    public static boolean isPointRightOfLine(LineSegment a, Point b) {
        // Move the image, so that a.first is on (0|0)
        LineSegment aTmp = new LineSegment(new Point(0, 0), new Point(
                a.second.x - a.first.x, a.second.y - a.first.y));
        Point bTmp = new Point(b.x - a.first.x, b.y - a.first.y);
        return crossProduct(aTmp.second, bTmp) < 0;
    }

    /**
     * Check if line segment first touches or crosses the line that is
     * defined by line segment second.
     *
     * @param first line segment interpreted as line
     * @param second line segment
     * @return <code>true</code> if line segment first touches or
     *                           crosses line second,
     *         <code>false</code> otherwise.
     */
    public static boolean lineSegmentTouchesOrCrossesLine(LineSegment a,
            LineSegment b) {
        return isPointOnLine(a, b.first)
                || isPointOnLine(a, b.second)
                || (isPointRightOfLine(a, b.first) ^ isPointRightOfLine(a,
                        b.second));
    }

    /**
     * Check if line segments intersect
     * @param a first line segment
     * @param b second line segment
     * @return <code>true</code> if lines do intersect,
     *         <code>false</code> otherwise
     */
    public static boolean doLinesIntersect(LineSegment a, LineSegment b) {
        Point[] box1 = a.getBoundingBox();
        Point[] box2 = b.getBoundingBox();
        return doBoundingBoxesIntersect(box1, box2)
                && lineSegmentTouchesOrCrossesLine(a, b)
                && lineSegmentTouchesOrCrossesLine(b, a);
    }
}

Addendum

Some notes for me:

• Writing Tests first is worth the effort. I guess it finally saved me some time and it gives me some confidence that my code works.
• I should update my system. I’m still using Ubuntu 10.04.4 LTS. Especially, I have Eclipse 3.5.2. This means I could not try EclEmma to test my code coverage
• LaTeX is great. I’ve created all images with LaTeX and it was quite fast after I got the first one. Here is the LaTeX source.

edit:
I now have a more modern system. So I was able to use EclEmma, which works fine. And I have 100% branch code coverage for this part of code