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

Intersection of segments in 2D

Alexander Hristov

Intersection of two segments

Computing the intersection of two segments is no different than computing the intersection between the lines that define them. The only difference is that once we have the intersection point, we must make sure that it falls inside the segments.

Here is a Java function that does the trick. Use freely, but please give credit. LGPL license.

intersection-segments.java

0001  /**
0002   * Computes the intersection between two segments. 
0003   * @param x1 Starting point of Segment 1
0004   * @param y1 Starting point of Segment 1
0005   * @param x2 Ending point of Segment 1
0006   * @param y2 Ending point of Segment 1
0007   * @param x3 Starting point of Segment 2
0008   * @param y3 Starting point of Segment 2
0009   * @param x4 Ending point of Segment 2
0010   * @param y4 Ending point of Segment 2
0011   * @return Point where the segments intersect, or null if they don't
0012   */
0013  public Point intersection(
0014    int x1,int y1,int x2,int y2, 
0015    int x3, int y3, int x4,int y4
0016  ) {
0017    int d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
0018    if (d == 0) return null;
0019    
0020    int xi = ((x3-x4)*(x1*y2-y1*x2)-(x1-x2)*(x3*y4-y3*x4))/d;
0021    int yi = ((y3-y4)*(x1*y2-y1*x2)-(y1-y2)*(x3*y4-y3*x4))/d;
0022    
0023    Point p = new Point(xi,yi);
0024    if (xi < Math.min(x1,x2) || xi > Math.max(x1,x2)) return null;
0025    if (xi < Math.min(x3,x4) || xi > Math.max(x3,x4)) return null;
0026    return p;
0027  }

You can test the results of this function in the following applet. Click on the canvas to select the starting and ending points of each segment. As soon as you have defined the fourth point, the intersection will be computed. You can download the applet .jar file, which includes full sources.

Source code

intersection-segments.java
( 956 bytes )

Resources

segments.jar
( 17 Kb )

Comments

Jan 06, 2011 at 00:29 Sent by Alex

this should work too: A = y2 - y1; Ap = y4 - y3; B = x1 - x2; Bp = x3 - x4; C = y1 * x2 - y2 * x1; Cp = y3 * x4 - y4 * x3; try { xi = (B * Cp - Bp * C) / (A * Bp - Ap * B); yi = (C * Ap - Cp * A) / (A * Bp - Ap * B); } catch (java.lang.ArithmeticException e) { // Only Chuck can divide by zero return null; }

Apr 24, 2009 at 22:09 Sent by Ralph

well this algorithm does not work if one of the segments is vertical. i suggest the following: public Point2D.Double intersection( double x1,double y1,double x2,double y2, double x3, double y3, double x4,double y4 ) { double d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4); if (d == 0) return null; double xi = ((x3-x4)*(x1*y2-y1*x2)-(x1-x2)*(x3*y4-y3*x4))/d; double yi = ((y3-y4)*(x1*y2-y1*x2)-(y1-y2)*(x3*y4-y3*x4))/d; if(x3==x4) { if ( yi < Math.min(y1,y2) || yi > Math.max(y1,y2) )return null; } Point2D.Double p = new Point2D.Double(xi,yi); if (xi < Math.min(x1,x2) || xi > Math.max(x1,x2)) return null; if (xi < Math.min(x3,x4) || xi > Math.max(x3,x4)) return null; return p; } thank you

Jan 16, 2008 at 18:31 Sent by Skud

There is a bug when one of the segments is vertical, you should also test on the y coordinate to correct that: if (yi < Math.min(y1,y2) || yi > Math.max(y1,y2)) return null; if (yi < Math.min(y3,y4) || yi > Math.max(y3,y4)) return null;

Jul 31, 2007 at 17:36 Sent by anonymous

2d segment intersection can be empty, a point or a segment

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

Geometry for Games

Intersection of segments in 2D

Intersection of two segments

Source code

Resources

Comments

Add a Comment