具有最大線段長度的直線和矩形的交點

Question

我有一個由斜率m表示的向量。然後是矩形（假定軸對齊），它由左上角和右下角表示。 當然，可能有許多斜率爲m的直線與給定的矩形相交。問題是要找出所有這些線中矩形內線截距長度最大的線。即如果該線在P1和P2處與矩形相交，則問題是找到P1P2的長度最大的線的方程。

我繼續這樣。讓這條線是：y = m * x + c。然後找出矩形每邊的交點，找出每對點之間的距離函數的最大值。但它只會給我線段的長度，似乎有很多角落案件需要處理。

任何人都可以請建議一個更好的方法來做到這一點。

在此先感謝。

Answer 1

想想看，就像你想縮放一個三角形以適應矩形內部一樣。考慮與基部寬度1.

我們知道，DY/DX =米

一個三角形，所以用相同的斜率三角形的高度爲m。

現在把你的矩形，並制定出適合在矩形內的三角形的最大規模。對於正瑪：

min(rectWidth, rectHeight/m) 

這是我們必須使用，以適應矩形內的三角形的規模。現在，它很容易與pytagoras定理得到交點

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

注意，有一個線這個長度可能有多個可能的解決方案的長度，是我們肯定積極M（三角形朝上），它將適合在矩形的左下部，和用於負米（三角形指向下方），它會適合在右上角。

因此，可以說您的矩形是由4個值了minX，MINY，maxX的中，美星

如果m是正數，線相交了minX MINY，並退出在

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

矩形如果m是消極的線相交於maxX的美星，並退出在

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

所有你需要處理的矩形現在爲0的斜率，這是微不足道的。