任意凸多边形中具有固定纵横比的最大对齐矩形?
The largest aligned rectangular with fixed aspect ratio in an arbitrary convex polygon?
如何计算任意凸面固定纵横比的最大对齐矩形的宽度/高度多边形?
此图显示了不同凸多边形(黑色)中的此类矩形(红色)的示例:
.
我找到了关于主题的不同论文,但它们不适合我的局限性。这很奇怪,因为他们应该大大简化算法,但不幸的是我没有找到任何线索。
固定比率确实简化了问题,因为现在有了线性程序。
你想找到 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 − w z), y1 = (y − h z ), x2 = (x + w z), y2 = (y + h z)。其次,让我们用 objective 项来交换这些约束。通常,多边形中的点约束看起来像(到半平面的有符号距离)≤ 0。相反,我们将对 objective 应用惩罚项。设 α > 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)
提示:
WLOG 矩形可以是正方形(必要时拉伸 space)。
然后由距离图的最高点到多边形的切比雪夫度量 (L∞) 中的最高点给出解决方案。它可以从中轴变换中确定,中轴变换本身是从 Voronoi 图获得的。
如何计算任意凸面固定纵横比的最大对齐矩形的宽度/高度多边形?
此图显示了不同凸多边形(黑色)中的此类矩形(红色)的示例:
我找到了关于主题的不同论文,但它们不适合我的局限性。这很奇怪,因为他们应该大大简化算法,但不幸的是我没有找到任何线索。
固定比率确实简化了问题,因为现在有了线性程序。
你想找到 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 − w z), y1 = (y − h z ), x2 = (x + w z), y2 = (y + h z)。其次,让我们用 objective 项来交换这些约束。通常,多边形中的点约束看起来像(到半平面的有符号距离)≤ 0。相反,我们将对 objective 应用惩罚项。设 α > 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)
提示:
WLOG 矩形可以是正方形(必要时拉伸 space)。
然后由距离图的最高点到多边形的切比雪夫度量 (L∞) 中的最高点给出解决方案。它可以从中轴变换中确定,中轴变换本身是从 Voronoi 图获得的。