尋找四邊形內最大的矩形

Question

最近，我掃描了很多專輯封面，試圖將我的音樂收藏數字化。掃描後的默認步驟是旋轉和裁剪。

對於旋轉，重要的是找到一個或多個參考線。旋轉之後，「正常」線將大致水平（或垂直），奇數線將稍微傾斜。兩個「不同」的旋轉可以區分

注：這兩個四邊形是兩個專輯封面。您可以將專輯中的兩行代碼想象爲兩行打印行。所有參考線都以粗體顯示。您可能想知道爲什麼專輯封面不僅僅是矩形，而且請注意，這張圖片非常昂貴。也就是說，如果你仔細看過專輯封面，你會發現他們很少接近矩形。

在情況A中，很清楚，大多數蓋板邊緣是平行的和形式90度角，和/或印刷對象過於傾斜，其指示所述打印本身是傾斜的。在這兩種情況下，我都可以更好地使用封面邊緣作爲參考。

在情況B中，大部分線似乎不規則和打印似乎好。然後我更好地使用打印的對象作爲參考。

總之，這主要是一個直觀的過程。

雖然上述是不是我認爲這將是有益的你先了解背景信息的實際問題的一部分。我們現在已經進入了剪裁階段，這一直是我的煩惱。

我的問題很簡單：如果我必須裁剪所有專輯封面，我怎麼能裁剪以這樣一種方式，它讓我的專輯封面上最大的部分？換句話說，我怎樣才能找到四個值一起構成四邊形內最大可能的矩形？

唯一的條件是該矩形必須是平行於基準線，即水平的。

Answer 1

如果您接受指定的矩形將與在現實世界中的X和Y軸對準的約束，而不是在一些傾斜，你可以做以下

Given that point contains values x,y 
Given quadrilateral roughly formed by 

    A 
        B 

     C   D 

A rectangle may be formed via the following 

leftX = max(A.x,C.x) 
topY = min(A.y,B.y) 
rightX = min(B.x,D.x) 
botY = max(C.y,D.y) 

rectA = point(leftX, topY) 
rectB = point(rightX, topY) 
rectC = point(leftX, botY) 
rectD = point(rightX, botY)