私はthisのような形のメッシュを持っています。 には、最後に各ポリゴンを表すインデックスのリストがあります。私はポリゴンごとに隣接するポリゴンのリストを生成する必要があり、誰かがこれを行うための効率的なアルゴリズムを知っているのだろうか？ポリゴンインデックスのリストの隣のポリゴン
最も簡単な方法は各ポリゴンについてですが、他のすべてのポリゴンに2つの一致するインデックスがあるかどうかを確認しますが、これはネストされたループがいくつかあるようです。私はこれを使用しても構いませんが、ここでのパフォーマンスは大きな問題ではありませんが、代替案のためにスカウトしています。
ポリゴンごとに最大のインデックス/頂点に制限はありませんが、簡単にするために、3つのポリゴンを想定しています。
ありがとうございました！ :)
XMLメッシュ:)
私は実際にこれをよく見ていました。私の最初の答えはかなり怠惰でした。あなたはもっと上手く書くことができます（上記のように）、それはそれほど複雑ではありません。これ以上のジャーナル記事は$ 40を出しません。ここではあなたのために動作する擬似コードのソリューションです。
注：私がテーブルと言うとき、私は 'ルックアップテーブル'を意味します。
各三角形に番号が付けられ、一意に番号が付けられ、<演算子を使用して比較できる（したがって、一意のキーの組み合わせを得ることができる）頂点v1、v2、v3で構成されているものとします。 - >（三角形リスト）テーブルと呼ばれるedge_triangles
は、我々は2つのルックアップテーブルを必要としています。
与えられたエッジを使用する三角形と、与えられた三角形がどの辺から構成されているかを示す表。次のように私たちは、これらのリストを構築する：
for t = next triangle
// Determine the ordering of vertices.
min_vertex = min(t.v1, t.v2, t.v3);
mid_vertex = median(p.v1, t.v2, t.v3);
max_vertex = max(t.v1, t.v2, t.v3);
// Register which edges this triangle uses.
edge_triangles[min_vertex][mid_vertex].append(t);
edge_triangles[mid_vertex][max_vertex].append(t);
edge_triangles[min_vertex][max_vertex].append(t);
// Set the edges that make up this triangle.
triangle_edges[t].append({min_vertex, mid_vertex});
triangle_edges[t].append({mid_vertex, max_vertex});
triangle_edges[t].append({min_vertex, max_vertex});
for next t
をこれらのリストを使用して、我々は、与えられた三角形のエッジを取るエッジテーブルへのキーとしてこれらを使用し、そのエッジを共有するポリゴンを見ることができます。したがって、隣接する三角形。三角形Tのため、我々は行うことができるように次の第0はちょうど最初に、「隣接する三角形Tの0番目のエッジを共有する三角形のリストに等しい」の擬似コードである
adjacent = edge_faces[face_edges[t][0]];
。
min、median、maxを使用して、{v1、v2}や{v2、v1}のように、同じ辺に対して異なるエントリがないことを確認します。ここで、v1とv2は2つの頂点です。実際にはこれを無視し、エッジリストの異なるエントリに対応するリストを連結するが、実際には同じエッジに対応する「コンパクト」ステップを追加することができます。
他の可能性のある問題は、一致するが共通の頂点を共有しない2つのエッジがある場合です。この場合、あなたは、パラメトリック方程式にエッジのいずれかを減らすことができる偶然の一致のためにそれらを比較し、エッジが一致している、与えられたエッジのために、あなたに伝えルックアップテーブルを形成し、そのマップ：
edge-> facesテーブルを連結できないため、さらに別のルックアップテーブルを使用します。 e1とe2が隣接している場合、e2とe3は同じですが、e1とe3は同じではありません。エッジ - >顔リストのe1、e2、e3のエントリを連結すると、間違ったデータが出てしまうでしょう。これはおそらくあなたがやりたいことより少しだけですが、今朝解決しなければならない問題です:)。
各辺が最大でも2つの三角形にしか対応できない場合、追加できる伝統的な意味で 'リスト'を削除し、サイズ2の固定サイズの配列を使用できます。メモリオーバーヘッドを削減し、メモリ効率を向上させます。 >（最初の三角形、第2の三角形）のテーブルと呼ばれるedge_triangles -
とにかく、基本アルゴリズムは任意の数の辺を持つポリゴン（すべてのポリゴン間で同じである必要はない）に対して拡張可能であり、三角形（またはポリゴン）の数に対してO（N）一般的な場合）。空間の複雑さはO（E + N）であり、Eはエッジであり、Nはポリゴンの数である。あなたが良いハッシュアルゴリズムを持っていると仮定すると、ルックアップ時間はO（1）に近いはずです。
このLiamに感謝します！間違いなく、私を含め、多くの人々を助けます。今のところそれは気が散っていますが、病気は私がプロセスを完全に理解するまで数回それを再読します。 – Aralox
事前計算されたデータがないと、すべての面をループするよりも高速に処理することはできません。
事前計算されたデータについては、各頂点が使用される面のリストを保持するだけで十分です。隣人を見つけることは、2つの頂点の交差する顔リストで行われます。
三角形メッシュ（またはn -Dのシンプレックス）のみに興味があるのであれば、実際にはより高速なソリューションがあります。あなたが行う提案の時間複雑さは、O（k^2）です。ここで、kは三角形の数です。これは、多数の三角形に対して、近傍を計算するのに必要な時間が二次的に増加することを意味し、これはほとんどの状況において計算上禁止されている。
私はあなたがUengとシコルスキ（「3D FEAデータの隣接グラフを構築するための線形時間アルゴリズムに関する注記」の記事を読むことをお勧め、ビジュアルコンピュータ ：頁445から450まで、1996 ）。著者らは、四面体メッシュ内の近傍を見つけるための線形時間アルゴリズムO（k）について説明します。そこから三角形メッシュの類似アルゴリズムを簡単に推論できます。おそらく、これを一般のポリゴンにも拡張することができます！
これがうまくいけば教えてください！
回答ありがとうございます、私は多くの疑いがあります;） – Aralox