ポリゴンが対称かどうかを確認します

Question

デカルト座標のポリゴン（凸面である必要はありません）を考えると、そのポリゴンの対称性を確認する方法はありますか？

O（N）ソリューションを考えることができます。回転キャリパーを使用して、反対側のエッジの各ペアが平行でサイズが等しいかどうかを確認します。しかし、私はそのアルゴリズムの正しさを証明することはできません。より良い解決策を提案できますか？

Answer 1

• ポリゴンの重心を計算します。
• 重心が座標として（0,0）になるように、原点に変換します。
• 次に、座標（i、j）の各頂点について、座標（-i、-j）を持つ頂点があることを確認します。

  これにより、ポリゴンが実際に対称であることが証明されます。

  複雑さ：N、座標から頂点に直接アクセスできると仮定します。

Answer 2

どのような対称性が許可されているかをより明確にする必要があります。中心対称（別名180度回転）？軸の1つで対称性をミラーリングしますか？ある程度の回転？一部のアプリケーションでは、0,90,180,270 +ミラーリングによる回転のみが許可されています...答えはそれぞれの場合で異なります。

中心対称の場合のみ、ポリゴンが適切に表現されていると仮定すると（つまり、エッジに余分な頂点がなく、頂点が前方演算子で含まれている場合、中心対称のポリゴンは偶数の2 * N頂点を持ちます。、そしてあなたはこれを行うことができます：

1. iter1は0番目の頂点を参照し、iter2はN番目の頂点を参照するように設定します。

2. N回繰り返す：

   if（* iter1！= * iter2）はfalseを返します;

3. trueを返します;

Answer 3

最初に、チェックする対称性のタイプ（ポリゴンがどの変換に対して不変であるか）を定義する必要があります。提供するアルゴリズムは、凸多角形の中心対称性をチェックします（回転キャリパーは凸多角形でのみ機能するため）。