algorithm - 如何在任意四边形内刻上一个矩形或圆形

Question

这可能是一个更侧重于数学的问题，但想在这里问，因为它是在 CS 上下文中。我正在寻找在另一个(任意)四边形内刻一个矩形，其中刻有尽可能大的高度和宽度的四边形。因为我认为算法会相似，所以我想看看我是否也可以用一个圆圈来做到这一点。

更清楚的是，我以边界四边形为例。

以下是我试图实现的内切最大化的 2 个示例:

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

注释:对于内切方 block ，假设我们知道我们正在寻找的目标 w/h 比率(例如 4:3)。对于四边形，假设边不会交叉并且是凹形的(如果这样可以简化计算)。

Answer 1

1) 圆。
对于三角形，这是一个 standard math question来自学校类(class)。
对于四边形，您会注意到最大内圆至少会触及它的三个边。因此，取三个边的每种组合并解决每个三角形的问题。
平行边的情况必须单独考虑(因为它们不形成三角形)，但这并不是非常困难。

2) 矩形。
您不能“最大高度和宽度”，您需要选择其他条件。例如，在您的图片上，我可以通过降低高度来增加宽度，反之亦然。