如何求已知内接于闭合多边形的最大等腰梯形?

问题描述 投票:0回答:1

我需要找到多边形内接的最大(面积最大)等腰梯形,并且该梯形必须有一个设定的中心。

多边形由二维点数组定义。多边形是封闭的,可以是凸多边形,也可以是凹多边形。 我所说的等腰梯形是指这种形状。enter image description here

这是一个有两条平行边和一条对称线的四边形。

中心可以有很多含义,对于这个问题,中心如下 enter image description here

即底中垂线与高中中垂线相交的点。

梯形的中心必须与多边形的任意点相匹配。例如,如果多边形如下,任意点是黑点:enter image description here

内切梯形应该是这样的:enter image description here

我的示例梯形可能不是最大的梯形,但我们假设它是最大的。平行线必须是水平的,因此以下示例无效:

enter image description here

我尝试阅读算法来找出多边形中最大的内切矩形,并对其进行调整,但它们似乎不太灵活。

algorithm math geometry convex-polygon
1个回答
0
投票

这个问题会变得容易很多,如果你:

  1. 旋转90度;和
  2. 将其对折

这样:

Original

变成这样:

enter image description here

现在,您只关心每个 x 位置处可用的最大高度,并且您只需找到适合该信封下方的最佳半梯形的顶线:

enter image description here

只需找到每个 x 位置处高度最小的原始线段,即可将包络线轻松计算为分段函数。

要找到最佳梯形的顶线,您可以尝试每对过零之间的每一对线段,并找到连接这些跨度的最佳顶线。

最新问题
© www.soinside.com 2019 - 2025. All rights reserved.