如何在任意四边形内刻一个矩形或圆圈

Question

这可能是一个更注重数学的问题,但是想在这里问一下,因为它是在CS环境中.我想在另一个(任意)四边形内刻一个矩形,内切四边形可能具有最大的高度和宽度.由于我认为算法类似,我想看看我是否也可以用圆圈做到这一点.

更清楚地听到我的意思是边界四边形作为一个例子.

以下是我试图实现的内容最大化的两个例子:

我做了一些初步的搜索,但没有发现任何确定的东西.似乎某种形式的动态编程可能是解决方案.看来这应该是一个线性优化问题,应该比我发现的更常见,也许我正在寻找错误的术语.

注意: 对于铭刻的正方形,假设我们知道我们正在寻找的目标w/h比(例如4:3).对于四边形,假设边不会交叉并且它将是凹的(如果这简化了计算).

Answer 1

1）圆圈。
对于三角形，这是学校课程中的标准数学问题。
对于四边形，您可以注意到最大内圆将至少接触其三个边。因此，采用三个边的每种组合并解决每个三角形的问题。
必须单独考虑平行边的情况（因为它们不形成三角形），但这并不是非常困难。

2）矩形。
你不能有“最大的高度和宽度”，你需要选择另一个标准。例如，在你的图片上，我可以通过减少高度来增加宽度，反之亦然。