ポリゴン間の共有頂点の検索

Question

すぐに面白い問題が発生しました。アルゴリズムについて考え始めました。私がそれを考えると、賢くなることができない限り、恐ろしいスケール（O（n^4））になるだろうと思うので、私は恐怖を感じます。私はこの問題について賢明になるのに困っている。ここでは、問題の簡単な説明です。

M個の頂点のリスト（Mは100のオーダー）として格納されているN個のポリゴン（Nは巨大> 10,000,000以上）を持っています。私がする必要があるのは、各ポリゴンが他のポリゴンの中で共有されている頂点のリストを作成することです（ポリゴンを周囲の関心領域、時にはリージョン同士を考えて考える）。私は、これは、多角形1で頂点1は、ポリゴン2の頂点2と同じポイントであり、ポリゴン1の頂点2は、ポリゴン2の頂点3と同じポイント同様に頂点であることを意味し、この

Polygon i | Vertex | Polygon j | Vertex 
    1   1   2   2 
    1   2   2   3 
    1   5   3   1 
    1   6   3   2 
    1   7   3   3 

のようなものを参照してくださいポリゴン1の5はポリゴン3の頂点1と同じです....

簡潔にするため、ポリゴンは重複しないこと、最も近いポリゴンはエッジに接していること、すべての頂点は整数であると仮定できます平等をテストしやすくするため）。

ここで私ができることは、各ポリゴンに対して、ポリゴンと頂点のすべてをループして、O（N^2 * M^2）のスケーリングを与える必要があります。私の場合。非常に大きなポリゴンファイルを持つことができるので、すべてをRAMに保存することもできないため、ファイルの複数の読み込みを意味します。ここで

は私の擬似コードは、私は（私はそこに多くの時間を費やすことはありませんので、私は文学を知らない）、これは、グラフィックスコミュニティに来ていることを仮定しているこれまでのところ

for i=1 to N 
    Pi=Polygon(i) 
    for j = i+1 to N 
    Pj=Polygon(j) 
    for ii=1 to Pi.VertexCount() 
     Vi=Pi.Vertex(ii) 
     for jj=1 to Pj.VertexCount() 
     Vj=Pj.Vertex(jj) 
     if (Vi==Vj) AddToList(i,ii,j,jj) 
     end for 
    end for 
    end for 
end for 

です。何か案は？

Answer 1

これは古典的な反復対メモリの問題です。すべてのポリゴンを1つおきのポリゴンと比較する場合は、O（n^2）の解決策を実行します。すべてのポリゴンをステップ実行してテーブルを作成し、その後テーブルを進めていくと、素晴らしいO（2n）ソリューションが得られます。私はインタビューの際に同様の質問をします。

メモリを使用できると仮定して、各頂点をキーとするマルチマップ（1つのキー、複数のエントリ）と、そのエントリとしてのポリゴンを作成する必要があります。次に、頂点とポリゴンをマップに挿入して、各ポリゴンを一度正確に歩くことができます。頂点がすでに存在する場合は、その頂点キーに追加エントリとしてポリゴンを追加します。

すべてのポリゴンにヒットしたら、マップ全体を1回歩き、複数のポリゴンエントリを持つ頂点で何をしても構いません。

Answer 2

単純な最適化の1つは、それぞれの別個の頂点（その座標によって識別される）を、それが一部であるすべてのポリゴンのリストにマッピングするマップ（ハッシュテーブル、おそらく）を作ることです。これはあなたのランタイムをO（NM）のようなものにカットします - まだまだ大きいですが、すべての頂点を調べることを避ける方法は想像できないので、私はあなたがうまくいくか疑問があります。

Answer 3

ポリゴン/フェイスデータがある場合、頂点を見る必要はありません。

• ポリゴンにわたって反復
• （MはVertsの数である）[0..M]から配列を作成し、各頂点インデックスの配列エントリをインクリメントします。

これはあなたの各頂点が使用されている回数を説明配列を与える。*

あなたはその後、ポリゴンの上に別のパスを行うと、各頂点のエントリを確認することができます。 1より大きい場合は、頂点が別のポリゴンと共有されていることがわかります。

他の情報を保存/検索する必要がある場合は、この戦略をさらに進めることができます。たとえば、カウントの代わりにポリゴンを直接配列に格納して、与えられた頂点インデックスを使用するすべての面のリストを取得することができます。この時点で、頂点インデックスがキーとなるマップを効果的に作成できます。

（*この例では縮退ポリゴンがないと仮定していますが、簡単に処理できます）。