Intersection of line and rectangle with maximum segment length

Question

I have a vector represented by the slope m. Then there is rectangle (assume axis aligned), which is represented by top-left and bottom-right corner. Of course, there may be many lines with slope m and intersecting the given rectangle. The problem is to find out the line whose length of line intercept inside the rectangle is maximum among all such lines. i.e., if the line intersects rectangle at P1 and P2, then the problem is to find the equation of line for which length of P1P2 is maximum.

I proceeded like this. Let the line is: y = m*x + c. Then find out the intersection with each side of rectangle and finding out the maxima for distance function between each pair of points. But it will only give me the length of line segment and there seem to be many corner cases to handle.

Could anyone please suggest a better way to do this.

Thanks in advance.

Matt Esch Matt Esch · Accepted Answer · 2012-03-18T17:58:49

Think about it like you want to scale a triangle to fit inside the rectangle. Consider a triangle with base width 1.

we know that dy/dx = m, so the height of the triangle with the same slope is m.

Now take your rectangle and work out the maximum scale that fits the triangle inside the rectangle. For positive m:

min(rectWidth, rectHeight/m)

This is the scale we have to use to fit the triangle inside the rectangle. Now it's easy with pytagoras' theorem to get the length of the intersection

scale = min(rectWidth, abs(m/rectHeight)) // m could be negative so we take abs
length = sqrt(scale*scale + scale*m*scale*m)

Note that there are potentially many possible solutions for a line of this length, be we are certain that for positive m (triangle pointing up) it will fit in the bottom left of the rectangle, and for negative m (triangle pointing down) it will fit in the top right.

So lets say your rectangle is made up of 4 values minX, minY, maxX, maxY

if m is positive, the line intersects at minX minY, and exits the rectangle at

[minX + scale, minY + (m * scale)]

and if m is negative the line intersects at maxX maxY and exits the rectangle at

[maX - scale, maxY + (m * scale)] (noting that m is negative)

All you need to handle now is slope of 0, which is trivial.

Intersection of line and rectangle with maximum segment length

1 Answers