XMLメッシュ:)
私は実際にこれをよく見ていました。私の最初の答えはかなり怠惰でした。あなたはもっと上手く書くことができます(上記のように)、それはそれほど複雑ではありません。これ以上のジャーナル記事は$ 40を出しません。ここではあなたのために動作する擬似コードのソリューションです。
注:私がテーブルと言うとき、私は 'ルックアップテーブル'を意味します。
各三角形に番号が付けられ、一意に番号が付けられ、<演算子を使用して比較できる(したがって、一意のキーの組み合わせを得ることができる)頂点v1、v2、v3で構成されているものとします。 - >(三角形リスト)テーブルと呼ばれるedge_triangles
与えられたエッジを使用する三角形と、与えられた三角形がどの辺から構成されているかを示す表。次のように私たちは、これらのリストを構築する:
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-> edge_coincident_edgesという名前の(エッジリスト)テーブル。
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)に近いはずです。
回答ありがとうございます、私は多くの疑いがあります;) – Aralox