How to find the intersection point between a line and a rectangle?

Question

I have a line that goes from points A to B; I have (x, y) both points. I also have a rectangle centered in B and the width and height of the rectangle.

I need to find a point in a line that intersects a rectangle. Is there a formula that gives me (x, y) this point?

Answer 1

Point A is always outside the rectangle, and Point B is always in the center of the rectangle.

Assuming the rectangle is axially aligned, this makes things pretty simple:

The slope of the line is s = (Ay - By) / (Ax - Bx).

• If -h / 2 <= s * w / 2 <= h / 2, then the line intersects:
  • Right edge if Ax> Bx
  • Left edge if Ax <Bx.
• If -w / 2 <= (h / 2) / s <= w / 2, then the line intersects:
  • Top edge if Ay> By
  • Lower edge if Ay <K.

As soon as you know that the edge intersects, you know one coordinate: x = Bx ± w / 2 or y = By ± h / 2, depending on which edge you hit. Another coordinate is given by the expression y = By + s * w / 2 or x = Bx + (h / 2) / s.

Answer 2

You might want to check Graphic Graphs - this is a classic set of routines for graphics and includes many of the required algorithms. Although it is slightly outdated in C from algorithms, it is still sparkling, and it should be trivial to pass to other languages.

For your current task, simply create four lines for the rectangle and see which lines intersect with your line.

Answer 3

/** * Finds the intersection point between * * the rectangle * with parallel sides to the x and y axes * * the half-line pointing towards (x,y) * originating from the middle of the rectangle * * Note: the function works given min[XY] <= max[XY], * even though minY may not be the "top" of the rectangle * because the coordinate system is flipped. * Note: if the input is inside the rectangle, * the line segment wouldn't have an intersection with the rectangle, * but the projected half-line does. * Warning: passing in the middle of the rectangle will return the midpoint itself * there are infinitely many half-lines projected in all directions, * so let just shortcut to midpoint (GIGO). * * @param x:Number x coordinate of point to build the half-line from * @param y:Number y coordinate of point to build the half-line from * @param minX:Number the "left" side of the rectangle * @param minY:Number the "top" side of the rectangle * @param maxX:Number the "right" side of the rectangle * @param maxY:Number the "bottom" side of the rectangle * @param validate:boolean (optional) whether to treat point inside the rect as error * @return an object with x and y members for the intersection * @throws if validate == true and (x,y) is inside the rectangle * @author TWiStErRob * @see <a href="http://stackoverflow.com/a/31254199/253468">source</a> * @see <a href="http://stackoverflow.com/a/18292964/253468">based on</a> */ function pointOnRect(x, y, minX, minY, maxX, maxY, validate) { //assert minX <= maxX; //assert minY <= maxY; if (validate && (minX < x && x < maxX) && (minY < y && y < maxY)) throw "Point " + [x,y] + "cannot be inside " + "the rectangle: " + [minX, minY] + " - " + [maxX, maxY] + "."; var midX = (minX + maxX) / 2; var midY = (minY + maxY) / 2; // if (midX - x == 0) -> m == ±Inf -> minYx/maxYx == x (because value / ±Inf = ±0) var m = (midY - y) / (midX - x); if (x <= midX) { // check "left" side var minXy = m * (minX - x) + y; if (minY <= minXy && minXy <= maxY) return {x: minX, y: minXy}; } if (x >= midX) { // check "right" side var maxXy = m * (maxX - x) + y; if (minY <= maxXy && maxXy <= maxY) return {x: maxX, y: maxXy}; } if (y <= midY) { // check "top" side var minYx = (minY - y) / m + x; if (minX <= minYx && minYx <= maxX) return {x: minYx, y: minY}; } if (y >= midY) { // check "bottom" side var maxYx = (maxY - y) / m + x; if (minX <= maxYx && maxYx <= maxX) return {x: maxYx, y: maxY}; } // edge case when finding midpoint intersection: m = 0/0 = NaN if (x === midX && y === midY) return {x: x, y: y}; // Should never happen :) If it does, please tell me! throw "Cannot find intersection for " + [x,y] + " inside rectangle " + [minX, minY] + " - " + [maxX, maxY] + "."; } (function tests() { var left = 100, right = 200, top = 50, bottom = 150; // a square, really var hMiddle = (left + right) / 2, vMiddle = (top + bottom) / 2; function intersectTestRect(x, y) { return pointOnRect(x,y, left,top, right,bottom, true); } function intersectTestRectNoValidation(x, y) { return pointOnRect(x,y, left,top, right,bottom, false); } function checkTestRect(x, y) { return function() { return pointOnRect(x,y, left,top, right,bottom, true); }; } QUnit.test("intersects left side", function(assert) { var leftOfRect = 0, closerLeftOfRect = 25; assert.deepEqual(intersectTestRect(leftOfRect, 25), {x:left, y:75}, "point above top"); assert.deepEqual(intersectTestRect(closerLeftOfRect, top), {x:left, y:80}, "point in line with top"); assert.deepEqual(intersectTestRect(leftOfRect, 70), {x:left, y:90}, "point above middle"); assert.deepEqual(intersectTestRect(leftOfRect, vMiddle), {x:left, y:100}, "point exact middle"); assert.deepEqual(intersectTestRect(leftOfRect, 130), {x:left, y:110}, "point below middle"); assert.deepEqual(intersectTestRect(closerLeftOfRect, bottom), {x:left, y:120}, "point in line with bottom"); assert.deepEqual(intersectTestRect(leftOfRect, 175), {x:left, y:125}, "point below bottom"); }); QUnit.test("intersects right side", function(assert) { var rightOfRect = 300, closerRightOfRect = 250; assert.deepEqual(intersectTestRect(rightOfRect, 25), {x:right, y:75}, "point above top"); assert.deepEqual(intersectTestRect(closerRightOfRect, top), {x:right, y:75}, "point in line with top"); assert.deepEqual(intersectTestRect(rightOfRect, 70), {x:right, y:90}, "point above middle"); assert.deepEqual(intersectTestRect(rightOfRect, vMiddle), {x:right, y:100}, "point exact middle"); assert.deepEqual(intersectTestRect(rightOfRect, 130), {x:right, y:110}, "point below middle"); assert.deepEqual(intersectTestRect(closerRightOfRect, bottom), {x:right, y:125}, "point in line with bottom"); assert.deepEqual(intersectTestRect(rightOfRect, 175), {x:right, y:125}, "point below bottom"); }); QUnit.test("intersects top side", function(assert) { var aboveRect = 0; assert.deepEqual(intersectTestRect(80, aboveRect), {x:115, y:top}, "point left of left"); assert.deepEqual(intersectTestRect(left, aboveRect), {x:125, y:top}, "point in line with left"); assert.deepEqual(intersectTestRect(120, aboveRect), {x:135, y:top}, "point left of middle"); assert.deepEqual(intersectTestRect(hMiddle, aboveRect), {x:150, y:top}, "point exact middle"); assert.deepEqual(intersectTestRect(180, aboveRect), {x:165, y:top}, "point right of middle"); assert.deepEqual(intersectTestRect(right, aboveRect), {x:175, y:top}, "point in line with right"); assert.deepEqual(intersectTestRect(220, aboveRect), {x:185, y:top}, "point right of right"); }); QUnit.test("intersects bottom side", function(assert) { var belowRect = 200; assert.deepEqual(intersectTestRect(80, belowRect), {x:115, y:bottom}, "point left of left"); assert.deepEqual(intersectTestRect(left, belowRect), {x:125, y:bottom}, "point in line with left"); assert.deepEqual(intersectTestRect(120, belowRect), {x:135, y:bottom}, "point left of middle"); assert.deepEqual(intersectTestRect(hMiddle, belowRect), {x:150, y:bottom}, "point exact middle"); assert.deepEqual(intersectTestRect(180, belowRect), {x:165, y:bottom}, "point right of middle"); assert.deepEqual(intersectTestRect(right, belowRect), {x:175, y:bottom}, "point in line with right"); assert.deepEqual(intersectTestRect(220, belowRect), {x:185, y:bottom}, "point right of right"); }); QUnit.test("intersects a corner", function(assert) { assert.deepEqual(intersectTestRect(left-50, top-50), {x:left, y:top}, "intersection line aligned with top-left corner"); assert.deepEqual(intersectTestRect(right+50, top-50), {x:right, y:top}, "intersection line aligned with top-right corner"); assert.deepEqual(intersectTestRect(left-50, bottom+50), {x:left, y:bottom}, "intersection line aligned with bottom-left corner"); assert.deepEqual(intersectTestRect(right+50, bottom+50), {x:right, y:bottom}, "intersection line aligned with bottom-right corner"); }); QUnit.test("on the corners", function(assert) { assert.deepEqual(intersectTestRect(left, top), {x:left, y:top}, "top-left corner"); assert.deepEqual(intersectTestRect(right, top), {x:right, y:top}, "top-right corner"); assert.deepEqual(intersectTestRect(right, bottom), {x:right, y:bottom}, "bottom-right corner"); assert.deepEqual(intersectTestRect(left, bottom), {x:left, y:bottom}, "bottom-left corner"); }); QUnit.test("on the edges", function(assert) { assert.deepEqual(intersectTestRect(hMiddle, top), {x:hMiddle, y:top}, "top edge"); assert.deepEqual(intersectTestRect(right, vMiddle), {x:right, y:vMiddle}, "right edge"); assert.deepEqual(intersectTestRect(hMiddle, bottom), {x:hMiddle, y:bottom}, "bottom edge"); assert.deepEqual(intersectTestRect(left, vMiddle), {x:left, y:vMiddle}, "left edge"); }); QUnit.test("validates inputs", function(assert) { assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center"); assert.throws(checkTestRect(hMiddle-10, vMiddle-10), /cannot be inside/, "top left of center"); assert.throws(checkTestRect(hMiddle-10, vMiddle), /cannot be inside/, "left of center"); assert.throws(checkTestRect(hMiddle-10, vMiddle+10), /cannot be inside/, "bottom left of center"); assert.throws(checkTestRect(hMiddle, vMiddle-10), /cannot be inside/, "above center"); assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center"); assert.throws(checkTestRect(hMiddle, vMiddle+10), /cannot be inside/, "below center"); assert.throws(checkTestRect(hMiddle+10, vMiddle-10), /cannot be inside/, "top right of center"); assert.throws(checkTestRect(hMiddle+10, vMiddle), /cannot be inside/, "right of center"); assert.throws(checkTestRect(hMiddle+10, vMiddle+10), /cannot be inside/, "bottom right of center"); assert.throws(checkTestRect(left+10, vMiddle-10), /cannot be inside/, "right of left edge"); assert.throws(checkTestRect(left+10, vMiddle), /cannot be inside/, "right of left edge"); assert.throws(checkTestRect(left+10, vMiddle+10), /cannot be inside/, "right of left edge"); assert.throws(checkTestRect(right-10, vMiddle-10), /cannot be inside/, "left of right edge"); assert.throws(checkTestRect(right-10, vMiddle), /cannot be inside/, "left of right edge"); assert.throws(checkTestRect(right-10, vMiddle+10), /cannot be inside/, "left of right edge"); assert.throws(checkTestRect(hMiddle-10, top+10), /cannot be inside/, "below top edge"); assert.throws(checkTestRect(hMiddle, top+10), /cannot be inside/, "below top edge"); assert.throws(checkTestRect(hMiddle+10, top+10), /cannot be inside/, "below top edge"); assert.throws(checkTestRect(hMiddle-10, bottom-10), /cannot be inside/, "above bottom edge"); assert.throws(checkTestRect(hMiddle, bottom-10), /cannot be inside/, "above bottom edge"); assert.throws(checkTestRect(hMiddle+10, bottom-10), /cannot be inside/, "above bottom edge"); }); QUnit.test("doesn't validate inputs", function(assert) { assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle-10), {x:left, y:top}, "top left of center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle), {x:left, y:vMiddle}, "left of center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle+10), {x:left, y:bottom}, "bottom left of center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle-10), {x:hMiddle, y:top}, "above center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle), {x:hMiddle, y:vMiddle}, "center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle+10), {x:hMiddle, y:bottom}, "below center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle-10), {x:right, y:top}, "top right of center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle), {x:right, y:vMiddle}, "right of center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle+10), {x:right, y:bottom}, "bottom right of center"); }); })(); 

 <link href="https://code.jquery.com/qunit/qunit-2.3.2.css" rel="stylesheet"/> <script src="https://code.jquery.com/qunit/qunit-2.3.2.js"></script> <div id="qunit"></div> 

Answer 4

Here is a solution in Java that returns true if a line segment (first 4 parameters) intersects a rectangle aligned on the axis (last 4 parameters). It would be trivial to return the intersection point instead of Boolean. It works by first checking to see if it is completely outside, otherwise using the linear equation y=m*x+b . We know that the lines that make up the rectangle are aligned along the axis, so checking is easy.

 public boolean aabbContainsSegment (float x1, float y1, float x2, float y2, float minX, float minY, float maxX, float maxY) { // Completely outside. if ((x1 <= minX && x2 <= minX) || (y1 <= minY && y2 <= minY) || (x1 >= maxX && x2 >= maxX) || (y1 >= maxY && y2 >= maxY)) return false; float m = (y2 - y1) / (x2 - x1); float y = m * (minX - x1) + y1; if (y > minY && y < maxY) return true; y = m * (maxX - x1) + y1; if (y > minY && y < maxY) return true; float x = (minY - y1) / m + x1; if (x > minX && x < maxX) return true; x = (maxY - y1) / m + x1; if (x > minX && x < maxX) return true; return false; } 

You can use a shortcut if the beginning or end of the segment is inside the rectangle, but it's probably best to just do the math, which will always return true if inside or both ends of the segment are inside. If you need a shortcut anyway, paste the code below after checking "completely outside".

 // Start or end inside. if ((x1 > minX && x1 < maxX && y1 > minY && y1 < maxY) || (x2 > minX && x2 < maxX && y2 > minY && y2 < maxY)) return true; 

Answer 5

I will not give you a program for this, but here is how you can do it:

• calculate line angle
• calculate the angle of a line from the center of a rectangle to one of its angles
• based on the angles determine which side the line intersects the rectangle
• calculate the intersection between the side of the rectangle and the line

Answer 6

I am not a fan of mathematics and I don’t particularly like translating things from other languages ​​if others have already done so, so when I finish the boring translation job, I add it to the article that led me to the code. So no one does the double job.

So, if you want to have this intersection code in C #, look here http://dotnetbyexample.blogspot.nl/2013/09/utility-classes-to-check-if-lines-andor.html

Answer 7

Another option that you can consider especially if you plan to test many lines with the same rectangle is to transform your coordinate system so that the axes coincide with the diagonals of the rectangle. Then, when your line or ray starts at the center of the rectangle, you can determine the angle, then you can determine which segment it will intersect at the angle (i.e. <90deg seg 1, 90deg <180deg seg 2, etc.), Then, of course, you have to go back to the original coordinate system

Although this seems like a lot of work, the transformation matrix and its inverse can be calculated once and then reused. It also more simply extends to larger rectangles, where you will need to consider quadrants and intersections with faces in 3D, etc.

Answer 8

I don't know if this is better, but what you can do is figure out the proportion of the line that is inside the rectangle. You can get this from the width of the rectangle and the difference between the x coordinates of the A and B coordinates (or the height and y, depending on the width and height, you can check which case applies, and the other to the extension of the side of the rectangle). When you have this, just take this proportion of the vector from B to A and you have the coordinates of the intersection point.

Answer 9

Here is a somewhat detailed method that returns the intersection intervals between a (infinite) line and a rectangle using only basic math:

 // Line2 - 2D line with origin (= offset from 0,0) and direction // Rectangle2 - 2D rectangle by min and max points // Contacts - Stores entry and exit times of a line through a convex shape Contacts findContacts(const Line2 &line, const Rectangle2 &rect) { Contacts contacts; // If the line is not parallel to the Y axis, find out when it will cross // the limits of the rectangle horizontally if(line.Direction.X != 0.0f) { float leftTouch = (rect.Min.X - line.Origin.X) / line.Direction.X; float rightTouch = (rect.Max.X - line.Origin.X) / line.Direction.X; contacts.Entry = std::fmin(leftTouch, rightTouch); contacts.Exit = std::fmax(leftTouch, rightTouch); } else if((line.Offset.X < rect.Min.X) || (line.Offset.X >= rect.Max.X)) { return Contacts::None; // Rectangle missed by vertical line } // If the line is not parallel to the X axis, find out when it will cross // the limits of the rectangle vertically if(line.Direction.Y != 0.0f) { float topTouch = (rectangle.Min.Y - line.Offset.Y) / line.Direction.Y; float bottomTouch = (rectangle.Max.Y - line.Offset.Y) / line.Direction.Y; // If the line is parallel to the Y axis (and it goes through // the rectangle), only the Y axis needs to be taken into account. if(line.Direction.X == 0.0f) { contacts.Entry = std::fmin(topTouch, bottomTouch); contacts.Exit = std::fmax(topTouch, bottomTouch); } else { float verticalEntry = std::fmin(topTouch, bottomTouch); float verticalExit = std::fmax(topTouch, bottomTouch); // If the line already left the rectangle on one axis before entering it // on the other, it has missed the rectangle. if((verticalExit < contacts.Entry) || (contacts.Exit < verticalEntry)) { return Contacts::None; } // Restrict the intervals from the X axis of the rectangle to where // the line is also within the limits of the rectangle on the Y axis contacts.Entry = std::fmax(verticalEntry, contacts.Entry); contacts.Exit = std::fmin(verticalExit, contacts.Exit); } } else if((line.Offset.Y < rect.Min.Y) || (line.Offset.Y > rect.Max.Y)) { return Contacts::None; // Rectangle missed by horizontal line } return contacts; } 

This approach provides a high degree of numerical stability (the intervals in all cases are the result of one subtraction and division), but includes some branching.

For a line segment (with start and end points) you need to specify the start point of the segment as the origin and direction, end - start . Calculating the coordinates of two intersections is simple as entryPoint = origin + direction * contacts.Entry and exitPoint = origin + direction * contacts.Exit .