Trying to figure out if two line segments intersect

Question

I have a line segment made of two points p1 and p2, and a second line segment made up of points p3 and p4. I'm trying to figure out if they intersect, and so far, I have had no luck. This is my code so far:

public static double angle(Point p1, Point p2, Point p3) {
    double AB = length(p2, p1);
    double BC = length(p2, p3);
    double AC = length(p3, p1);
    return Math.acos((sqr(BC) + sqr(AB) - sqr(AC)) / (2 * BC * AB)) * (180 / Math.PI);
}

public static boolean doIntersect(Point p1, Point p2, Point p3, Point p4) {
    double a = angle(p4, p3, p2);
    double b = angle(p3, p2, p1);
    double c = 180 - b - a;

    System.out.println("a: " + a + ", b: " + b + ", c:" + c);

    if((length(p3, p2) * Math.sin(a)) / Math.sin(c) > length(p2, p1)) return false;
    if((length(p3, p2) * Math.sin(b)) / Math.sin(c) > length(p3, p4)) return false;
    return true;
}

public static double length(Point point1, Point point2) {
    return Math.sqrt(sqr(point1.x - point2.x) + sqr(point1.y - point2.y));
}

public static double sqr(double doub) {
    return Math.pow(doub, 2);
}

But this isn't working. Sometimes, the angle "c" even comes out as negative numbers.

Also, Point is a custom class with two parameters: x and y. Should be fairly self-explanatory.

Answer 1

I would suggest to put up a mathematical solution first, validate it and then try to migrate it to a computer program.

Answer 2

There are two solutions, each with its own advantages:

1. Mathematical Solution

From two points p1 and p2, one can easily derive a formula y = m*x + b for the line that crosses those two points. With formulas for the lines defined by (p1, p2) and (p3, p4), it's again easy to compute their intersection by equalization. All that's left to do is check whether the intersection point is part of both line segments, which is fairly obvious.

2. Algorithmic Solution

Another approach is to apply a sweep line algorithm: Sort all points by their respective x-coordinate. Then for each point in x-order, imagine a vertical line that hops from point to point.

If you reach the first point from line segment B after you visited all points from line segment A, there is no intersection.

Otherwise your first point is from line segment A and your second point is from line segment B. Hence your third and fourth point belong to A and B or to B and A respectively. Focus your attention on the y-coordinates and solve the very last part of this solution on your own. ;-)

EDIT: or simpler yet, ask Wikipedia on line segment intersection.

Answer 3

For angle calculations, instead of using a complicated method where you sum up squares of x and y differences, then take the square root of the sum, then square that value, and then use acos, one can use atan2 which computes an angle in proper quadrant from x and y differences. This is faster and less problematic than the acos method.

However, there's no real need to compute any angles at all. Instead, first test if overlap is infeasible. That is, return No if ((x₁≤x₃≤x₂ || x₁≤x₄≤x₂ || x₃≤x₁≤x₄ || x₃≤x₂≤x₄) && (y≤y₃≤y₂ || y₁≤y₄≤y₂ || y₃≤y₁≤y₄ || y₃≤y₂≤y₄)) is false. (Let p₁,p₂ be endpoints of one segment, and p₃,p₄ endpoints of the other.)

If the case isn't infeasible, you then can test whether an intersection occurs by seeing if the signs of the areas of the triangles p₁,p₂,p₃ and p₁,p₂,p₄ are different. The area of p₁,p₂,p₃ is ±(x₁·y₂-x₂·y₁ + x₃·(y₂-y₁) + y₃·(x₂-x₁))/2, and the factor of 1/2 can be ignored since it doesn't affect sign. That is, for feasible cases you can compute
t = x₁·y₂-x₂·y₁
u = t + x₃·(y₂-y₁) + y₃·(x₂-x₁)
v = t + x₄·(y₂-y₁) + y₄·(x₂-x₁)
and return Yes if u·v ≤ 0, else No. The point of using a method like this is to avoid having to check all the special cases that arise with vertical or horizontal lines, parallel or coincident lines, etc. If you expect degenerate lines to occur, report Yes if u·v < 0, or No if u·v > 0, else test if one line has an endpoint on the other line.