アルゴリズム設計 - 頂点を共有する三角形のセットを見つけるより良い方法

Question

私はDelaunay三角測量からボロノイグラフを計算しようとしていますが、私は三角形分割データを頂点の集合の形にしています（赤丸グラフ）と三角（グラフ上の青線）上：

私はすべての三角形の外心を取得することにより）（簡単に赤の線の交点をボロノイグラフverticiesを計算することができますよ。

ただし、赤いポリゴンごとに 'セル'情報を取得する必要があります。これを行うには、赤い頂点ごとに同じ頂点を共有する三角形のセットを見つける必要があります。それがすべてを検索だと、もちろん、非常に非効率的である

foreach (Vertex3 vertex in DelaunayVertices) 
    { 
     VoronoiCell cell = new VoronoiCell(); 
     cell.Vertex = vertex; 

     //seach all triangles for the ones that match this. 
     foreach (Face3 face in DelaunayTriangles) 
     { 
      if (face.Vertices.Where(v => v.Equals(vertex)).Any()) 
      { 
       //shares vertices, add it's circumcenter as an edge vertex of the cell 
       cell.EdgeVertices.Add(face.Circumcenter); 
      } 
     } 
    } 

：

だから私のコードは、この（C＃の）次のようになります。丸で囲まれた頂点のために、私は緑の三角形を必要とするので、 。しかし、顔やバーチャルのコレクションは完全にソートされていません（ソートの仕方やソートの方法がわかりません）。ちょうど混乱させるために、球の表面に3次元の頂点があります。

私はそれは、隣接します持っている各三角形について、隣接する頂点または面を見つけなければならない唯一のことは、以下のオレンジ色の三角形のためので、私は3つの緑の三角形を知っている：私は考えている

このグラフをトラバースするほうが効率的かもしれませんが、私は、ポイントを共有するセットを生成するアルゴリズムへのアプローチを考え出すのに苦労しています。

Answer 1

あなたは2次頂点ツー三角形のデータ構造を格納するために喜んでいる場合は、あなたが最初の3つの頂点に関連付けられた隣接リスト上に各三角形を押して、三角形リストをトラバースすることができます

for (all tria's ti) 
    for (all nodes ni in tria ti) 
     v2t[ni] <- ti 
    end for 
end for 

これは単にスイープO(n)です。

Answer 2

ヒルベルト曲線に沿って頂点をソートする、空白を埋める曲線を試すことができます。ポイントポリゴンテストを試すこともできますが、非常に難しいです。ブルートフォースアルゴリズムを使用してビットマップを作成することもできます。