Make delicious recipes!

Intersection point of two lines



Problem: Given two lines on a 2D plane, find the intersection point of these two lines.
Each line is specified by two points (x1,y1) and (x2,y2)


Solution: A line formed by two points can be expressed in the form ax + by = c
Similarly other line can be expressed as px + qy = r
This can be expressed in a matrix form as:

[a b c]
[p q r]

The above can then be solved using linear programming.
Code for the same is as follows:


public class LineIntersection 
{
    static class Point 
    {
        public Integer x, y;

        public Point(Integer x, Integer y) 
        {
            super();
            this.x = x;
            this.y = y;
        }
    }
    
    
    static void findIntersection(Point p1, Point p2, Point p3, Point p4) 
    {
        int matrix [][] = new int [2][];
        matrix[0] = createLine (p1, p2);  // ax + by = c
        matrix[1] = createLine (p3, p4);  // px + qy = r
        
        printMatrix (matrix, "Initial matrix: ");
        
        int b = matrix[0][1];
        int q = matrix[1][1];
        
        if (b == 0 && q == 0)
        {
            if (matrix[0][0]*matrix[1][2] == matrix[1][0]*matrix[0][2])
                System.out.println ("Vertical congruent lines");
            else
                System.out.println ("Vertical parallel lines");
            return;
        }
        
        if (b != 0 && q != 0)
        {
            // multiply first line by q
            matrix[0][0] *= q;
            matrix[0][1] *= q;
            matrix[0][2] *= q;

            // multiply second line by b
            matrix[1][0] *= b;
            matrix[1][1] *= b;
            matrix[1][2] *= b;


            printMatrix (matrix, "After mutliplying by 'b' and 'q': ");
            // perform q(ax + by = c) - b(px + qy = r) to give 
            // (qa-bp)x = qc-br
            matrix[0][0] -= matrix[1][0];
            matrix[0][1] -= matrix[1][1];
            matrix[0][2] -= matrix[1][2];
        }
        else
        {
            if (q == 0)
            {
                // swap lines so that first line has b coefficient=0
                for (int i=0; i<3; i++) 
                {
                    int tmp = matrix[0][i];
                    matrix[0][i] = matrix[1][i];
                    matrix[1][i] = tmp;
                }
            }
        }
        
        if (matrix[0][0] == 0 && matrix[0][2] == 0)
        {
            System.out.println ("Congruent lines");
            return;
        }
        
        if (matrix[0][0] == 0)
        {
            System.out.println ("Parallel lines");
            return;
        }
        
        printMatrix (matrix, "Eliminating b: ");
        
        float x = matrix[0][2]/matrix[0][0];
        float y = (matrix[1][2] - x*matrix[1][0])/matrix[1][1];
        
        System.out.println ("Intersection point at " + x + ", " + y);        
    }
    
    
    public static void main(String[] args) 
    {
        
        Point p1 = new Point (getNum(), getNum());
        Point p2 = new Point (getNum(), getNum());
        
        Point p3 = new Point (getNum(), getNum());
        Point p4 = new Point (getNum(), getNum());
        
        printPoint(p1, "p1");
        printPoint(p2, "p2");
        printPoint(p3, "p3");
        printPoint(p4, "p4");
        
        findIntersection (p1, p2, p3, p4);
    }

    
    static int getNum ()
    {
        return (int)(Math.random()*20);
    }
    
    
    // converts the given points into line equation of the form ax + by = c
    static int[] createLine(Point p1, Point p2) 
    {
        int line [] = new int[3];
    
        line[0] = p1.y - p2.y; // finds constant a
        line[1] = p2.x - p1.x; // finds constant b
        line[2] = p1.y*(p2.x - p1.x) - p1.x*(p2.y - p1.y); // finds constant c
        
        return line; // Equation of line is now ax + by = c
    }
    
    
    static void printMatrix(int[][] m, String msg) 
    {
        System.out.println ("\n" + msg);
        System.out.println (m[0][0] + " " + m[0][1] + " " + m[0][2]);
        System.out.println (m[1][0] + " " + m[1][1] + " " + m[1][2]);
        System.out.println ();
    }

    static void printPoint(Point p, String msg) 
    {
        System.out.println (msg + ": " + p.x + ", " + p.y);
    }

}



Sample Executions:


Execution 1 Execution 2 Execution 3 Execution 4
p1: 6, 14
p2: 19, 3
p3: 13, 16
p4: 14, 17

Initial matrix: 
11 13 248
-1 1 3


After mutliplying by 'b' and 'q': 
11 13 248
-13 13 39


Eliminating b: 
24 0 209
-13 13 39

Intersection point at 8.0, 11.0

p1: 6, 2
p2: 7, 3
p3: 9, 15
p4: 7, 16

Initial matrix: 
-1 1 -4
-1 -2 -39


After mutliplying by 'b' and 'q': 
2 -2 8
-1 -2 -39


Eliminating b: 
3 0 47
-1 -2 -39

Intersection point at 15.0, 12.0

p1: 1, 6
p2: 4, 18
p3: 6, 14
p4: 3, 11

Initial matrix: 
-12 3 6
3 -3 -24


After mutliplying by 'b' and 'q': 
36 -9 -18
9 -9 -72


Eliminating b: 
27 0 54
9 -9 -72

Intersection point at 2.0, 10.0

p1: 11, 12
p2: 8, 4
p3: 14, 1
p4: 11, 7

Initial matrix: 
8 -3 52
-6 -3 -87


After mutliplying by 'b' and 'q': 
-24 9 -156
18 9 261


Eliminating b: 
-42 0 -417
18 9 261

Intersection point at 9.0, 11.0






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal