geometry - 最适合正方形到四边形

Question

我有一个由四个点组成的形状，A、B、C 和 D，其中唯一的位置是已知的。目标是将这些点转换为相对于彼此具有特定角度和偏移量。

例如：A(-1,-1) B(2,-1) C(1,1) D(-2,1)，它应该被转换为一个完美的正方形（所有角度都是 90），AB、BC、CD 和 AD 之间的偏移量都为 2。结果应该是一个逆时针稍微旋转的正方形。

最有效的方法是什么？我将它用于一个简单的块模拟程序。

Answer 1

正如 Mark 所暗示的，我们可以使用约束优化来找到边 2 正方形，以最小化到原始角落的距离平方。

我们需要f = (a-A)^2 + (b-B)^2 + (c-C)^2 + (d-D)^2在某些约束下最小化（其中正方形实际上是向量参数与自身的点积）。

按照拉格朗日乘数的方法，我选择了以下距离约束：

g1 = (a-b)^2 - 4
g2 = (c-b)^2 - 4
g3 = (d-c)^2 - 4

以及以下角度约束：

g4 = (b-a).(c-b)
g5 = (c-b).(d-c)

一张快速的餐巾纸草图应该会让你相信这些限制就足够了。

然后，我们希望在 g 都为零的情况下最小化 f。

拉格朗日函数为：

L = f + Sum(i = 1 to 5, li gi)

其中lis 是拉格朗日乘数。

梯度是非线性的，所以我们必须采用 hessian 并使用多元牛顿法迭代到一个解决方案。

这是给定数据（黑色）的解决方案（红色）：

这需要 5 次迭代，之后该步骤的 L2 范数为 6.5106e-9。

Answer 2

虽然 Codie CodeMonkey 的解决方案是一个完全有效的解决方案（并且是拉格朗日乘数的一个很好的用例），但我相信值得一提的是，如果没有给出边长，这个特定问题实际上有一个封闭形式的解决方案。

我们希望最小化拟合正方形的角与给定四边形的角之间的距离。这相当于最小化成本函数：

f(x1,...,y4) = (x1-ax)^2+(y1-ay)^2 + (x2-bx)^2+(y2-by)^2 +
                (x3-cx)^2+(y3-cy)^2 + (x4-dx)^2+(y4-dy)^2

Pi = (xi,yi)拟合正方形的角在哪里，并且A = (ax,ay)通过按顺时针顺序D = (dx,dy)表示四边形的给定角。由于我们正在拟合一个正方形，因此我们对四个角的位置有一定的限制。实际上，如果给定两个对角，它们就足以描述一个独特的正方形（除了对角线上的镜像）。

点的参数化

这意味着两个对角足以代表我们的目标正方形。我们可以使用前两个角的组件对剩下的两个角进行参数化。在上面的例子中，我们用and来表达P2and 。如果您需要正方形参数化背后的几何直觉的可视化，您可以使用交互式版本。P4P1 = (x1,y1)P3 = (x3,y3)

P2 = (x2,y2) = ( (x1+x3-y3+y1)/2 , (y1+y3-x1+x3)/2 )
P4 = (x4,y4) = ( (x1+x3+y3-y1)/2 , (y1+y3+x1-x3)/2 )

代入x2,x4,y2,y4方式f(x1,...,y4)可以改写为：

f(x1,x3,y1,y3) = (x1-ax)^2+(y1-ay)^2 + ((x1+x3-y3+y1)/2-bx)^2+((y1+y3-x1+x3)/2-by)^2 + 
                (x3-cx)^2+(y3-cy)^2 + ((x1+x3+y3-y1)/2-dx)^2+((y1+y3+x1-x3)/2-dy)^2

一个仅依赖于 的函数x1,x3,y1,y3。为了找到结果函数的最小值，我们将偏导数设置f(x1,x3,y1,y3)为零。它们是：

df/dx1 = 4x1-dy-dx+by-bx-2ax = 0   -->   x1 = ( dy+dx-by+bx+2ax)/4
df/dx3 = 4x3+dy-dx-by-bx-2cx = 0   -->   x3 = (-dy+dx+by+bx+2cx)/4
df/dy1 = 4y1-dy+dx-by-bx-2ay = 0   -->   y1 = ( dy-dx+by+bx+2ay)/4
df/dy3 = 4y3-dy-dx-2cy-by+bx = 0   -->   y3 = ( dy+dx+by-bx+2cy)/4

您可能会看到这是怎么回事，因为对术语的简单重新排列会导致最终解决方案。

最终解决方案