問題タブ [delaunay]

私は現在、サブ問題として 2D ポイント セットの変更を含むプロジェクトの研究を行っています。ポイント セット自体には、いくつかのポイントのクラスターが含まれます。これをどうにかして互いに分離し、クラスター ハル内のポイントを緩和する必要があります。あるいは、クラスターのハルポイントを取得し、それらをドメインとして使用し、それらの内部に (ほぼ) 等間隔にポイントを分散するだけで十分です。したがって、緩和はスキップされる可能性があります。最悪のシナリオとして、最大 10 万個の頂点を含むいくつかのポイント セットを処理する必要があるため、使用するアルゴリズムは高速である必要があります。私はこの問題の複雑さを知っています。そのため、車輪を再発明したくなく、可能であれば既存のコードを使用したいと考えています。これまでのところ、次のことがわかりました。

1. 点集合緩和: Fortunes/Sullivans "Sweep Line" アルゴリズム: 最速のシングル スレッド ボロノイ ダイアグラム コンストラクターと言われています。ただし、コードを拡張するのは非常に難しいようで、デフォルトで抽出可能な情報には、少なくとも重心を計算して次の緩和反復を実行する必要があるボロノイ セル ハル データ (それらの頂点位置) が含まれていません。さらに、長方形以外のドメインは使用できません。

2. CVT: ボロノイ図を作成するための多目的ライブラリの束。ポイントの緩和と、ユーザーが指定した領域内のポイント セットもサポートしています。

3. CGAL: 基本的な MP サポートを備えた広範なフレームワークですが、明らかに統合された緩和方法はありません。各ポイント セットのサブクラスターの delaunay 三角形分割を作成し、これをボロノイ アダプターにフィードする必要があります。ボロノイ アダプターは、さらに緩和するためにボロノイ セル ハル データをクエリするイテレータを提供します。私がドキュメントを読んでいる限り、ドメインをサポートする必要があります（数千ページ:)

4. さらに、主に 3D で動作するように見える Voro++ などがあります。三角形。領域の制約を使用して、指定されたドメインからドローネ三角形分割を作成し、三角形の頂点を結果の点として使用できるようにします。

わかりました、現時点では、これをすべて非常にシンプルに保ちながら、CVTが私のニーズに合うべきだと私には思えます。しかし、よくわからないので、質問: できればドメインを使用して、ポイントセット緩和の実装を経験した人はいますか? どの既存のコードが望ましいでしょうか?

毛皮の提案に感謝します！t

MATLAB R2011b のデータ カーソルを三角形分割された 3D サーフェスのプロットに適用すると、不安定な動作が見られます: 特定の点をクリックすると、代わりに完全に異なる点が選択されます。円柱の例:

次に、データ カーソル モードを有効にして、前の列の 1 つの一番上のドットを選択してみます。私のインストールでは、MATLAB はカーソルの下のポイントを選択しませんが、ランダムに選択されたように見える別のポイントを選択します。

これはバグですか、それとも何か間違っていますか?

ドロネー三角形分割に関するこの会話をたどろうとしていますが、写真のアクセルと同じ結果を得ることはできません。顔だけにメッシュを描く方法を本当に知りたいですか？また、このループの役割と、「ポイント」の正確なタイプを知る必要がありますか?

誰でも私を助けてください。ありがとうございました ：）

必要以上に大きい Delaunay 三角形分割から距離を削除するにはどうすればよいですか?

サンプルデータ:

マップのプロット:

tri.mesh() によるDelaunay 三角形分割- package(tripack)

短い距離だけを抽出するにはどうすればよいですか? 私が意味する距離をあなたが確実に知っているそれらの大きなものは必要ありません。tri.mesh() 関数でこれを行う引数はありますか? それともその後にできるのでしょうか？

距離もこのオブジェクトに保存されていますか?

エッジを共有するすべての三角形のリストがあります。ボロノイ図を描くにはどうすればよいですか？Delaunay 三角形をループして、頂点 1 = 頂点 2 および頂点 2 = 頂点 1 と比較します。同じエッジがある場合。また、頂点 1 = 頂点 1 および頂点 2 = 頂点 2 の場合もチェックします。方程式では、両側が異なる三角形です。Boywer watson アルゴリズムと同じループです。

3D座標のセットを取り、三角形分割を実行して凸包/ Delaunay を生成するコードを開発しました。

これはうまくいき、Deluanay 三角形分割を使用して、tsearchn を使用して特定のボリュームにポイントが含まれているかどうかをテストできます。

次に、そのような 3D ボリュームを 2 つ取り、それらが交差するかどうかをテストします。さらに、ボリューム A とボリューム B の何パーセントが交差しているかを知りたいです。

1 つのボリューム内にあるポイントのメッシュ グリッドを生成し、tsearchn を使用してそれらを別のボリュームにテストできると思います。しかし、もっと便利な方法を誰かが知っているかどうか知りたかったのです。または、同様の分析を行うためのアドバイスがあります。

どうもありがとう！

編集...コード例

このサンプル コードの場合、shapeAは と 50% 交差しshapeBます。 コードの最後に、形状のポイント数を増やしてテストすることで問題を解決できることを
示すセクションを追加しました。tsearchn
tsearchn

ファセットが何らかの「ラベル」(何らかの抽象プロパティ) に関連付けられている、制約付きの Delaunay 三角形分割があるとします。同じラベルを共有するファセットに付随するエッジを制約から削除したいと考えています。それを行うための効率的なアプローチは何ですか?また、制約が削除された後に取得されたファセットがそのラベルを保持していることを確認する方法は?

これは、私の目的を説明するために CGAL の例から追加されたコードの一部です。

そこからいくつかの可能性が見えます：

1. 元の三角形分割で異なるラベルを持つ面のみを結合する制約を挿入して、新しい CDT を構築します。
2. バリアントcdt.remove_constrained_edge(fh, i, out)を使用して、制約の削除によって影響を受ける可能性のあるファセットを回復し、それに応じて処理します (ただし、イテレータが無効になるという問題は残ります)。
3. 前の発言と組み合わせてファセットの BFS/DFS トラバーサルを使用しますが、各制約の削除によってどのキュー/スタック ファセットが影響を受けたかを知る必要があります。
4. トラバーサル中に/のset代わりに使用して、ファセットから削除できるようにします (削除前に) 削除された制約に関連するファセットへのハンドルを参照する必要があります。queuestack

では、StackOverflow はこれについてどう考えているのでしょうか?