A、B、C、Dの4点からなる形状があり、その位置だけがわかります。目標は、これらのポイントを変換して、相互に特定の角度とオフセットを持たせることです。
例：A(-1,-1) B(2,-1) C(1,1) D(-2,1)、これは、AB、BC、CD、およびAD間のオフセットがすべて2である完全な正方形（すべての角度90）に変換する必要があります。結果は、反時計回りにわずかに回転した正方形になります。
これを行うための最も効率的な方法は何でしょうか？私はこれを単純なブロックシミュレーションプログラムに使用しています。
マークがほのめかしたように、制約付き最適化を使用して、元の角までの距離の2乗を最小化する辺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から5、li gi）
ここで、lisはラグランジュ乗数です。
勾配は非線形であるため、ヘッセ行列を取り、多変量ニュートン法を使用して解を反復処理する必要があります。
与えられたデータ（黒）に対して私が得た（赤）解決策は次のとおりです。
これには5回の反復が必要であり、その後、ステップのL2基準は6.5106e-9でした。
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)は四辺形の指定された角を時計回りに表します。正方形をフィッティングしているので、四隅の位置に関して一定の制約があります。実際には、2つの反対側のコーナーが指定されている場合、それらは一意の正方形を記述するのに十分です（対角線上の鏡像を保存してください）。
これは、2つの反対側のコーナーがターゲットの正方形を表すのに十分であることを意味します。最初の2つのコンポーネントを使用して、残りの2つのコーナーをパラメーター化できます。上記の例では、とをとで表現してP2いP4ます。正方形のパラメータ化の背後にある幾何学的な直感を視覚化する必要がある場合は、インタラクティブバージョンで遊ぶことができます。P1 = (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
用語の単純な再配置が最終的な解決策につながるので、これがどこに向かっているのかがわかるかもしれません。
