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) of both points. I also have a rectangle that's centered at B and the width and height of the rectangle.

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

Solution 1

The point A is always outside of the rectangle and the point B is always at the center of the rectangle

Assuming the rectangle is axis-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:
  • The right edge if Ax > Bx
  • The left edge if Ax < Bx.
• If -w/2 <= (h/2)/s <= w/2 then the line intersects:
  • The top edge if Ay > By
  • The bottom edge if Ay < By.

Once you know the edge it intersects you know one coordinate: x = Bx ± w/2 or y = By ± h/2 depending on which edge you hit. The other coordinate is given by y = By + s * w/2 or x = Bx + (h/2)/s.

Solution 2

/**
 * 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's 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
 * @licence Dual CC0/WTFPL/Unlicence, whatever floats your boat
 * @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>

Solution 3

You might want to check out Graphics Gems - this is a classic set of routines for graphics and includes many of the algorithms required. Although it's in C and slightly dated the algorithms still sparkle and it should be trivial to transfer to other languages.

For your current problem the just create the four lines for the rectangle and see which intersect your given line.

Solution 4

Here is a solution in Java that returns true if a line segment (the first 4 parameters) intersects an axis aligned rectangle (the last 4 parameters). It would be trivial to return the intersection point instead of a boolean. It works by first checking if completely outside, else using the line equation y=m*x+b. We know the lines that make up the rectangle are axis aligned, so the checks are 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;
}

It is possible to shortcut if the start or end of the segment is inside the rectangle, but probably it is better to just do the math, which will always return true if either or both segment ends are inside. If you want the shortcut anyway, insert the code below after the "completely outside" check.

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

Solution 5

Here is a solution that works for me. I assume that the rect is aligned to the axes.

Data:

// Center of the Rectangle
let Cx: number
let Cy: number
// Width
let w: number
// Height
let h: number

// Other Point
let Ax: number
let Ay: number

Now translate point A by the center of the rectangle so the rect is centered in O(0,0) and consider the problem in the first quarter (i.e. x > 0 and y > 0).

// Coordinates Translated
let Px = Math.abs(Ax - Cx)
let Py = Math.abs(Ay - Cy)

// Slope of line from Point P to Center
let Pm = Py / Px

// Slope of rectangle Diagonal
let Rm = h / w

// If the point is inside the rectangle, return the center
let res: [number, number] = [0, 0]

// Check if the point is inside and if so do not calculate
if (!(Px < w / 2 && Py < h / 2)) {

    // Calculate point in first quarter: Px >= 0 && Py >= 0
    if (Pm <= Rm) {
        res[0] = w / 2
        res[1] = (w * Pm) / 2
    } else {
        res[0] = h / (Pm * 2)
        res[1] = h / 2
    }

    // Set original sign 
    if (Ax - Cx < 0) res[0] *= -1
    if (Ay - Cy < 0) res[1] *= -1
}

// Translate back
return [res[0] + Cx, res[1] + Cy]

View more solutions

Comments

[pjnovas]

Great thanks!, this is what I was looking for. I moved it to javascript, here is the fiddle I used to test it jsfiddle.net/pjnovas/fPMG5 cheers!

[Johnner]

Thanks Joren, I'v made a fiddle of this algorithm: jsfiddle.net/524ctnfh It's seems right-left and top-bottom edges are swapped-around, so it should be: right: Ax < Bx; left: Ax > Bx; top: Ay < By; bottom: Ay > By;

[Johnner]

Sorry, I'v made some mistakes in the script, here is fixed version: jsfiddle.net/524ctnfh/1

[gzmask]

i can spot couple potential divide by zeros here

[NateS]

@gzmask It's true, but the method still appears to return the correct values for all inputs (in Java and JavaScript x/0=Infinity and x/Infinity=0). See here.

[TWiStErRob]

This is too far from what the OP asked.

[TWiStErRob]

I added a specialized version of this with all "trivial" stuff and "shortcuts": stackoverflow.com/a/31254199/253468

[TWiStErRob]

An implementation of a similar one in JavaScript: stackoverflow.com/a/31254199/253468

[Joren]

@Johnner: Assuming a standard coordinate system where x increases left-to-right, then Ax < Bx definitely implies that point A is to the left of the rectangle with center B (and Ax > Bx => to the right). Top-bottom could indeed be flipped depending on your coordinate system convention. I'm using a right-handed coordinate system where y increases bottom-to-top (as is standard in mathematics), while you're probably thinking of a left-handed coordinate system where y increases top-to-bottom (as is standard in graphics & UI programming).

[cp.engr]

This answer is incomplete. OP says he "need[s] to find the point in the line that intersects the rectangle" - not just which side of the rectangle it intersects.

[Joren]

@cp.engr Once you know the edge it intersects you know one coordinate: x = Bx ± w/2 or y = By ± h/2 depending on which edge you hit. The other coordinate is given by y = By + s * w/2 or x = Bx + (h/2)/s.

[cp.engr]

@Joren, I don't see how that follows. Are you assuming the intersection is perpendicular? OP doesn't say it is.

[Joren]

@cp.engr: No, but I am assuming the rectangle is axis-aligned.

[cp.engr]

@Joren, oh, I didn't read your last sentence of your previous comment carefully enough. I suggest you add that info to your answer, with explanation. Thanks.

[Mark]

Excellent answer. I just shamelessly stole your function for this question and worked like a charm.

[TWiStErRob]

@Mark Attribution is never shameless, and way better than a link-only answer ;)

[Narek]

Thank you for the answer. But this has a bit of error in it. It is a sign error. To fix it you need to change y = By + s * w/2 or x = Bx + (h/2)/s to something else.

[Lara]

There is an error I cannot track inside the (xY > xX)

[Anthony]

@Lara wdym by and error you "cannot track" ? Do you mean an error upon compilation, or an error regarding the result yielded ? Have you c/p'ed the code, or have you translated to your language of choice ? Are you sure your points are all in positions compatible with the assumptions I made to the problem ?

[Lara]

The code works when the line crosses above and below but not when the line crosses from the left or right of the rectangle. In that case, yE is correctly calculated but xE is not (it becomes displaced increasingly away). I cannot figure out why, i.e., cannot track down the error other than it is at that if. My mistake somehow, no doubt. Here is my implementation of your algorithm: pastebin.com/6xPnKMAB

[Ti Hausmann]

Warning: this returns false if the line crosses exactly the corner. jsfiddle.net/obgxhyku

[vidstige]

What if the line is horizontal or vertical?

[canbax]

That's neat, it's what I need ;)

[Shashi3456643]

It works fine. Intersection point is correct