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

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.

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) xTR and x2 > xTR), no intersection (line is to right of rectangle).

If (x1 yTR and y2 > yTR), no intersection (line is above rectangle). If (y1 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.

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 at 21:02.

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.

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.

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.

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 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 be = 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 maxY) // If Y-projections do not intersect return false { return false; } return true; }.

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 rectX + rectWidth) { out |= OUT_RIGHT; } if (rectHeight 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; } }.

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 Y) - we have an intersection. Try every vertex if this one fails to make the cut.

Because the box is axis-aligned, all you need to do is to check for interval intersection in each coordinate. Here is an example in python, with some tests. Note that it is generic for N dimensions, and it is the same algorithm for box-box intersection: def are_intervals_intersecting(a0, a1, b0, b1): ''' @param a0: float @param a1: float @param b0: float @param b1: float ''' if (a1.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.