python - 寻找四边形内最大矩形拟合的简单算法

Question

我的问题来自于一个具体的应用:如果你想在现有的近矩形孔 ABCD 内安装一个矩形 window EFGH，并且你想要尽可能大的 window (你想为一个 window build 一个金属框架)现有建筑的开口几乎是完美的，但并不完全......)

我想在 python 2.7 中实现这一点，但首先我需要涵盖所有情况的协议(protocol) - 也许我不知道的 python 库(shapely？)可以帮助做到这一点？

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(您想要构建的窗口，它将是矩形)的宽度和高度，如果矩形与四边形的边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)中上方的水平线的交点，依此类推。