Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## 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: