How to test if a line segment intersects an axis-a

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.

Answer 1

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;
  }

Answer 2

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

Answer 3

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;
    }
}

Answer 4

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.

Answer 5

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;
}

Answer 6

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