Geometry for Games

Intersection of lines in 2D

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_i is 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

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.

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

Comments

(c) 2006-2010 Alexander Hristov. Todos los derechos reservados
Más información sobre cursos de java, cursos de ajax, cursos de .NET,