ポリゴン合同アルゴリズム

Question

2組のポリゴン間の合同性をチェックするアルゴリズムを知っている人はいますか？具体的には、下の図を参照してください。

私は平行移動、回転または反射回数を経由して与えられたセット（例えば青の三角形）が可能かどうか、つまり、別のセットに色の三角形の与えられたセットが合同であるかどうかをチェックする方法を探しています

別のセット（例えば、赤い三角形）に重ね合わせます。上記の例では、3組の三角形（青、赤、緑）がすべて合同です。

私が取り組んでいる実際の三角形はこれより大きく、より多くのセットを持っています。

グーグルでthis paperが見つかりましたが、それは3Dポリゴンに関係しており、（私の考えでは）実装可能ではありません。

建設的なアイデアやリンクは大歓迎です。

ちょうど明確にする編集は、三角形の各セットは、セット内の他の三角形に対する位置情報にセットで、すなわち各三角形が固定され、全​​体の接続図のように扱われなければなりません。

また、三角形の1つのセットが別のセットと一致しているかどうかを判断できるアルゴリズムが必要ですが、上記の三角形よりはるかに大きな三角形があり、さらに多くのセットがあります。 N個の三角形のN個の異なる色のセットに分割された、辺の長さNとN 2個の小さな三角形の合計を持つ三角形を想像してください。

Answer 1

回転と反射の組み合わせは、回転と最大で1回の反射で表すことができます。回転のみのアルゴリズムを2回、元の図形を1回、反射図形を1回実行すると、反射を無視できます。

三角形の重心（または、三角形の頂点にのみ質量を持つ図の重心）は回転の影響を受けませんので、重心を計算することから始めます各図の今度は、その図をその重心からの図の各点の方向と距離を与えるリストで表します。

距離のセットが異なる場合、数字は互いに回転することはできません。この段階では、ほとんどの不一致が検出されます。総コストN^2の場合、ある図形の頂点を他の図形の可能な各頂点に回転させ、この計算した回転を他のすべての頂点に適用し、それらが一致するかどうかを見ることができます。可能であれば、https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotationのいくつかのバージョンを使用してこれをスピードアップすることができます。頂点への方向の間の角度による方向を、それらを順番にソートした後に表現するのに役立ちます。