Intersection point of two linesProblem: 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:
|
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: