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

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

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