問題: 2 つの重なり合う 2D 形状 A と B があり、それぞれの形状のピクセル数は同じですが、形状が異なります。形状の一部が重なり合っており、重なり合っていない部分がいくつかあります。私の目標は、形状 A のすべての重複しないピクセルを形状 B の重複しないピクセルに移動することです。各形状のピクセル数は同じなので、1 対 1 のマッピングを見つけることができるはずです。ピクセル。制限は、移動したすべてのピクセルが移動した合計距離を最小にするマッピングを見つけたいということです。
ブルート フォース:この問題を解決するためのブルート フォース アプローチは明らかに問題外です。なぜなら、n 個あると思われるすべての可能なマッピングの合計距離を計算する必要があるからです。(ここで、n は 1 つのシェイプ内の重複しないピクセルの数です) を、マッピング内のポイントの各ペアの距離を計算する計算 n 倍すると、合計 O( n * n! ) または同様の値が得られます。
バックトラッキング:私が考えることができる唯一の「より良い」解決策は、バックトラッキングを使用することでした。これにより、これまでの現在の最小値を追跡し、特定のマッピングを評価している任意の時点で、その最小値に達するか超えた場合、私は次のマッピングに進みます。これでも O( n! ) よりもうまくいきません。
合理的な複雑さでこの問題を解決する方法はありますか?
また、ポイントを最も近くにある隣接ポイントに単純にマッピングするという「明白な」アプローチでは、常に最適なソリューションが得られるとは限らないことにも注意してください。
より単純なアプローチ?:二次的な質問として、実行可能な解決策が存在しない場合、重複しない各セクションを小さな領域に分割し、これらの領域をマッピングして、マッピングの数を大幅に削減することが 1 つの可能性として考えられます。2 つの領域間の距離を計算するには、重心 (領域内のピクセル位置の平均) を使用します。ただし、これは、最適に近い答えを得るためにパーティショニングをどのように行うべきかという問題を提示します。
どんなアイデアでも大歓迎です!!