这可能是一个更注重数学的问题，但想在这里问是因为它是在 CS 环境中。我正在寻找在另一个（任意）四边形内内接一个矩形，内接四边形具有最大的高度和宽度。因为我认为算法会相似，所以我想看看我是否也可以用圆圈来做到这一点。
更清楚地听到我的意思是以边界四边形为例。
以下是我试图实现的两个铭文最大化示例：
我做了一些初步的搜索，但没有找到任何确定的东西。似乎某种形式的动态编程可能是解决方案。看来这应该是一个线性优化问题，应该比我发现的更常见，也许我正在寻找错误的术语。
注意： 对于内接正方形，假设我们知道我们正在寻找的目标 w/h 比（例如 4:3）。对于四边形，假设边不会交叉并且是凹形的（如果这样可以简化计算）。
1）圈。
对于三角形，这是学校课程中的标准数学问题。
对于四边形，您会注意到最大内圆将至少接触它的三个边。因此，采用三个边的每个组合并解决每个三角形的问题。
必须单独考虑平行边的情况（因为它们不形成三角形），但这并不是非常困难。
2) 矩形。
你不能有“最大的高度和宽度”，你需要选择另一个标准。例如，在您的图片上，我可以通过降低高度来增加宽度，反之亦然。
4岁的线程，但我在谷歌搜索我的问题时碰巧偶然发现了它。
我在当前的 CV 应用程序中遇到了这样的问题。我想出了一个简单但有点笨拙的解决方案来找到最大的。虽然不完全相同，因为我在没有固定边比的情况下最大化了矩形的面积。
我还不知道我的解决方案是否找到了最佳方案，或者它是否适用于所有情况。我也认为应该有更有效的方法，所以我期待您的意见。
首先，假设一组 4 个点形成我们的（凸）四边形：
x y
P1 -2 -5
P2 1 7
P3 4 5
P4 3 -2
对于此过程，最左边的点是 P1，以下点按顺时针方向编号。它看起来像这样：
然后我们创建点之间的线性函数。对于每个函数，我们必须知道斜率 k 和到 0 的距离：d。k 只是两点的 Y 差除以 X 的差。d 可以通过求解 d 的线性函数来计算。所以我们有
k=dy/dx
d=y1-k*x1
我们还需要反函数。
k_inv = 1/k
d_inv = -d/k
然后我们为四边形的每一边创建函数和反函数
k d k d
p1p2 4 3 p1p2_inv 0.25 -0.75
p2p3 -0.67 7.67 p2p3_inv -1.5 11.5
p3p4 7 -23 p3p4_inv 0.14 3.29
p4p1 0.6 -3.8 p4p1_inv 1.67 6.33
如果我们有完全水平或垂直的线，我们最终会在函数或逆函数之一中得到 DIV/0，因此我们需要单独处理这种情况。
现在我们遍历由两个函数包围的所有角，这些函数具有 ak 和带有不同符号的斜率。在我们的例子中，这将是 P2 和 P3。
我们从 P2 开始，以适当的步长迭代 P2 与 P1 和 P3 中较高的一个之间的 y 值，并使用反函数计算函数之间在水平方向上的距离。这会给我们矩形的一侧
a=p2p3_inv(y)-p1p2_inv(y)
在两个 x 值 x = p2p3_inv(y) 和 x = p1p2_inv(y) 处，我们然后计算 y 与两个相反函数的差异，并将到当前 y 位置的距离作为矩形第二边的候选。
b_candidate_1 = y-p4p1(p2p3_inv(y))
b_candidate_2 = y-p4p1(p1p2_inv(y))
b_candidate_3 = y-P3p4(p2p3_inv(y))
b_candidate_4 = y-P3p4(p1p2_inv(y))
四个参数中较小的一个将是 b 面的解决方案。该区域显然变为 a*b。
我在excel中做了一个简单的例子来演示：
这里的最小 b 是 6.9，所以解决方案的右上角在 p2p3 上，矩形在水平方向上延伸 a，在垂直方向上分别延伸到左侧和底部。
因此矩形的四个点是
Rect x y
R1 0.65 -1.3
R2 0.65 5.6
R3 3.1 5.6
R4 3.1 -1.3
我将不得不将其放入 C++ 代码中，并运行一些测试以查看解决方案是否普遍化，或者这是否只是“运气”。
我认为也应该可以用函数替换 A=a*b 中的 a 和 b 并将其放入一个线性公式中，该公式必须在 p1p2 仅在 P1 和 P2 之间定义等条件下最大化...