algorithm - 任意凸多边形中具有固定纵横比的最大对齐矩形？

Question

如何计算任意凸多边形中具有固定纵横比的最大对齐矩形的宽度/高度？

此图像显示了不同凸多边形（黑色）中的此类矩形（红色）的示例：

.

我发现了关于主题的不同论文，但它们不适合我的限制。这很奇怪，因为他们应该显着简化算法，但不幸的是我没有找到任何线索。

标签： algorithmgeometrycomputational-geometryconvex-optimization

Answer 1

固定比率确实简化了问题，因为现在有一个线性程序。

您想找到 x1, y1, x2, y2 以最大化 x2 − x1 受限于 (x2 − x1) h = w (y2 − y1) 的约束，其中纵横比为 w:h，并且对于每个线性不等式定义凸多边形，每个点 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 满足它。

例如，考虑这个凸多边形：

具有四个点(x_1, y_1) , (x_1, y_2) , (x_2, y_2) , (x_2, y_1)的矩形的线性规划，纵横比r = w / h并与上面的多边形内接如下：

理论上，有专门的算法用于在线性时间内运行的低维线性规划。在实践中，您可以使用求解器。如果您想编写自己的代码，则可以使用单纯形法，但梯度下降更简单。

首先让我们摆脱等式约束和一个变量，通过在变量 x, y, z 上最大化 z 来满足 x1 = (x - wz), y1 = (y - hz), x2 = ( x + wz), y2 = (y + hz)。其次，让我们用这些约束换取一个客观的术语。通常，多边形内的点约束看起来像（到半平面的有符号距离）≤ 0。相反，我们将对目标应用惩罚项。设 α > 0 为参数。新项是 -exp(α (到半平面的有符号距离))。如果有符号距离为负（该点在半平面内），则随着 α 趋于无穷大，惩罚将变为零。如果有符号距离为正，则惩罚为负无穷大。如果我们使 α 足够大，那么变换后的问题的最优解将是近似可行的。

这就是它在 Python 中的样子。我不是持续优化专家，所以请谨慎购买。

# Aspect ratio.
w = 3
h = 2

# Represented as intersection of half-spaces a*x + b*y - c <= 0 given below as
# (a, b, c). For robustness, these should be scaled so that a**2 + b**2 == 1,
# but it's not strictly necessary.
polygon = [(1, 1, 20), (1, -2, 30), (-2, 1, 40)]

# Initial solution -- take the centroid of three hull points. Cheat by just
# using (0, 0) here.
x, y, z = (0, 0, 0)

from math import exp

# Play with these.
alpha = 10
rate = 0.02

for epoch in range(5):
    for iteration in range(10 ** epoch, 10 ** (epoch + 1)):
        # Compute the gradient of the objective function. Absent penalties, we
        # only care about how big the rectangle is, not where.
        dx, dy, dz = (0, 0, 1)
        # Loop through the polygon boundaries, applying penalties.
        for a, b, c in polygon:
            for u in [-w, w]:
                for v in [-h, h]:
                    term = -exp(alpha * (a * (x + u * z) + b * (y + v * z) - c))
                    dx += alpha * a * term
                    dy += alpha * b * term
                    dz += alpha * (a * u + b * v) * term
        x += rate * dx
        y += rate * dy
        z += rate * dz
    print(x, y, z)