CODEWITHSUNDEEP
javaalgorithmgeometry
Out Of Bounds
Out Of Bounds

Reputation: 185

How to find if two line segments intersect or not in Java?

I need to implement a method called disjointSegments that returns true if line segments are disjoint and false otherwise.

That's what I have until now. There should be 2 segments, ab and cd.

public static boolean disjointSegments(Point2D.Double a, Point2D.Double b,
        Point2D.Double c, Point2D.Double d)

This is an assignment and it says that I could figure it out by using delta method, which is a method that computes the determinant of a matrix.

API

API

I already implemented the delta method.

public static double delta(Point2D.Double a, Point2D.Double b,
        Point2D.Double c) {
    return (a.getX() * b.getY() * 1) + ( a.getY() * 1 * c.getX()) + (1 * b.getX() * c.getY()) - (1 * b.getY() * c.getX())
            - (a.getX() * 1 * c.getY()) - (a.getX() * b.getY() * 1);
}

So How could I figure out if the line segments are disjoint or not ?

Upvotes: 3

Views: 10024

Answers (3)

MasterHD
MasterHD

Reputation: 2384

Since you only need a true/false result in 2D space, there's an efficient way to compute this:

bool segmentsIntersect(Point2D a, Point2D b, Point2D c, Point2D d) {
    float det = (b.x - a.x) * (d.y - c.y) - (d.x - c.x) * (b.y - a.y);
    if (det == 0)
        return false; //Lines are parallel
    float lambda = ((d.y - c.y) * (d.x - a.x) + (c.x - d.x) * (d.y - a.y)) / det;
    float gamma = ((a.y - b.y) * (d.x - a.x) + (b.x - a.x) * (d.y - a.y)) / det;
    return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);
}

Upvotes: 0

Steve Benett
Steve Benett

Reputation: 12933

The function delta is an implementation of the cross product. This can be used to determine if points or vectors are clockwise or counterclockwise to each other. Two vectors are clockwise if ab x cd > 0, counterclockwise if ab x cd < 0 and they are collinear if ab x cd = 0.

To use this to determine that two vectors intersect you can do the following:

Assume you have 4 points: a, b, c, d. Then you need to do 4 calculations:

(a - c) x (d - c) < 0
(b - c) x (d - c) > 0

With these 2 calculations you can determine if point a is counterclockwise and b is clockwise (or vice versa) to the vector cd. If this holds, the points are on different sides of the vector and this is what you need to have an intersection between them. Now you have to test d and c for the same.

(d - a) x (b - a) < 0
(c - a) x (b - a) > 0

If this also holds your two vectors intersect.

Edit: If all 4 calculations in this example are true, then there is an intersection of the vectors. This is true for the disjoint examples in your question, where no point is collinear with a vector. If you have to test this also then a collinear test is necessary.

The term a - c makes a vector out of two points. 

a - c => ac.x = a.x - c.x, ac.y = a.y - c.y

Upvotes: 1

Kzhunter
Kzhunter

Reputation: 627

Here's a solution for the General Case. See this-page 9 for special cases.

public static int orientation(Point p, Point q, Point r) {
    double val = (q.getY() - p.getY()) * (r.getX() - q.getX())
            - (q.getX() - p.getX()) * (r.getY() - q.getY());

    if (val == 0.0)
        return 0; // colinear
    return (val > 0) ? 1 : 2; // clock or counterclock wise
}

public static boolean intersect(Point p1, Point q1, Point p2, Point q2) {

    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    if (o1 != o2 && o3 != o4)
        return true;

    return false;
}

public static void main(String[] args) {
    Point p1 = new Point(1,1);
    Point q1 = new Point(2,0);
    Point p2 = new Point(1,0);      
    Point q2 = new Point(3,2);      
    System.out.println("intersect: "+intersect(p1, q1, p2, q2));
}

Answer: intersect: true

Upvotes: 4

Related Questions