問題タブ [delaunay]

Delaunay 三角形分割をボロノイ グラフに明示的に変換せずに、点集合の Delaunay 三角形分割に関連するボロノイ セルの面積を計算したいと考えています。ボロノイ セルの領域のみを気にするので、ボロノイ データ構造を明示的に構築するコストを回避したいと考えました。これは可能ですか？Delaunay 三角形分割/円と二重ボロノイ セル領域の間に関係はありますか? ありがとう、

フィリップ

平面内の一連の点の Delaunay Triangulation を生成するための Bowyer-Watson アルゴリズムを実装しようとしています。このアルゴリズムは、境界のある超三角形の存在を前提としていますが、点の集合の凸包を維持するなどの代替手段もいくつか言及されています。

したがって、インクリメンタル アルゴリズムで凸包を仮定して点のドロネー三角形分割を生成することを決定した場合、点が凸包の外側にある場合、その点から面を構成する凸包上のすべての頂点に頂点を描画する必要があります。ポイントが見える船体の。

どうすればこの問題にアプローチできるのだろうかと思っていました。ポイントが一度に 1 つずつ追加されるインクリメンタル アプローチですべてのポイントなどの凸包を最初に生成する必要がありますか? DCEL の形式で凸包を維持する必要がありますか?

編集: 上の画像では、平面内の一連の点の凸包の外側にある点 P がある場合、点が見える包のエッジを計算する必要があります。【船体の緑の縁】

画像が質問を明確にするのに役立つことを願っています。

前もって感謝します

Ubuntu 11.04 で NetBeans 7.1 を使用しており、OpenCV を使用して一連の点から三角形を取得したいと考えています。次のように Delaunay 三角形分割を作成します。

その部分はうまくいくようです。実行すると、結果のストレージは次のようになります。

ストレージ 0xb287a90
署名 1116274688
下部 0x2a2d57a0
前 0x0 次 0x2a2e5730
上部 0x2cc947d0
前 0x2cc84840
次 0x0 親 0x0 署名
下部
上部
親
block_size
free_space
block_size 65408
free_space 0

ここでこれらの関数のドキュメントを見ましたが、三角形を抽出する関数が見つかりません。

誰かが三角形を抽出する方法を教えてくれたら、とてもありがたいです。

ピーター。

このプログラムにあるボロノイ/ドロネー図生成ライブラリを使用します。これは、フォーチュンのアルゴリズムの元の実装に基づいており、入力データとしてランダムなポイントのセットを使用して、次の出力データを取得できます。

1. Delaunay Triangulationからのエッジのリスト。つまり、各入力ポイントについて、どの入力ポイントが隣接しているかを確認できます。それらは特定の順序であるようには見えません。
2. ボロノイ図の頂点ペアのリスト。これを使用して、一度に1本の線でボロノイ図を描くことができます。繰り返しますが、明らかに特定の順序ではありません。
3. ポイントのペアの名前のないリスト。これは2と同じリストのようですが、順序が異なります。
4. ボロノイ図で形成された頂点のリスト。これも特定の順序ではないようです。

このライブラリを使用したプログラムのテスト実行からのデータの例を次に示します。

ボロノイ図とドロネー図を描くだけであれば上記のデータで十分ですが、これらの図で実際に作業するための情報は十分ではありません。必要なのは、ボロノイ頂点によって形成されたポリゴンの辞書であり、各ポリゴンが形成された入力ポイントによってインデックスが付けられています。好ましくは、各ポリゴンについて、これらのポイントは時計回りの順序でソートされます。

上記の情報を使用して、各領域に暗黙的にデータを割り当て、必要に応じてコーナーにデータを割り当て、どの領域がエッジを共有しているかを判断し（Delaunayエッジを使用）、それに応じて分析を行うことができます。

つまり、利用可能なデータを使用して、キーが入力ポイントの1つであり、そのキーによってインデックス付けされたデータが周囲のポリゴンを形成するボロノイ頂点のリストである辞書をまとめるにはどうすればよいでしょうか。あるいは、その情報は、私が与えられたデータのどこかに暗黙のうちに含まれていますか？

MST がドローニー三角形分割のサブセットであることは理解していますが、最小スパニング ツリーを見つけるのにどのように役立つのでしょうか? MST にドローニー三角形分割のエッジを使用すると、どのような意味がありますか? これは、MST を見つける前に一連のポイントを三角測量しないこととどう違うのですか?

それぞれに関連付けられたIDを持つ2Dポイントのセットがあります。（たとえば、ポイントが配列に格納されている場合、idは各ポイント0、....、n-1へのインデックスです）。

次に、これらの点のドロネー三角形分割を作成し、すべての有限エッジをリストします。エッジごとに、対応する2つの頂点で表されるポイントのIDが必要です。例：ポイント0とポイント2の間にエッジがある場合、（0,2）。これは可能ですか？

2次元のdelaunay関数を使用してMATLABで三角形メッシュを生成したいと思います。そこで、X値とY値を宣言し、tri = delaunay（X、Y）を設定します。次に、トリプロットを使用してプロットします。しかし、トライは私に何を与えますか？それは私の三角形のそれぞれに特別な指定番号を与えますか？いくつかのMATLABチュートリアルを読んだ後でも、私はそれを理解していません。

DomiterとZalikが使用するスイープラインアプローチを実装して、Javaの2D空間内の一連のポイントに対して制約付きドロネー三角形分割を生成しました。私が開発したコードが、nランダムに生成されたポイントとkそれらの間の制約エッジに対して本当に機能することを確認したいと思います。

ここで、一般的な戦略を使用して、n頂点のセットからランダムな点を選択し、次に2番目のランダムな点を選択して、それらの間にエッジがあると、制約付きドロネー三角形分割の定義から理解できるのは、制約が機能しない可能性があるためです。エッジは、平面直線グラフのエッジです。したがって、それらは交差していません。ポイントがランダムに選択された場合、交差する制約が生成されないことを確認するためにチェックを実行する必要がある場合があります。そのアプローチはまったく効率的ではないかもしれません。

したがって、制約をランダムに生成するための効率的な戦略を誰かが知っているかどうか疑問に思いました。

前もって感謝します。

計算幾何学にいくつかのコードを記述し、openMPを使用してそれらを並列化する必要があります。これまでに、凸包と最も近い点のペアを完成させました。ドロネー三角形分割分割統治コードを記述する必要があります。しかし、時間があまりありません。凸包を計算できれば、どこかでドロネー三角形分割を簡単に実装できるので、誰かがDTのシリアルコードを提供してくれるか、少なくとも凸包からドロネー三角形分割を生成する方法を教えてください。コードを記述して並列化できます。できるだけ早くそれ。

任意の点 P が与えられ、距離でソートされた近くの (メッシュ化されていない) ポイントを検索できると仮定すると、P を含むドロネー三角形を形成する 3 つの近くの点を効率的に決定できますか? もしそうなら、どのように？