# Fastest linesIntersect method

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

May be something here: http://www.java-gaming.org/index.php/topic,22144.0.html

Hi,

Just an apology and a code fix - I made an error in the above for the edge-case of parallel but non-intersecting lines. The code above is now correct. I was making the false assumption that parallel lines were always collinear and overlapping which is obviously wrong. Sorry! The above code now works.

Oops I made another error in the linesIntersect method, this is getting embarrassing :’(

It was in the corner-case where lines are parallel and collinear. Now it’s fixed, fingers crossed!

Maybe it’s a bit of a gravedig, but I see you’re still active on forums.

Would you be willing to share more of your geometric math? Specifically rectangles intersecting lines/other rectangles. Everything is useful though.

Thanks.

I’ve found this: http://paulbourke.net/geometry/ to be extremely useful.

here

``````
public static boolean doesIntersect(LineSegment line, double x1, double y1, double x2, double y2) {
return doesIntersect(line.getStart().x, line.getStart().y, line.getEnd().x, line.getEnd().y, x1, y1, x2, y2);
}

public static boolean doesIntersect(double l1x1, double l1y1, double l1x2, double l1y2, double l2x1, double l2y1, double l2x2,
double l2y2) {
double denom = ((l2y2 - l2y1) * (l1x2 - l1x1)) - ((l2x2 - l2x1) * (l1y2 - l1y1));

if (denom == 0.0f) {
return false;
}

double ua = (((l2x2 - l2x1) * (l1y1 - l2y1)) - ((l2y2 - l2y1) * (l1x1 - l2x1))) / denom;
double ub = (((l1x2 - l1x1) * (l1y1 - l2y1)) - ((l1y2 - l1y1) * (l1x1 - l2x1))) / denom;

return ((ua >= 0.0d) && (ua <= 1.0d) && (ub >= 0.0d) && (ub <= 1.0d));
}

public static boolean doesIntersect(LineSegment ln1, LineSegment ln2) {
float denom = ((ln2.getEnd().y - ln2.getStart().y) * (ln1.getEnd().x - ln1.getStart().x))
- ((ln2.getEnd().x - ln2.getStart().x) * (ln1.getEnd().y - ln1.getStart().y));

if (denom == 0.0f) {
return false;
}

double ua = ((ln2.getEnd().x - ln2.getStart().x) * (ln1.getStart().y - ln2.getStart().y))
- ((ln2.getEnd().y - ln2.getStart().y) * (ln1.getStart().x - ln2.getStart().x)) / denom;
double ub = ((ln1.getEnd().x - ln1.getStart().x) * (ln1.getStart().y - ln2.getStart().y))
- ((ln1.getEnd().y - ln1.getStart().y) * (ln1.getStart().x - ln2.getStart().x)) / denom;

return ((ua >= 0.0d) && (ua <= 1.0d) && (ub >= 0.0d) && (ub <= 1.0d));
}

public static Point getIntersection(LineSegment line, double x1, double y1, double x2, double y2) {
double denom = ((line.getEnd().y - line.getStart().y) * (x2 - x1))
- ((line.getEnd().x - line.getStart().x) * (y2 - y1));
double nume_a = ((line.getEnd().x - line.getStart().x) * (y1 - line.getStart().y))
- ((line.getEnd().y - line.getStart().y) * (x1 - line.getStart().x));
double nume_b = ((x2 - x1) * (y1 - line.getStart().y)) - ((y2 - y1) * (x1 - line.getStart().x));

if (denom == 0.0f) {
return null;
}

double ua = nume_a / denom;
double ub = nume_b / denom;

if ((ua >= 0.0f) && (ua <= 1.0f) && (ub >= 0.0f) && (ub <= 1.0f)) {

// Get the intersection point.
int intersectX = (int) (line.getStart().x + ua * (line.getEnd().x - line.getStart().x));
int intersectY = (int) (line.getStart().y + ua * (line.getEnd().y - line.getStart().y));

return new Point(intersectX, intersectY);
}

return null;
}

public static Point lineIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
if (denom == 0.0) { // Lines are parallel.
return null;
}
double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denom;
double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denom;
if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) {
// Get the intersection point.
return new Point((int) (x1 + ua * (x2 - x1)), (int) (y1 + ua * (y2 - y1)));
}

return null;
}

``````

hth

``````
public static boolean checkCollision(Rectangle rect1, Rectangle rect2) {
if ((rect1.getRotation() == 0x00) && (rect2.getRotation() == 0x00)) {    // see if we should just do standard collision checking
int tw = rect1.width;
int th = rect1.height;
int rw = rect2.width;
int rh = rect2.height;

if ((rw <= 0) || (rh <= 0) || (tw <= 0) || (th <= 0)) {
return false;
}

int tx = rect1.x;
int ty = rect1.y;
int rx = rect2.getX();
int ry = rect2.getY();

rw += rx;
rh += ry;
tw += tx;
th += ty;
return (((rw < rx) || (rw > tx)) && ((rh < ry) || (rh > ty)) && ((tw < tx) || (tw > rx))
&& ((th < ty) || (th > ry)));
} else {

// First do a circle on circle collision test
int rectS1 = rect1.getWidth() / 2;

if (rectS1 > rect1.getHeight() / 2) {
rectS1 = rect1.getHeight() / 2;
}

int rectS2 = rect2.getWidth() / 2;

if (rectS2 > rect2.getHeight() / 2) {
rectS2 = rect2.getHeight() / 2;
}

int radiiSum = rectS1 + rectS2;
int rcw1 = rect1.getX() + rect1.getWidth() / 2;
int rch1 = rect1.getY() + rect1.getHeight() / 2;
int rcw2 = rect2.getX() + rect2.getWidth() / 2;
int rch2 = rect2.getY() + rect2.getHeight() / 2;
double dist = getDistanceSq(rcw1, rch1, rcw2, rch2);

if (dist > radiiSum * radiiSum) {    // The inner circles don't intersect - no collision is possible.
return false;
}

Vector2D a = new Vector2D(0, 0);
Vector2D b = new Vector2D(0, 0);
Vector2D c;
Vector2D bl, tr;
float ang = (float) (rect1.getRotation() - rect2.getRotation()), cosa = (float) Math.cos((double) ang),
sina = (float) Math.sin((double) ang);
float t_, x, a_;
float dx;
float vert1, vert2;

c = new Vector2D(rect2.getX() + rect2.getWidth() / 2, rect2.getY() + rect2.getHeight() / 2);
rotateVector2DClockwise(c, (float) rect2.getRotation());
bl = c.copy();
tr = c.copy();
a.setX(-rect1.getHeight() / 2 * sina);
b.setX(a.getX());
t_ = rect1.getWidth() / 2 * cosa;
a.setX(a.getX() + t_);
b.setX(b.getX() - t_);
a.setY(rect1.getHeight() / 2 * cosa);
b.setY(a.getY());
t_ = rect1.getHeight() / 2 * sina;
a.setY(a.getY() + t_);
b.setY(b.getY() - t_);
t_ = sina * cosa;

if (t_ < 0) {
t_ = a.getX();
a.setX(b.getX());
b.setX(t_);
t_ = a.getY();
a.setY(b.getY());
b.setY(t_);
}

if (sina < 0) {
b.setX(-b.getX());
b.setY(-b.getY());
}

if ((b.getX() > tr.getX()) || (b.getX() > -bl.getX())) {
return false;
}

if (t_ == 0) {
vert1 = a.getY();
vert2 = -vert1;
} else {
x = bl.getX() - a.getX();
a_ = tr.getX() - a.getX();
vert1 = a.getY();

if (a_ * x > 0) {
dx = a.getX();

if (x < 0) {
dx -= b.getX();
vert1 -= b.getY();
x = a_;
} else {
dx += b.getX();
vert1 += b.getY();
}

vert1 *= x;
vert1 /= dx;
vert1 += a.getY();
}

x = bl.getX() + a.getX();
a_ = tr.getX() + a.getX();
vert2 = -a.getY();

if (a_ * x > 0) {
dx = -a.getX();

if (x < 0) {
dx -= b.getX();
vert2 -= b.getY();
x = a_;
} else {
dx += b.getX();
vert2 += b.getY();
}

vert2 *= x;
vert2 /= dx;
vert2 -= a.getY();
}
}

if (vert1 > vert2) {
t_ = vert1;
vert1 = vert2;
vert2 = t_;
}

return !(((vert1 < bl.getY()) && (vert2 < bl.getY())) || ((vert1 > tr.getY()) && (vert2 > tr.getY())));
}
}

``````

rotated rect vs rotated rect collision detector

Sure, I’ve put all of the most useful 2D operations i’ve found and made in the straightedge.geom.KPolygon class here:

To do rectangle-rectangle you can make a rectangle polygon using the above code, and then easily do intersections with other polygons, lines, and so on. The hardest code to make fast and correct for me was polygon.contains(point), line intersection testing and the point of line-line intersection. But they’re working well in that polygon class.

Yes that stuff is great. So is
http://www.cs.princeton.edu/introcs/35purple/Polygon.java.html
and Joseph O’Rourke http://exaflop.org/docs/cgafaq/cga2.html

Thank you, very useful

That may not quite be the fastest algorithm, actually. I tested the algorithm you provided and the one I provide below. This other algorithm is approximately 40% faster, but the caveat is that it does not return true when an endpoint of a line segment is exactly on the other line segment. Here’s the implementation with that minor caveat, as it can be ignored in some applications.

``````private static int cmp(double a, double b) {
return (a > b ? 1 : 0) - (a < b ? 1 : 0);
}

private static int orientation(double x0, double y0, double x1, double y1, double x2, double y2) {
return cmp((x2 - x1) * (y1 - y0), (x1 - x0) * (y2 - y1));
}

private static boolean linesIntersect(double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3) {
return orientation(x0, y0, x1, y1, x2, y2) != orientation(x0, y0, x1, y1, x3, y3) && orientation(x2, y2, x3, y3, x0, y0) != orientation(x2, y2, x3, y3, x1, y1);
}
``````

I got this algorithm from https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/.

2 Likes

You should be very cautious about using floating point for this kind of algorithm. You’re going to find anomalous results such as doesIntersect(a,b) != doesIntersect(b,a), or getLineIntersection(a,b) != getLineIntersection(b,a).

In some applications it won’t matter, but when it matters it matters a lot.

1 Like