找到四边形内最大的矩形的简单算法

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）的上部，等等。