Hi,
I’ve been really getting into computer geometry lately and done lots of research on the fastest way to do various 2D linear geometry things, and surprisingly it’s quite hard to find the fastest methods to do basic things like line intersections. So I thought I’d share the fastest methods that I’ve come across, which might save you some time 8)
The fastest way to test if 2 line segments intersect. Tests if the line segment from (x1, y1) to (x2, y2) intersects the line segment from (x3, y3) to (x4, y4). My tests showed that this method was about 25% faster than java.awt.geom.Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4):
public static boolean linesIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4){
// Return false if either of the lines have zero length
if (x1 == x2 && y1 == y2 ||
x3 == x4 && y3 == y4){
return false;
}
// Fastest method, based on Franklin Antonio's "Faster Line Segment Intersection" topic "in Graphics Gems III" book (http://www.graphicsgems.org/)
double ax = x2-x1;
double ay = y2-y1;
double bx = x3-x4;
double by = y3-y4;
double cx = x1-x3;
double cy = y1-y3;
double alphaNumerator = by*cx - bx*cy;
double commonDenominator = ay*bx - ax*by;
if (commonDenominator > 0){
if (alphaNumerator < 0 || alphaNumerator > commonDenominator){
return false;
}
}else if (commonDenominator < 0){
if (alphaNumerator > 0 || alphaNumerator < commonDenominator){
return false;
}
}
double betaNumerator = ax*cy - ay*cx;
if (commonDenominator > 0){
if (betaNumerator < 0 || betaNumerator > commonDenominator){
return false;
}
}else if (commonDenominator < 0){
if (betaNumerator > 0 || betaNumerator < commonDenominator){
return false;
}
}
if (commonDenominator == 0){
// This code wasn't in Franklin Antonio's method. It was added by Keith Woodward.
// The lines are parallel.
// Check if they're collinear.
double y3LessY1 = y3-y1;
double collinearityTestForP3 = x1*(y2-y3) + x2*(y3LessY1) + x3*(y1-y2); // see http://mathworld.wolfram.com/Collinear.html
// If p3 is collinear with p1 and p2 then p4 will also be collinear, since p1-p2 is parallel with p3-p4
if (collinearityTestForP3 == 0){
// The lines are collinear. Now check if they overlap.
if (x1 >= x3 && x1 <= x4 || x1 <= x3 && x1 >= x4 ||
x2 >= x3 && x2 <= x4 || x2 <= x3 && x2 >= x4 ||
x3 >= x1 && x3 <= x2 || x3 <= x1 && x3 >= x2){
if (y1 >= y3 && y1 <= y4 || y1 <= y3 && y1 >= y4 ||
y2 >= y3 && y2 <= y4 || y2 <= y3 && y2 >= y4 ||
y3 >= y1 && y3 <= y2 || y3 <= y1 && y3 >= y2){
return true;
}
}
}
return false;
}
return true;
}
This method calculates the intersection point of two lines, or returns null if they’re parallel. Note that the line segments may not actually intersect, but the intersection point will still be returned, so long as the lines aren’t parallel. This method treats the lines as never-ending lines, not line segments. Use ‘linesIntersect’ to test for intersection.
public static KPoint getLineLineIntersection(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
double det1And2 = det(x1, y1, x2, y2);
double det3And4 = det(x3, y3, x4, y4);
double x1LessX2 = x1 - x2;
double y1LessY2 = y1 - y2;
double x3LessX4 = x3 - x4;
double y3LessY4 = y3 - y4;
double det1Less2And3Less4 = det(x1LessX2, y1LessY2, x3LessX4, y3LessY4);
if (det1Less2And3Less4 == 0){
// the denominator is zero so the lines are parallel and there's either no solution (or multiple solutions if the lines overlap) so return null.
return null;
}
double x = (det(det1And2, x1LessX2,
det3And4, x3LessX4) /
det1Less2And3Less4);
double y = (det(det1And2, y1LessY2,
det3And4, y3LessY4) /
det1Less2And3Less4);
return new KPoint(x, y);
}
protected static double det(double a, double b, double c, double d) {
return a * d - b * c;
}
I’ve also got fast code for a few other things like polygon.contains(point). Let me know if it’d be useful.
Keith
