Java - Proper line intersection check

Question

I need to determine whether two line segments intersect but there's a problem with using the line2D.linesIntersect method. The method returns a true result even if the lines only share an endpoint, like so:

Point2D.Double temp1 = new Point2D.Double(0, 0);
Point2D.Double temp2 = new Point2D.Double(0, 1);
Point2D.Double temp3 = new Point2D.Double(1, 0);

if(Line2D.linesIntersect(temp1.x, temp1.y, temp2.x, temp2.y, temp1.x, temp1.y, temp3.x, temp3.y){
    System.out.println("Lines share an endpoint.");
}
else{
    System.out.println("Lines don't intersect.");
}

In this case, I'll always get the "lines share an endpoint" message. Of course, in some instances where lines do share an endpoint, it is possible for them to intersect infinitely many times ((0,0) to (0,1) is intersected by (0,0) to (0,2)), and that should obviously return a true result. However, in other cases where only the endpoint is shared and no other intersection occurs, the program won't work correctly. Is there any way to prevent this problem?

Answer 1

I found a solution around the web and I have adapted it, tested manually. It's self-contained, just import java.awt.geom.Point2D

/**
 * Test if the first point lies in the bounding box denote by the other two
 * points.
 */
public static boolean isBetween(Point2D pToTest, Point2D p1, Point2D p2) {
    return isBetween(pToTest.getX(), pToTest.getY(), p1.getX(), p1.getY(), p2.getX(), p2.getY());
}

/**
 * Called {@link #isBetween(Point2D, Point2D, Point2D)} passing those points
 * coordinates.
 */
public static boolean isBetween(double pxToTest, double pyToTest, double px1, double py1, double px2, double py2) {
    double w, h;
    // taking inspiration from Rectangle's class
    w = px1 - px2;
    if (w < 0)
        w = -w;
    h = py1 - py2;
    if (h < 0)
        h = -h;
    // use p1 as the left-top corner of the rectangle
    // (the left-top corner is considered as the origin (0;0))
    if (px1 > px2)
        px1 = px2;//
    if (py1 > py2)
        py1 = py2;//
    if (pxToTest < px1 || pyToTest < py1) {
        return false;
    }
    w += px1;
    h += py1;
    // overflow || intersect
    return ((w < px1 || w > pxToTest) && (h < py1 || h > pyToTest));
}

public static double slope(double xa, double ya, double xb, double yb) {
    if (xb == xa)
        return Double.POSITIVE_INFINITY;
    return (yb == ya) ? 0.0 : ((yb - ya) / (xb - xa));
}

/**
 * Called by {@link #areLinesIntersecting(Point2D, Point2D, Point2D, Point2D)}
 * by providing each of those point's coordinates.
 */
public static Point2D areLinesIntersecting(double pxStart1, double pyStart1, double pxEnd1, double pyEnd1,
        double pxStart2, double pyStart2, double pxEnd2, double pyEnd2) {
    double slope_ab, slope_cd, numerator, denominator, q_ab, q_cd, x, y;
    Point2D p;
    slope_ab = slope(pxStart1, pyStart1, pxEnd1, pyEnd1);
    slope_cd = slope(pxStart2, pyStart2, pxEnd2, pyEnd2);
    q_ab = (pyStart1 - slope_ab * pxStart1);
    q_cd = (pyStart2 - slope_cd * pxStart2);
    if ((slope_ab == slope_cd) // parallel?
            && (
            // overlapping?
            ((slope_ab == Double.POSITIVE_INFINITY || slope_ab == Double.NaN) && pxStart1 == pxStart2) //
                    || //
                        // overlapping?
                    (slope_ab == 0.0 && pyStart1 == pyStart2) //
                    || //
                        // if different costant parts of lines, then parallel BUT not overlapping
                    (q_ab == q_cd)//
            )) {
        if (isBetween(pxStart2, pyStart2, pxStart1, pyStart1, pxEnd1, pyEnd1))
            return new Point2D.Double(pxStart2, pyStart2);
        if (isBetween(pxEnd2, pyEnd2, pxStart1, pyStart1, pxEnd1, pyEnd1))
            return new Point2D.Double(pxEnd2, pyEnd2);
        if (isBetween(pxStart1, pyStart1, pxStart2, pyStart2, pxEnd2, pyEnd2))
            return new Point2D.Double(pxStart1, pyStart1);
        if (isBetween(pxEnd1, pyEnd1, pxStart2, pyStart2, pxEnd2, pyEnd2))
            return new Point2D.Double(pxEnd1, pyEnd1);
    }
    if (slope_ab == Double.POSITIVE_INFINITY) {
        // ab vertical line: all a&b's x-es are equals
        x = pxStart1;
        y = (q_cd + (slope_cd * x));
        // it's a cross
        if ((pyStart1 <= pyEnd1) ? (y < pyStart1 || y > pyEnd1)
                // point are reversed
                : (y > pyStart1 || y < pyEnd1))
            return null;
        if ((pxStart2 < pxEnd2) ? (pxStart2 <= x && x <= pxEnd2)//
                : (pxEnd2 <= x && x <= pxStart2))
            return new Point2D.Double(x, y);
        else
            return null;
    }
    if (slope_cd == Double.POSITIVE_INFINITY) {
        // cd vertical line: all c&d's x-es are equals
        x = pxStart2;
        y = (q_ab + (slope_ab * x));
        // it's a cross
        if ((pyStart2 <= pyEnd2) ? (y < pyStart2 || y > pyEnd2)
                // point are reversed
                : (y > pyStart2 || y < pyEnd2))
            return null;
        // if the y lies inside the line a-b, then intersection
        if ((pxStart1 < pxEnd1) ? (pxStart1 <= x && x <= pxEnd1)//
                : (pxEnd1 <= x && x <= pxStart1))
            return new Point2D.Double(x, y);
        else
            return null;

    }
    // slopes cannot be infinity
    if (slope_ab == 0.0) {
        y = pyStart1;
        // slope_cd cannot be Infinity (second group of checks) and zero (first ones)
        x = (y - q_cd) / slope_cd;

        if ((pxStart1 <= pxEnd1) ? (x < pxStart1 || x > pxEnd1)
                // point are reversed
                : (x > pxStart1 || x < pxEnd1))
            return null;
        if ((pxStart2 <= pxEnd2) ? (x < pxStart2 || x > pxEnd2)
                // point are reversed
                : (x > pxStart2 || x < pxEnd2))
            return null;
        if ((pyStart2 < pyEnd2) ? (pyStart2 <= y && y <= pyEnd2)//
                : (pyEnd2 <= y && y <= pyStart2))
            return new Point2D.Double(x, y);
        else
            return null;
    }
    if (slope_cd == 0.0) {
        y = pyStart2;
        // slope_ab cannot be Infinity (second group of checks) and zero (first ones)
        x = (y - q_ab) / slope_ab;

        if ((pxStart2 <= pxEnd2) ? (x < pxStart2 || x > pxEnd2)
                // point are reversed
                : (x > pxStart2 || x < pxEnd2))
            return null;

        if ((pxStart1 <= pxEnd1) ? (x < pxStart1 || x > pxEnd1)
                // point are reversed
                : (x > pxStart1 || x < pxEnd1))
            return null;
        if ((pyStart1 < pyEnd1) ? (pyStart1 <= y && y <= pyEnd1)//
                : (pyEnd1 <= y && y <= pyStart1))
            return new Point2D.Double(x, y);
        else
            return null;
    }
    denominator = slope_cd - slope_ab;
    numerator = q_ab - q_cd;
    x = (numerator / denominator);
    y = (q_ab + (slope_ab * x));
    p = new Point2D.Double(x, y);
    if (isBetween(p.getX(), p.getY(), pxStart1, pyStart1, pxEnd1, pyEnd1)
            && isBetween(p.getX(), p.getY(), pxStart2, pyStart2, pxEnd2, pyEnd2))
        return p;
    y = (q_cd + (slope_cd * x));
    p = new Point2D.Double(x, y);
    if ((isBetween(p.getX(), p.getY(), pxStart1, pyStart1, pxEnd1, pyEnd1)
            && isBetween(p.getX(), p.getY(), pxStart2, pyStart2, pxEnd2, pyEnd2)))
        return p;

    return null;
}

Answer 2

If you are not restricted to your Point2D and Line2D objects you can use JTS (Java Topology Suite).

• Create your lines as LineString objects
• Use the intersects method

Simple code example:

LineString lineA = new GeometryFactory().createLineString(new Coordinate[]{new Coordinate(0, 0), new Coordinate(0, 10)});
LineString lineB = new GeometryFactory().createLineString(new Coordinate[]{new Coordinate(-5,5), new Coordinate(5,5)});
boolean intersect = lineA.intersects(lineB);

Answer 3

This is the answer I could come up with using my basic mathematics knowledge. Hope it helps you. Given 4 points, It tells you if two lines (from those four points) intersect, share an end point or neither one.

        //starting point of line 1
        Point2D.Double temp1 = new Point2D.Double(0 , 1);
        //ending point of line 1
        Point2D.Double temp2 = new Point2D.Double(0, -1);
        //starting point of line 2
        Point2D.Double temp3 = new Point2D.Double(-1, 0);
        //ending point of line 2
        Point2D.Double temp4 = new Point2D.Double(1, 0);

        //determine if the lines intersect
        boolean intersects = Line2D.linesIntersect(temp1.x, temp1.y, temp2.x, temp2.y, temp3.x, temp3.y, temp4.x, temp4.y);

        //determines if the lines share an endpoint
        boolean shareAnyPoint = shareAnyPoint(temp1, temp2, temp3, temp4);

        if (intersects && shareAnyPoint) {
            System.out.println("Lines share an endpoint.");
        } else if (intersects && !shareAnyPoint) {
            System.out.println("Lines intersect.");
        } else {
            System.out.println("Lines neither intersect nor share a share an endpoint.");
        }

Here is the shareAnyPoint(StartPointA, EndPointA, StartPointB, EndPointB) function that checks if start/end points from either lines lies on the other line.

public static boolean shareAnyPoint(Point2D.Double A, Point2D.Double B, Point2D.Double C, Point2D.Double D) {
    if (isPointOnTheLine(A, B, C)) return true;
    else if (isPointOnTheLine(A, B, D)) return true;
    else if (isPointOnTheLine(C, D, A)) return true;
    else if (isPointOnTheLine(C, D, B)) return true;
    else return false;
}

And here is the isPointOnTheLine(StartPoint, EndPoint, MyPoint) function that determines if a point lies on line (made by 2 other points)

public static boolean isPointOnTheLine(Point2D.Double A, Point2D.Double B, Point2D.Double P) {  
    double m = (B.y - A.y) / (B.x - A.x);

    //handle special case where the line is vertical
    if (Double.isInfinite(m)) {
        if(A.x == P.x) return true;
        else return false;
    }

    if ((P.y - A.y) == m * (P.x - A.x)) return true;
    else return false;
}

Give it a try and let me know about the results.