Alexander Hristov - Geometry for Games - Intersection of lines in 2D

Intersection of lines in 2D

Alexander Hristov

Intersection of Lines in y=ax+b form

If you have the equations in y = ax+b format for both lines (i.e. : none of them is vertical), the lines intersect only if the slopes are different ( a₁ ≠ a₂), and the intersection is:

x = (b₂-b₁)/(a₁-a₂)

y = a₁x + b₁ = a₁(b₂-b₁)/(a₁-a₂) + b₁

Intersection of Lines in ax+by +c = 0 form

If you have the equations in the more general case : ax+by+c = 0, the lines intersect only if a₁b₂≠a₂b₁. If both lines are vertical then by definition they do not intersect, so it can be assumed that at least one of the lines is non-vertical (for example, a₁≠0). In this case, the intersection is:

y = (c₁a₂- c₂a₁)/(a₁b₂-a₂b₁)
x = -1/a₁ - b₁y/a₁

Intersection of Lines defined by four points.

If you have four points : (x₁,y₁) and (x₂,y₂) belonging to the first line and (x₃,y₃) and (x₄,y₄) belonging to the second line, the intersection is given by solving the following equations:

and

where x_i,y_iis the intersection point. Now I assume you came here for the plain results and not for an explanation or derivation of them, so, getting to the point:

The lines intersect if D ≡ (x₁-x₂)(y₃-y₄) - (y₁-y₂)(x₃-x₄) ≠0. The intersection point is

Intersection of two lines

where "D" is the above quantity.

The following Java function returns the intersection of two lines defined by four points. Use freely, but please give credit. LGPL license.

intersection-lines.java

0001  /**
0002   * Computes the intersection between two lines. The calculated point is approximate, 
0003   * since integers are used. If you need a more precise result, use doubles
0004   * everywhere. 
0005   * (c) 2007 Alexander Hristov. Use Freely (LGPL license). http://www.ahristov.com
0006   *
0007   * @param x1 Point 1 of Line 1
0008   * @param y1 Point 1 of Line 1
0009   * @param x2 Point 2 of Line 1
0010   * @param y2 Point 2 of Line 1
0011   * @param x3 Point 1 of Line 2
0012   * @param y3 Point 1 of Line 2
0013   * @param x4 Point 2 of Line 2
0014   * @param y4 Point 2 of Line 2
0015   * @return Point where the segments intersect, or null if they don't
0016   */
0017  public Point intersection(
0018    int x1,int y1,int x2,int y2, 
0019    int x3, int y3, int x4,int y4
0020  ) {
0021    int d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
0022    if (d == 0) return null;
0023    
0024    int xi = ((x3-x4)*(x1*y2-y1*x2)-(x1-x2)*(x3*y4-y3*x4))/d;
0025    int yi = ((y3-y4)*(x1*y2-y1*x2)-(y1-y2)*(x3*y4-y3*x4))/d;
0026    
0027    return new Point(xi,yi);
0028  }

Source code

intersection-lines.java
( 984 bytes )

Comments

Jan 16, 2008 at 20:41 Sent by anonymous

Awesome, easy to read, implement, understand and it works! I have looked around the net for easy algorithms that does the trick and the only easy one I found produced wrong intersection point! Thank you alot for this snippet!

Jul 12, 2007 at 12:30 Sent by anonymous

thanks for your contributions, have a great day.

Name (optional)
EMail (optional, will not be displayed)
Text

Geometry for Games