このアルゴリズムは、2つの配列の内容が同じかどうかを判断するのに適していますか？

Question

私は2つの配列を持っています。それぞれが単純な閉じた多角形を、順番に並んだ点の配列として表しています。最後の要素は最初の要素と同じです。私は任意の2つの単純な閉じたポリゴンの等価アルゴリズムを実装しています。

Array A would be like this [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6, pnt1] 
Array B would be like this [pnt2, pnt3, pnt4, pnt5, pnt6, pnt1, pnt2] 
Array C would be like this [pnt2, pnt1, pnt6, pnt5, pnt4, pnt3, pnt2] 
Array D would be like this [pnt1, pnt2, pnt3, pnt5, pnt6, pnt4, pnt1] 

配列AとBは、同じ順番と同じ点にあるため、等しいです。配列AとCは、同じ順序である（しかし、逆の）ため、同じ理由でBとCも同じです。

配列Dは、ポイントのトラバーサルが順序外であるため、他の配列と同じではありません。

次のように私のアルゴリズムである：

1）の要素の同じ＃が含まれている必要があり、配列の長さを比較する - 時定数を

2）Kとして[0] Bの設定を見つける - 線形探索[1] = B [K + 1]など[N]まで、線形時間

当然インデックスは、おそらくを介して、アレイの端部を包み込むならば、線形時間

3）を参照しますmod演算子です。

これよりも優れたアルゴリズムがありますか？

Answer 1

概要：

1. 繰り返し点
2. I-1における値i + 1での値よりも低い場合に有する（文字列を逆iが最小値
3. の位置を探すを削除エッジケース、すなわち、iの取る= 0又はI = N-1の最小値は、ヘッド

総複雑であるように）

アレイを回し：O（N）

注：手順3と4は必ずしも必要ではありません。ステップ2からの位置は、ステップ3からはの向きはになります。 2つの異なる配列を比較しながら、最小値の* location *からの比較から始めて、オリエンテーションに従って移動してください。

例：

[PNT1、pnt2、pnt3、pnt4、pnt5、pnt6、PNT1] - > [PNT1、pnt2、pnt3、pnt4、pnt5、pnt6] - > [PNT1、pnt2、pnt3、pnt4 、pnt5、pnt6]

[pnt2、pnt3、pnt4、pnt5、pnt6、PNT1、pnt2] - > [pnt2、pnt3、pnt4、pnt5、pnt6、PNT1] - > [PNT1、pnt2、pnt3、pnt4、 pnt5、pnt6]

[pnt2、PNT1、pnt6、pnt5、pnt4、pnt3、pnt2] - > [pnt2、PNT1、pnt6、pnt5、pnt4、pnt3] - > [pnt3、pnt4、pnt5、pnt6、PNT1 、pnt2]→[pnt1、pnt2、pnt3、pnt4、pnt5、pnt6]

[PNT1、pnt2、pnt3、pnt5、pnt6、pnt4、PNT1] - > [PNT1、pnt2、pnt3、pnt5、pnt6、pnt4] - > [PNT1、pnt2、pnt3、pnt5、pnt6、pnt4]

Answer 2

このような比較を行うには、一方の配列が他方の回転（最後の要素を除く）であるかどうかを調べることができます。

まず、ElKaminoが指摘しているように、繰り返される要素を削除します。そして場合のみB=[x3, x4, ..., xk, x1, x2]またはそのような何かあれば、基本的に、あなたはAがBに

A=[x1, x2, ..., xk]の要素を回転させることによって得ることができるかどうかを知りたい、BはAと同じ順序で同じ内容を持つことになります。そのような場合、Bはrotation of Aと呼ぶことができます。しかし、それは十分ではありません。順序が同じか逆であるかどうかをチェックしたいからです。その後、Bの逆、または逆のAの同じ手順を適用することができます。

擬似コード

def isSamePolygon(A, B): 
    remove the last element of A and last element of B 
    return isRotation(A, B) or isRotation(A, reverse(B)) 

def isRotation(A, B): // returns true if A is a rotation of B 
    // create an array which has two copies of A. 
    // e.g [a1, a2, ..., ai, a1, a2, ..., ai] 
    if (size(A) != size(B)) 
     return false 
    temp_array = concat(A, A) 
    return true if temp_array contains the elements of B in the exact same order, 
     false otherwise 

分析

isRotationの実行時間と空間の複雑さは、最大の大きさ（サイズ（A）、サイズ（B））で線形です。これは、temp_arrayを作成すると、Aのサイズで線形時間と線形空間を取るためです。同様に、BがAに含まれているかどうかをチェックすることも、線形時間で実行するためです。

私が間違っている場合は私を修正しますが、このアルゴリズムを使用すると、漸近的な複雑さを減らすことはできません。しかし、それを最適化してより速く実行することができます。 size(A)>size(B)の場合、AとBを入れ替えることができます。さらに、あなたは同時に2つの呼び出しを行う代わりに逆を確認することができます。

Answer 3

前処理が許可されていない場合、この問題は他の頂点の中の1つのポリゴンの1つの頂点をN個比較できるので、最悪の場合のオメガ（N）です。

したがって、最適な時間O（N）で実行されるアルゴリズムよりもあまり良くありません。 [2、3の間にステップを挿入してトラバーサル順序を決定する]

前処理が許可されている場合は、すべてのポリゴンに対して（X、Y）字句順で最初の頂点を識別できます。それを主な頂点と呼ぶことにしよう。これにより、2つの等しいポリゴンが同じ主頂点を持ち、線形検索が不要になるため、アルゴリズムのステップ1が役に立たなくなります。

さらに、頂点から開始して座標上のCRCを計算することで、ポリゴンに署名を関連付けることができます。それでは、署名を比較するだけで、時間O（1）で高い確率で異なるポリゴンを検​​出します。

Answer 4

"シンプル"とは、穴や自己交差のないポリゴンを意味しますが、それは頂点でのみ接触することがあります。たとえば、次のよう

シナリオのこの種は、あなたのケースでは問題ないかもしれませんが、いくつかpolygon algorithmsは、複雑な多角形を構成する輪郭を形成するために、このような形状に依存しているので、それのことができるようにするために便利ですそれらに対処する。この場合

、これら2つの多角形が等しいとすべきである：Pにおける最初の（及び辞書式に最小の）頂点Aが繰り返されるので、所定のアルゴリズムの

P = ABCADEAFGAHIAJKA 
Q = FGAHIAJKABCADEAF 

一部はこれを見落とす可能性があります。しかし、あまりにも長い間、我々は何のエッジが繰り返されていないことを知っているように、我々は多くの問題なしアルゴリズムを適応させることができます：QでP[0]ため

1. 検索。
2. Q[i]で一致するものを見つけたら、P[1]~Q[i-1]とQ[i+1]（適切なラッピングあり）を比較してください。
3. 一致が1に戻り、の場合はP[0]をQに、Q[i+1]から検索し続けます。
4. 手順2で一致が見つかったら、Pを通り、同じ方向にQを進めて比較を続けます。不一致が見つかった場合、ポリゴンが異なり、すぐに停止することができます（P[0]の別の一致を検索し続ける必要はありません）。まったく通過しても同じです。余談として、

あなたは、輪郭に辞書的に最小限の頂点を識別する必要がありますが、頂点を反復することができる場所、あなたは最小限の隣接頂点または時計回りのいずれかを考慮してネクタイを破ることができるアルゴリズムを使用する場合（または反時計回りに、あなたが一貫している限り）隣り合った頂点。ここでも、これは繰り返されないエッジに依存します。