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

Question

这可能是一个更关注数学的问题，但是想在这里问一下，因为它在CS环境中。我正在寻找在另一个（任意）四边形内刻出矩形，其中具有最大高度和宽度的内接四边形可能。因为我认为算法会类似，所以我期待着看看我是否也可以用圆圈来做这个。

为了更清楚听到我的意思是以边界四边形为例。

下面是刻最大化的两个例子，我想实现：

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

备注：对于刻写的方块，假设我们知道目标w/h比率，我们正在寻找（例如4：3）。对于四边形，假定边不会交叉，并且它将是凹的（如果这简化了计算）。

Answer 1

1）Circle。
对于三角形，这是一个来自学校计划的standard math question。
对于四边形，您可以注意到最大内圆至少会触及其三个边。因此，采取三方面的每个组合并解决每个三角形的问题。
平行边的情况必须分开考虑（因为它们不形成三角形），但这并不是非常困难。

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

Answer 2

4岁的线程，但我碰巧绊倒它时，谷歌搜索我的问题。

我在当前的CV应用程序中有这样的问题。我想出了一个简单而有点笨拙的解决方案，以找到最大的。不完全相同，因为我没有一个固定的边的比例最大化矩形的面积。

我还不知道我的解决方案是否能找到最佳解决方案，或者它是否适用于所有情况。我也认为应该有一个更有效的方法，所以我期待着你的意见。

首先，假设一组4个点形成我们的（凸）四边形：

x y 
P1 -2 -5 
P2 1 7 
P3 4 5 
P4 3 -2 

对于此过程中最左边的点是P1，有以下几点被编号顺时针方向旋转。它看起来像这样：

然后，我们创建点之间的线性函数。对于每个函数，我们必须知道斜率k和从0到d的距离。 k只不过是两点的Y的差异除以X的差异而已。可以通过求解d的线性函数来计算d0。所以我们有

k=dy/dx 
d=y1-k*x1 

我们也会想要反函数。

k_inv = 1/k 
d_inv = -d/k 

然后，我们创建了四边形

 k  d      k   d 
p1p2 4  3   p1p2_inv 0.25 -0.75 
p2p3 -0.67 7.67  p2p3_inv -1.5 11.5 
p3p4 7  -23   p3p4_inv 0.14 3.29 
p4p1 0.6  -3.8  p4p1_inv 1.67 6.33 

的每一侧上的功能和反函数如果我们有完全水平或垂直线，我们将在的功能的一个结束了一个DIV/0或者反函数，因此我们需要分别处理这种情况。

现在我们通过两个函数所包含的所有角落，这两个函数具有不同符号的斜率。在我们的情况下，这将是P2和P3。

我们从P2开始，用适当的步长迭代P2和P1和P3中较高的一个之间的y值，并使用反函数来计算水平方向上函数之间的距离。这将使我们矩形

a=p2p3_inv(y)-p1p2_inv(y) 

在两个X值x = p2p3_inv（Y）并且x = p1p2_inv（Y），那么我们计算在y中的差异在两个相反的功能，并采取的距离的一侧到我们当前的y位置作为我们矩形第二面的候选位置。

b_candidate_1 = y-p4p1(p2p3_inv(y)) 
b_candidate_2 = y-p4p1(p1p2_inv(y)) 
b_candidate_3 = y-P3p4(p2p3_inv(y)) 
b_candidate_4 = y-P3p4(p1p2_inv(y)) 

四个参数中较小的一个将是b方案的解决方案。 该地区显然成为a * b。

我确实在Excel一个简单的例子来证明：

最小B给是6.9，因此该溶液的右上角是上P2P3和矩形在水平和b延伸的分别垂直于左边和底部。

矩形的四点是这样

Rect x  y 
R1  0.65 -1.3 
R2  0.65 5.6 
R3  3.1  5.6 
R4  3.1  -1.3 

我将不得不把这个成C++代码，并运行一些测试，看看如果解决方案推广，或者这只是“运气”。

我认为也应该可以用函数将A = a * b中的a和b代入函数，并将它放入一个必须在p1p2仅在P1和P2之间定义的条件下必须最大化的线性公式中。 ...