import java.awt.geom.Point2D;
/**
* Utility class for computing intersections between lines and line segments.
*/
public class Intersection
{
/**
* Epsilon for floating point computations
*/
private static final double epsilon = 1e-6f;
/**
* Computes the intersection of the specified line segments and returns
* the intersection point, or <code>null</code> if the line segments do
* not intersect.
*
* @param s0x0 x-coordinate of point 0 of line segment 0
* @param s0y0 y-coordinate of point 0 of line segment 0
* @param s0x1 x-coordinate of point 1 of line segment 0
* @param s0y1 y-coordinate of point 1 of line segment 0
* @param s1x0 x-coordinate of point 0 of line segment 1
* @param s1y0 y-coordinate of point 0 of line segment 1
* @param s1x1 x-coordinate of point 1 of line segment 1
* @param s1y1 y-coordinate of point 1 of line segment 1
* @param location Optional location that stores the
* relative location of the intersection point on
* the given line segments
* @return The intersection point, or <code>null</code> if
* there is no intersection.
*/
public static Point2D computeIntersectionSegmentSegment(
double s0x0, double s0y0,
double s0x1, double s0y1,
double s1x0, double s1y0,
double s1x1, double s1y1)
{
Point2D location = new Point2D.Double();
Point2D result = computeIntersectionLineLine(
s0x0, s0y0, s0x1, s0y1, s1x0, s1y0, s1x1, s1y1, location);
if (location.getX() >= 0 && location.getX() <= 1.0 &&
location.getY() >= 0 && location.getY() <= 1.0)
{
return result;
}
return null;
}
/**
* Computes the intersection of the specified lines and returns the
* intersection point, or <code>null</code> if the lines do not
* intersect.
*
* Ported from
* [url]http://www.geometrictools.com/LibMathematics/Intersection/[/url]
* Wm5IntrSegment2Segment2.cpp
*
* @param s0x0 x-coordinate of point 0 of line segment 0
* @param s0y0 y-coordinate of point 0 of line segment 0
* @param s0x1 x-coordinate of point 1 of line segment 0
* @param s0y1 y-coordinate of point 1 of line segment 0
* @param s1x0 x-coordinate of point 0 of line segment 1
* @param s1y0 y-coordinate of point 0 of line segment 1
* @param s1x1 x-coordinate of point 1 of line segment 1
* @param s1y1 y-coordinate of point 1 of line segment 1
* @param location Optional location that stores the
* relative location of the intersection point on
* the given line segments
* @return The intersection point, or <code>null</code> if
* there is no intersection.
*/
public static Point2D computeIntersectionLineLine(
double s0x0, double s0y0,
double s0x1, double s0y1,
double s1x0, double s1y0,
double s1x1, double s1y1,
Point2D location)
{
double dx0 = s0x1 - s0x0;
double dy0 = s0y1 - s0y0;
double dx1 = s1x1 - s1x0;
double dy1 = s1y1 - s1y0;
double len0 = Math.sqrt(dx0*dx0+dy0*dy0);
double len1 = Math.sqrt(dx1*dx1+dy1*dy1);
double dir0x = dx0 / len0;
double dir0y = dy0 / len0;
double dir1x = dx1 / len1;
double dir1y = dy1 / len1;
double c0x = s0x0 + dx0 * 0.5;
double c0y = s0y0 + dy0 * 0.5;
double c1x = s1x0 + dx1 * 0.5;
double c1y = s1y0 + dy1 * 0.5;
double cdx = c1x - c0x;
double cdy = c1y - c0y;
double dot = dotPerp(dir0x, dir0y, dir1x, dir1y);
if (Math.abs(dot) > epsilon)
{
double dot0 = dotPerp(cdx, cdy, dir0x, dir0y);
double dot1 = dotPerp(cdx, cdy, dir1x, dir1y);
double invDot = 1.0/dot;
double s0 = dot1*invDot;
double s1 = dot0*invDot;
if (location != null)
{
double n0 = (s0 / len0) + 0.5;
double n1 = (s1 / len1) + 0.5;
location.setLocation(n0, n1);
}
double x = c0x + s0 * dir0x;
double y = c0y + s0 * dir0y;
return new Point2D.Double(x,y);
}
return null;
}
/**
* Returns the perpendicular dot product, i.e. the length
* of the vector (x0,y0,0)x(x1,y1,0).
*
* @param x0 Coordinate x0
* @param y0 Coordinate y0
* @param x1 Coordinate x1
* @param y1 Coordinate y1
* @return The length of the cross product vector
*/
private static double dotPerp(double x0, double y0, double x1, double y1)
{
return x0*y1 - y0*x1;
}
/**
* Private constructor to prevent instantiation
*/
private Intersection()
{
}
}
