How to test if a line segment intersects an axis-aligned rectange in 2D?

Question

How to test if a line segment intersects an axis-aligned rectange in 2D? The segment is defined with its two ends: p1, p2. The rectangle is defined with top-left and bottom-right points.

score 64 · Answer 1 · answered Nov 15 '08 at 21:07

64

The original poster wanted to DETECT an intersection between a line segment and a polygon. There was no need to LOCATE the intersection, if there is one. If that's how you meant it, you can do less work than Liang-Barsky or Cohen-Sutherland:

Let the segment endpoints be p1=(x1 y1) and p2=(x2 y2).
Let the rectangle's corners be (xBL yBL) and (xTR yTR).

Then all you have to do is

A. Check if all four corners of the rectangle are on the same side of the line. The implicit equation for a line through p1 and p2 is:

F(x y) = (y2-y1)*x + (x1-x2)*y + (x2*y1-x1*y2)

If F(x y) = 0, (x y) is ON the line.
If F(x y) > 0, (x y) is "above" the line.
If F(x y) < 0, (x y) is "below" the line.

Substitute all four corners into F(x y). If they're all negative or all positive, there is no intersection. If some are positive and some negative, go to step B.

B. Project the endpoint onto the x axis, and check if the segment's shadow intersects the polygon's shadow. Repeat on the y axis:

If (x1 > xTR and x2 > xTR), no intersection (line is to right of rectangle).
If (x1 < xBL and x2 < xBL), no intersection (line is to left of rectangle).
If (y1 > yTR and y2 > yTR), no intersection (line is above rectangle).
If (y1 < yBL and y2 < yBL), no intersection (line is below rectangle).
else, there is an intersection. Do Cohen-Sutherland or whatever code was mentioned in the other answers to your question.

You can, of course, do B first, then A.

Alejo

answered Nov 15 '08 at 21:07

user37968

641
4
2

1

Another way to shortcut this would be to go through the rectangle in the following order: F(topleft),F(topright),F(bottomright),F(bottomleft) and then to check if any of those equation's signs is different from the previous one, meaning that one point is 'below' and the next is 'above' the line. – noio Feb 17 '11 at 21:02
1

Very well explained, and it seems to handle the case where the segment is completely enclosed by the box. – Paul Chernoch Oct 10 '13 at 18:14
I have F(x, y) < 0 as above the line. Although it doesn't make a difference to the algorithm. – Druckles Mar 07 '14 at 13:56
Why is the step B necessary? I can't think of case when some corners are on different sides of the line and the line does not intersect the rectangle. – jnovacho Apr 05 '15 at 14:26
1

@jnovacho, I guess is because it's not really a line it's a segment with endpoints. Even if the line over the segment intersects the segment may not. – RubenLaguna Sep 30 '15 at 07:07
It is really a good answer when we just want to determine if they are intersecting. – Eric Jun 13 '18 at 05:32
I'm benchmarking 5 different answers here and it looks like this is the fastest solution, and by a good margin faster than cohen-sutherland. Good job! – pid Feb 22 '19 at 09:40
11 years later and still relevant! Note that if you're using this in a 2D game and already have rectangle-rectangle collision working, you can offload step B to your other function by making a rectangle out of the line and then testing for collision. – Nick Reed Sep 17 '19 at 04:38

score 28 · Answer 2 · answered Sep 19 '08 at 07:07

Wrote quite simple and working solution:

      bool SegmentIntersectRectangle(double a_rectangleMinX,
                                 double a_rectangleMinY,
                                 double a_rectangleMaxX,
                                 double a_rectangleMaxY,
                                 double a_p1x,
                                 double a_p1y,
                                 double a_p2x,
                                 double a_p2y)
  {
    // Find min and max X for the segment

    double minX = a_p1x;
    double maxX = a_p2x;

    if(a_p1x > a_p2x)
    {
      minX = a_p2x;
      maxX = a_p1x;
    }

    // Find the intersection of the segment's and rectangle's x-projections

    if(maxX > a_rectangleMaxX)
    {
      maxX = a_rectangleMaxX;
    }

    if(minX < a_rectangleMinX)
    {
      minX = a_rectangleMinX;
    }

    if(minX > maxX) // If their projections do not intersect return false
    {
      return false;
    }

    // Find corresponding min and max Y for min and max X we found before

    double minY = a_p1y;
    double maxY = a_p2y;

    double dx = a_p2x - a_p1x;

    if(Math::Abs(dx) > 0.0000001)
    {
      double a = (a_p2y - a_p1y) / dx;
      double b = a_p1y - a * a_p1x;
      minY = a * minX + b;
      maxY = a * maxX + b;
    }

    if(minY > maxY)
    {
      double tmp = maxY;
      maxY = minY;
      minY = tmp;
    }

    // Find the intersection of the segment's and rectangle's y-projections

    if(maxY > a_rectangleMaxY)
    {
      maxY = a_rectangleMaxY;
    }

    if(minY < a_rectangleMinY)
    {
      minY = a_rectangleMinY;
    }

    if(minY > maxY) // If Y-projections do not intersect return false
    {
      return false;
    }

    return true;
  }

Upvote. I tried the top answer, but my test against putting a box on top of a line going from 100 50 to 100 100 failed. — agmcleod, Jul 10 '12 at 03:15
This is really simple and works great! I did a javascript test: http://jsfiddle.net/77eej/2/ — urraka, Nov 27 '12 at 00:22
Btw, anyone can point out why `abs(dx) > 0.0000001` instead of just zero? — urraka, Nov 27 '12 at 00:38
Because floating point math is inaccurate. Two numbers that mathematically should be equal can differ by a very small amount, causing equality comparisons to fail. — Minthos, Dec 11 '12 at 11:36
does not work in some cases, try on a box [0,0 100,100], with points [25,125] and [101,100] and see that it will return true. But the segment is clearly outside. — Palax, May 08 '14 at 20:36
@Palax You've done something wrong, I tried those exact same coordinates by editing them into urraka's jsfiddle above and it returned false correctly. — Nathan Williams, Jan 30 '17 at 07:00
i know this is old, could someone explain why try to find minY maxY using the slope, then only to re-order and find true minY, maxY later on. — Vinh, Oct 13 '17 at 15:09

score 9 · Answer 3 · answered Sep 19 '08 at 03:51

9

Since your rectangle is aligned, Liang-Barsky might be a good solution. It is faster than Cohen-Sutherland, if speed is significant here.

Siggraph explanation
Another good description
And of course, Wikipedia

answered Sep 19 '08 at 03:51

ryan_s

7,826
3
27
28

score 7 · Answer 4 · answered Dec 12 '12 at 16:57

7

You could also create a rectangle out of the segment and test if the other rectangle collides with it, since it is just a series of comparisons. From pygame source:

def _rect_collide(a, b):
    return a.x + a.w > b.x and b.x + b.w > a.x and \
           a.y + a.h > b.y and b.y + b.h > a.y

answered Dec 12 '12 at 16:57

asolano

87
2
2

4

This is too simple and over-eager. It will collect false positives where the start of the line overlaps in x but not y, and the end of the line overlaps in y, but not x (or vice versa). – Synesso Oct 27 '15 at 05:09

easeout · Answer 5 · 2008-09-19T03:54:03.710

Use the Cohen-Sutherland algorithm.

It's used for clipping but can be slightly tweaked for this task. It divides 2D space up into a tic-tac-toe board with your rectangle as the "center square".
then it checks to see which of the nine regions each of your line's two points are in.

If both points are left, right, top, or bottom, you trivially reject.
If either point is inside, you trivially accept.
In the rare remaining cases you can do the math to intersect with whichever sides of the rectangle are possible to intersect with, based on which regions they're in.

Craigo · Answer 6 · 2011-03-22T05:26:20.063

Or just use/copy the code already in the Java method

java.awt.geom.Rectangle2D.intersectsLine(double x1, double y1, double x2, double y2)

Here is the method after being converted to static for convenience:

/**
 * Code copied from {@link java.awt.geom.Rectangle2D#intersectsLine(double, double, double, double)}
 */
public class RectangleLineIntersectTest {
    private static final int OUT_LEFT = 1;
    private static final int OUT_TOP = 2;
    private static final int OUT_RIGHT = 4;
    private static final int OUT_BOTTOM = 8;

    private static int outcode(double pX, double pY, double rectX, double rectY, double rectWidth, double rectHeight) {
        int out = 0;
        if (rectWidth <= 0) {
            out |= OUT_LEFT | OUT_RIGHT;
        } else if (pX < rectX) {
            out |= OUT_LEFT;
        } else if (pX > rectX + rectWidth) {
            out |= OUT_RIGHT;
        }
        if (rectHeight <= 0) {
            out |= OUT_TOP | OUT_BOTTOM;
        } else if (pY < rectY) {
            out |= OUT_TOP;
        } else if (pY > rectY + rectHeight) {
            out |= OUT_BOTTOM;
        }
        return out;
    }

    public static boolean intersectsLine(double lineX1, double lineY1, double lineX2, double lineY2, double rectX, double rectY, double rectWidth, double rectHeight) {
        int out1, out2;
        if ((out2 = outcode(lineX2, lineY2, rectX, rectY, rectWidth, rectHeight)) == 0) {
            return true;
        }
        while ((out1 = outcode(lineX1, lineY1, rectX, rectY, rectWidth, rectHeight)) != 0) {
            if ((out1 & out2) != 0) {
                return false;
            }
            if ((out1 & (OUT_LEFT | OUT_RIGHT)) != 0) {
                double x = rectX;
                if ((out1 & OUT_RIGHT) != 0) {
                    x += rectWidth;
                }
                lineY1 = lineY1 + (x - lineX1) * (lineY2 - lineY1) / (lineX2 - lineX1);
                lineX1 = x;
            } else {
                double y = rectY;
                if ((out1 & OUT_BOTTOM) != 0) {
                    y += rectHeight;
                }
                lineX1 = lineX1 + (y - lineY1) * (lineX2 - lineX1) / (lineY2 - lineY1);
                lineY1 = y;
            }
        }
        return true;
    }
}

score 1 · Answer 7 · answered Aug 04 '13 at 19:20

Here's a javascript version of @metamal's answer

var isRectangleIntersectedByLine = function (
  a_rectangleMinX,
  a_rectangleMinY,
  a_rectangleMaxX,
  a_rectangleMaxY,
  a_p1x,
  a_p1y,
  a_p2x,
  a_p2y) {

  // Find min and max X for the segment
  var minX = a_p1x
  var maxX = a_p2x

  if (a_p1x > a_p2x) {
    minX = a_p2x
    maxX = a_p1x
  }

  // Find the intersection of the segment's and rectangle's x-projections
  if (maxX > a_rectangleMaxX)
    maxX = a_rectangleMaxX

  if (minX < a_rectangleMinX)
    minX = a_rectangleMinX

  // If their projections do not intersect return false
  if (minX > maxX)
    return false

  // Find corresponding min and max Y for min and max X we found before
  var minY = a_p1y
  var maxY = a_p2y

  var dx = a_p2x - a_p1x

  if (Math.abs(dx) > 0.0000001) {
    var a = (a_p2y - a_p1y) / dx
    var b = a_p1y - a * a_p1x
    minY = a * minX + b
    maxY = a * maxX + b
  }

  if (minY > maxY) {
    var tmp = maxY
    maxY = minY
    minY = tmp
  }

  // Find the intersection of the segment's and rectangle's y-projections
  if(maxY > a_rectangleMaxY)
    maxY = a_rectangleMaxY

  if (minY < a_rectangleMinY)
    minY = a_rectangleMinY

  // If Y-projections do not intersect return false
  if(minY > maxY)
    return false

  return true
}

score 1 · Answer 8 · answered Sep 19 '08 at 03:45

1

A quick Google search popped up a page with C++ code for testing the intersection.

Basically it tests the intersection between the line, and every border or the rectangle.

Rectangle and line intersection code

answered Sep 19 '08 at 03:45

Vincent McNabb

33,327
7
31
53

Scott · Answer 9 · 2012-07-26T18:48:26.383

I was looking at a similar problem and here's what I came up with. I was first comparing the edges and realized something. If the midpoint of an edge that fell within the opposite axis of the first box is within half the length of that edge of the outer points on the first in the same axis, then there is an intersection of that side somewhere. But that was thinking 1 dimensionally and required looking at each side of the second box to figure out.

It suddenly occurred to me that if you find the 'midpoint' of the second box and compare the coordinates of the midpoint to see if they fall within 1/2 length of a side (of the second box) of the outer dimensions of the first, then there is an intersection somewhere.

i.e. box 1 is bounded by x1,y1 to x2,y2
box 2 is bounded by a1,b1 to a2,b2

the width and height of box 2 is:
w2 = a2 - a1   (half of that is w2/2)
h2 = b2 - b1   (half of that is h2/2)
the midpoints of box 2 are:
am = a1 + w2/2
bm = b1 + h2/2

So now you just check if
(x1 - w2/2) < am < (x2 + w2/2) and (y1 - h2/2) < bm < (y2 + h2/2) 
then the two overlap somewhere.
If you want to check also for edges intersecting to count as 'overlap' then
 change the < to <=

Of course you could just as easily compare the other way around (checking midpoints of box1 to be within 1/2 length of the outer dimenions of box 2)

And even more simplification - shift the midpoint by your half lengths and it's identical to the origin point of that box. Which means you can now check just that point for falling within your bounding range and by shifting the plain up and to the left, the lower corner is now the lower corner of the first box. Much less math:

(x1 - w2) < a1 < x2
&&
(y1 - h2) < b1 < y2
[overlap exists]

or non-substituted:

( (x1-(a2-a1)) < a1 < x2 ) && ( (y1-(b2-b1)) < b1 < y2 ) [overlap exists]
( (x1-(a2-a1)) <= a1 <= x2 ) && ( (y1-(b2-b1)) <= b1 <= y2 ) [overlap or intersect exists]

The question is about line-rect intersection, not rect-rect. — NateS, Aug 17 '13 at 18:00

score 0 · Answer 10 · answered Jul 26 '12 at 19:12

coding example in PHP (I'm using an object model that has methods for things like getLeft(), getRight(), getTop(), getBottom() to get the outer coordinates of a polygon and also has a getWidth() and getHeight() - depending on what parameters were fed it, it will calculate and cache the unknowns - i.e. I can create a polygon with x1,y1 and ... w,h or x2,y2 and it can calculate the others)

I use 'n' to designate the 'new' item being checked for overlap ($nItem is an instance of my polygon object) - the items to be tested again [this is a bin/sort knapsack program] are in an array consisting of more instances of the (same) polygon object.

public function checkForOverlaps(BinPack_Polygon $nItem) {
  // grab some local variables for the stuff re-used over and over in loop
  $nX = $nItem->getLeft();
  $nY = $nItem->getTop();
  $nW = $nItem->getWidth();
  $nH = $nItem->getHeight();
  // loop through the stored polygons checking for overlaps
  foreach($this->packed as $_i => $pI) {
    if(((($pI->getLeft()  - $nW) < $nX) && ($nX < $pI->getRight())) &&
       ((($pI->getTop()  - $nH) < $nY) && ($nY < $pI->getBottom()))) {
      return false;
    }
  }
  return true;
}

score 0 · Answer 11 · answered Jul 27 '12 at 15:49

Some sample code for my solution (in php):

// returns 'true' on overlap checking against an array of similar objects in $this->packed
public function checkForOverlaps(BinPack_Polygon $nItem) {
  $nX = $nItem->getLeft();
  $nY = $nItem->getTop();
  $nW = $nItem->getWidth();
  $nH = $nItem->getHeight();
  // loop through the stored polygons checking for overlaps
  foreach($this->packed as $_i => $pI) {
    if(((($pI->getLeft() - $nW) < $nX) && ($nX < $pI->getRight())) && ((($pI->getTop() - $nH) < $nY) && ($nY < $pI->getBottom()))) {
      return true;
    }
  }
  return false;
}

score 0 · Answer 12 · answered Sep 19 '08 at 04:11

I did a little napkin solution..

Next find m and c and hence the equation y = mx + c

y = (Point2.Y - Point1.Y) / (Point2.X - Point1.X)

Substitute P1 co-ordinates to now find c

Now for a rectangle vertex, put the X value in the line equation, get the Y value and see if the Y value lies in the rectangle bounds shown below

(you can find the constant values X1, X2, Y1, Y2 for the rectangle such that)

X1 <= x <= X2 & 
Y1 <= y <= Y2

If the Y value satisfies the above condition and lies between (Point1.Y, Point2.Y) - we have an intersection. Try every vertex if this one fails to make the cut.

How to test if a line segment intersects an axis-aligned rectange in 2D?

12 Answers12

Linked