1

重複しないポリゴンのセットがあります。これらのポリゴンは、ノード、エッジを共有できますが、厳密には重なり合いません。

ここで、制約付き Delaunay Triangulation (CDT) 手法を使用してそれらをメッシュ化します。問題なくメッシュを取得できます。

私の問題は、メッシュの後、どのメッシュ要素がどの元のポリゴンに属しているかを知りたいということです。私の現在のアプローチは、各メッシュ要素の重心を計算し、この重心がどの元のポリゴンに該当するかを確認することです。しかし、このアプローチは非常に計算量が多いため、好きではありません。

これを行う効率的な方法はありますか (Big O ランタイムに関して)? 私のプロジェクトには何万ものポリゴンが含まれており、スピードを落としたくありません。

編集: 以下のように、すべての頂点が複数の共通面を持つ場合があるため、メッシュ要素内のすべての頂点が共通の面を共有していることを確認してください (点線はメッシュ要素を形成し、頂点には 2 つの共通面があります):

4

5 に答える 5

1

私は2つのオプションを考えることができます.どちらもどういうわけか言及されています:

  1. ポイント/頂点の情報を維持します。この他の関連する質問を参照してください。

  2. 元のポリゴンで各メッシュ要素の重心を配置して、元のポリゴンで各メッシュ要素の重心を配置して、情報を再計算しますが、これは を使用して最適化しspatial_sort、入力ポリゴンでそれらを順番に配置することができます (前の結果を次の点の位置を開始するためのヒントとして使用します)。

于 2012-11-20T05:58:41.603 に答える
0

次の方法で新しいグラフ G(V,E) を作成します。すべてのメッシュに対して、V にノードを作成します。破線のエッジごとに、2 つの対応するメッシュを接続する E にエッジを作成します。ソリッド エッジを E のエッジにマッピングしないでください。

ConnectedComponents(G) を実行します。

すべてのメッシュにはラベルが付けられます (ポリゴンと 1 対 1 で対応します)。

于 2011-12-06T08:59:04.630 に答える
0

Mikeb が言うように、すべての元の頂点にポリゴン ID のラベルを付けます。

ポリゴンの内側にあるものが必要なので、ポリゴンの周りを時計回りにのみ移動するようにしてください。これにより、2 つのポリゴンのポイントが重なっている場合に、正しい方向を向いているポリゴンが取得されます。

このアプローチは O(n) に近いままであると予想されます。ここで、n はポイントの数を表し、各三角形は 3 つのポイントすべてに重なるポリゴンを 1 つまたは 2 つしか持つことができないためです。

于 2011-12-06T08:53:30.620 に答える
0

おそらく、ポリゴンごとに個別に CDT を呼び出し、各呼び出しの後にポリゴンで三角形にラベルを付けることができます。

于 2011-12-07T13:08:29.970 に答える
0

元の頂点のそれぞれにポリゴン ID (またはポリゴンが頂点を共有できるため、複数の頂点) でラベルを付けるのはどうでしょうか。次に、DT を正しく理解していれば、メッシュ内の特定の三角形の 3 つの頂点を見て、それらが共通のラベルを共有しているかどうかを確認できます。共有している場合、そのメッシュはラベル付きのポリゴンからのものです。

于 2011-12-06T04:01:36.923 に答える