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.
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 }
|
intersection-segments.java ( 956 bytes ) |
|
segments.jar ( 17 Kb ) |
