找到四邊形內最大的矩形的簡單算法

Question

我的問題來自一個具體的應用：如果你想在現有的近矩形孔ABCD中安裝一個矩形窗口EFGH，並且你想用最大的可能的窗口（你想建立一個金屬框架的開放幾乎完美，但不完全...）

我想在Python 2.7中實現這一點，但首先我需要的協議，涵蓋所有案例 - 可能是我不知道的一個python庫（很好？）可以幫助做到這一點？

A________D 
| a d | 
|  | 
|  | 
| b c | 
B________C 

E_______H 
|  | 
|  | 
|  | 
F_______G 

你有一個近乎直角四邊形ABCD（孔）

你知道各方AB, BC, CD, AD和對角線AC, BD，從而得益於鋁喀什定理和一些三角還知道所有4個角a, b, c, d

如何計算寬度和最大的矩形EFGH（要建立窗口，這將是矩形）的高度，能適合在T他是四邊形的，如果矩形的邊FG是平行於到邊的BC的四邊形？

（BC對應於開口的水平底部部分，其中FG - 窗口的底部 - 立場）。

A__________D 
|E________H| 
||  || 
||  || 
||  || 
||  || 
BF________GC 

Answer 1

這是關閉我的頭頂，所以要警惕空頭。

首先旋轉ABCD，使BC邊水平。然後，您想要將一個軸對齊的矩形放入旋轉後的形狀中。最後，如果你需要E，F，G，H的座標，你應該旋轉矩形通過第一步中使用的角度的負值;如果您只需要寬度和高度，您可以將它們從軸對齊的矩形中取出。

爲了適應軸排列的矩形（我將使用的名字A，B等爲旋轉的四邊形的頂點）

找到最右邊的最左邊的兩個點（A和B），並調用這個W和兩個上面點（A和D）中較低的一個並稱爲X.那麼點E將是通過W的垂直線與通過X的水平線的交點。

類似地，G是交點垂直線穿過兩個最右點（D和C）的最左邊，水平線穿過兩個較低點（B和C）的上部，等等。