Java - Find Intersection between Lines

Tạo phương trình đường thẳng từ đoạn thẳng

Ta có hai điểm A(x1,y1) và B(x2,y2) tạo thành một đoạn thẳng, để tạo được một phương trình đường thẳng từ hai điểm này, ta cần tính được độ nghiêng của đường thẳng (slope) theo công thức:

a = (y2 – y1)/(x2 – x1)

Thay thế x2, y2 bằng hai biến x,y:

a = (y – y1)/(x – x1)
=> y – y1 = a(x – x1)

Hay:
y = ax + (y1 – ax1)
Đặt b = y1 – ax1, ta có:

y = ax + b

Tính giao điểm của hai đường thẳng

Ta có hai phương trình đường thẳng

(1): y = a1x + b1
(2): y = a2x + b2

Ta có thể tính được giao điểm của chúng bằng cách tìm giao điểm x trước:

a1x + b1 = a2x + b2;

=> x(a1 – a2) = b2 – b1
=> x = (b2 – b1)/(a1 – a2)

Khi đã có x, ta sẽ thế vào (1) hoặc (2) để tính được y.
Để kiểm tra hai đoạn thẳng có cắt nhau không, ta chỉ cần kiểm tra điểm {x,y} thuộc cả hai đoạn thẳng hay không.
Ngoài ra ta cần loại trừ trường hợp hai đường thẳng song song hoặc trùng nhau, khi đó giá trị slope của chúng sẽ bằng nhau.

Point Class

import java.util.List;
import static java.lang.Math.sqrt;
class Point {
    // Coordinates of the point
    double x;
    double y;

    public Point() {
    }
    // Create a point from coordinates
    Point(double xVal, double yVal) {
        x = xVal;
        y = yVal;
    }
    // Create a point from another Point object
    Point(final Point oldPoint) {
        x = oldPoint.x; // Copy x coordinate
        y = oldPoint.y; // Copy y coordinate
    }
    // Move a point
    void move(double xDelta, double yDelta) {
        // Parameter values are increments to the current coordinates
        x += xDelta;
        y += yDelta;
    }
    // Calculate the distance to another point
    double distance(final Point aPoint) {
        return sqrt((x - aPoint.x)*(x - aPoint.x) + (y - aPoint.y)*(y - aPoint.y));
    }

    //Returns sqrt(x2 +y2) without intermediate overflow or underflow.
    public double distanceSqrt(Point p) {
        return Math.hypot(this.x - p.x, this.y - p.y);
    }

    // Convert a point to a string
    public String toString() {
        return Double.toString(x) + "," + y; // As “x, y”
    }

    //get closest point
    public Point getClosestPoint(List<Point> pts) {
        double minDistSoFar = Double.MAX_VALUE;
        Point rval = null;

        for (Point p : pts) {
            if (p.x == this.x && p.y == this.y) {
                continue;
            }

            double pDist = this.distance(p);
            if (pDist < minDistSoFar) {
                minDistSoFar = pDist;
                rval = p;
            }
        }
        return rval;
    }

    @Deprecated
    //get intersection Points
    public Point getIntersectionPoint(List<Point> listPoints)
    {
        Point minPoint = null;
        for(int i = 0; i<listPoints.size(); i++)
        {
            Point point = listPoints.get(i);
            minPoint = listPoints.get((i+1) % listPoints.size());
            double minXDistance = minPoint.x-point.x;
            double minYDistance = minPoint.y-point.y;
            double minDist = Math.hypot(minXDistance, minYDistance);

            for(int j = 0; j < listPoints.size(); j++)
            {
                if (i == j) {
                    continue;
                }

                Point testPt = listPoints.get(j);
                double dist = Math.hypot(point.x - testPt.x, point.y - testPt.y);
                if (dist < minDist)
                {
                    minDist = dist;
                    minPoint = testPt;
                }
            }
        }
        System.out.println("minPoint:"+minPoint.x+"\t"+minPoint.y);
        return minPoint;
    }
}

Line Class

class Line {
    Point start; // Start point of line
    Point end; // End point of line

    // Create a line from two points
    Line(final Point start, final Point end) {
        this.start = new Point(start);
        this.end = new Point(end);
    }

    // Create a line from two coordinate pairs
    Line(double xStart, double yStart, double xEnd, double yEnd) {
        start = new Point(xStart, yStart); // Create the start point
        end = new Point(xEnd, yEnd); // Create the end point
    }

    // Calculate the length of a line
    double length() {
        return start.distance(end);
    }

    // Convert a line to a string
    public String toString() {
        return "(" + start+ "):(" + end + ")";
    }


    // Case 1: Return a point as the intersection of two lines
    Point intersects(final Line line1) {
        Point localPoint = new Point(0, 0);
        double num = (this.end.y - this.start.y)*(this.start.x - line1.start.x) -(this.end.x - this.start.x)*(this.start.y - line1.start.y);
        double denom = (this.end.y - this.start.y)*(line1.end.x - line1.start.x) -(this.end.x - this.start.x)*(line1.end.y - line1.start.y);
        localPoint.x = line1.start.x + (line1.end.x - line1.start.x)*num/denom;
        localPoint.y = line1.start.y + (line1.end.y - line1.start.y)*num/denom;
        return localPoint;
    }

    // Case 2: Return a point as the intersection of two lines
    public Point getIntersect(Line line1, Line line2){
        //double slope = (line1.end.y-line1.start.y)/(line1.end.x-line1.start.x);
        Point X = new Point(0,0);
       
        double a1 = (line1.end.y-line1.start.y)/(line1.end.x-line1.start.x);
        double b1 = line1.end.y - a1*line1.end.x;
       
        double a2 = (line2.end.y- line2.start.y)/(line2.end.x-line2.start.x);
        double b2 = line2.end.y - a2*line2.end.x;
       
        // Solve equation to find intersection point
        // y = a1x + b1
        // y = a2x + b2
        // a1x + b1 = a2x + b2
        // (a1 - a2)x = b2 - b1
        double x = (b2 - b1)/(a1 - a2);
        double y = a1*x+b1;
       
        X = new Point(x,y);
        System.out.println("Point X:"+X .toString());
        return X;
    }
}

Test Class

public static void main(String[] args) {
        Line line1 = new Line(new Point(0,5674), new Point(50,5674));
        Line line2 = new Line(new Point(0,575.4), new Point(50,127057));
        Point inter = line1.intersects(line2);
        System.out.println(inter.x+","+inter.y);
   
        //Check  two lines are instersected
        Line2D.linesIntersect(0,5674,50,5674,0,575.4,50,127057));

}

GET INTERSECTION POINT OF TWO LINES 
& CHECK WHETHER THAT POINT IN ON TWO LINES OR NOT
/***
* Get intersection point between two lines
* @param line1
* @param line2
* @return
* intersection Point (not properly)
*/
public Point getIntersect(double x1, double y1, double x2, double y2,
double x3, double y3, double x4, double y4){
Point intersectionPoint = null;
//Algorithm 1
// slope
double slope1 = (y1-y2) / (x1-x2);
double slope2 = (y3-y4) / (x3-x4);      

// intercept      
double intercept1 = y1 - (slope1*x1);
double intercept2 = y3 - (slope2*x3);

double x = (intercept2 - intercept1) / (slope1 - slope2);
double y = slope1 * x + intercept1;

//Algorithm 12
//double d = (line1.start.x-line1.end.x)*(line2.start.y-line2.end.y) - (line1.start.y-line1.end.y)*(line2.start.x-line2.end.x);
//if (d == 0) return null;

// double d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
// double xi = ((x3-x4)*(x1*y2-y1*x2)-(x1-x2)*(x3*y4-y3*x4))/d;
// double yi = ((y3-y4)*(x1*y2-y1*x2)-(y1-y2)*(x3*y4-y3*x4))/d;

//check if x,y in the line 1: return 0.0 if true
double online1 = Line2D.ptSegDist(x1,y1,x2,y2,x,y);

double online2 = Line2D.ptSegDist(x3,y3,x4,y4,x,y);

if (online1 == 0.0 || online2 == 0.0){
if (y<=y4 && y<=y2){
intersectionPoint = new Point(x,y);
}
}
return intersectionPoint;
}
Source:
http://yinyangit.wordpress.com/2012/04/06/algorithm-intersection-of-two-lines-giao-diem-cua-hai-duong-thang/

Some others reference
/*
System.out.println(Line2D.linesIntersect(0,5674*tempRate,50,5674*tempRate,0,575.4*tempRate,50,127057*tempRate));
Line line1 = new Line(new Point(0,5674*tempRate), new Point(50,5674*tempRate));
Line line2 = new Line(new Point(0,575.4*tempRate), new Point(50,127057*tempRate));
Point inter = line1.intersects(line2);
System.out.println(inter.x+","+inter.y);
Rectangle shape1 = chart.getXYPlot().getRenderer().getSeriesShape(0).getBounds();
Rectangle shape2 = chart.getXYPlot().getRenderer().getSeriesShape(1).getBounds();
System.out.println(shape1.intersection(shape2));
*/