在任意凸多边形中，最大的固定长宽比对齐矩形是什么？

Question

在任意凸多边形中，最大的固定长宽比对齐矩形是什么？

algorithmgeometrycomputational-geometryconvex-optimization

3

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

下图展示了不同凸多边形中此类矩形（红色）的示例（黑色）： are presented on this image

我找到了一些与此相关的文章，但它们并不适合我的限制条件。这很奇怪，因为它们应该显著简化算法，但不幸的是我没有找到任何线索。

- grom

2

不失一般性，你可以解决一个正方形的问题。 - user1196549

2个回答

2

提示：

不失一般性，矩形可以是正方形（必要时拉伸空间）。

然后，在Chebyshev度量（L∞）下，解决方案由到多边形的距离图的最高点给出。它可以从中轴变换中确定，而中轴变换本身则是从Voronoi图获得的。

- user1196549

我打算尝试你的方法。谢谢。 - grom

1

@grom：注意，该度量标准是非标准的。 - user1196549

对不起，但我卡住了。我还需要深入挖掘，以理解如何根据切比雪夫度量构建沃罗诺伊图。看起来这是一个相当困难的任务。 - grom

1

@grom：一旦你了解了线段或角度的几何图形，它应该变得更容易。 - user1196549

唉，这个任务因为未知的原因被延迟了。所以我接受了David的答案。我认为它是值得的。谢谢你的帮助。 - grom

1

@grom: 别担心，我只是给了一个提示。我知道完整的解决方案很艰巨。 - user1196549

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

固定比例简化了问题，因为现在有一个线性规划。

你想找到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)