ポリゴンメッシュからの一意のエッジ検出アルゴリズム

StackOverflow https://stackoverflow.com/questions/207744

質問

ポリゴンデータのセットから一意のエッジを取得できる優れたアルゴリズムを探しています。この場合、ポリゴンは2つの配列によって定義されます。 1つの配列はポリゴンごとのポイントの数で、もう1つの配列は頂点インデックスのリストです。

動作しているバージョンがありますが、500,000ポリゴンを超えるとパフォーマンスが低下します。私のバージョンでは、各面を調べて、各エッジのソートされた頂点をstl :: setに追加します。私のデータセットは主に三角形と四角形のポリゴンであり、ほとんどのエッジが共有されます。

このためのよりスマートなアルゴリズムはありますか？

役に立ちましたか？

解決

はい
ダブルハッシュマップを使用します。
すべてのエッジには2つのインデックスA、Bがあります。 A <！> gt;と言うことができます。 B.
最初のトップレベルのハッシュマップは、Aを別のハッシュマップにマップし、さらに別のハッシュマップは、すべてのエッジについて必要な情報を表す何らかの値にBをマップします。 （または、エッジの情報を保持する必要がない場合は、単にboolです）。
基本的に、これはハッシュマップで構成される2レベルのツリーを作成します。

この構造でエッジを検索するには、より大きなインデックスを取得し、トップレベルで検索して、ハッシュマップで終わります。小さいインデックスを取得して、この2番目のハッシュマップで検索します。

他のヒント

明確にするために、次のようなポリゴンリストを作成します：

A +-----+ B
   \    |\
    \ 1 | \
     \  |  \
      \ | 2 \
       \|    \
      C +-----+ D

次に、このようなエッジの代わりに：

A - B -+
B - C  +- first polygon
C - A -+

B - D -+
D - C  +- second polygon
C - B -+

次に、重複するB-C対C-Bエッジを削除して共有しますか？

アルゴリズムでどのようなパフォーマンスの問題が発生していますか？合理的なハッシュ実装を備えたセットは、かなり正常に動作するはずです。一方、ハッシュがデータに最適でない場合は、パフォーマンスに悪影響を与える可能性のある多くの衝突が発生します。

あなたは両方とも正しいです。適切なハッシュセットを使用すると、必要なレベルをはるかに超えるパフォーマンスが得られます。私は自分の小さなハッシュセットをロールバックすることになりました。

エッジの総数はN / 2とNの間です。Nはメッシュ内の一意の頂点の数です。すべての共有エッジはN / 2になり、すべての一意のエッジはNになります。そこからuint64のバッファーを割り当て、インデックスをこれらの値にパックします。ユニークなテーブルの小さなセットを使用して、ユニークなエッジをすばやく見つけることができます！

まず、頂点が一意であることを確認する必要があります。特定の位置に1つのエッジのみが必要な場合です。次に、このデータ構造を使用します

typedef std::pair<int, int> Edge;

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Edgeには、ソートされた順序でエッジを構成する頂点インデックスが含まれます。したがって、sampleEdgeがインデックス番号12および5の頂点で構成されるエッジである場合、sampleEdge.first = 5およびsampleEdge.12

その後、あなたはただやることができます

uniqueEdges[sampleEdge] = true;

すべてのエッジに対して。 uniqueEdgesはすべてのユニークなエッジを保持します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top