問題タブ [delaunay]

問題: 3D ポイント (x、y、z 座標) からのメッシュ生成。

私が持っているのは、3D 空間の点 (x、y、z 座標) で、画像 1 で確認できます。
出力は画像 2、画像 3、または画像 4 です。つまり、メッシュになります。メッシュがあれば、その上の素材を提供できます。

Delaunay 三角形分割や制約付き Delaunay 三角形分割がメッシュ生成に役立つと多くの人が言っているのを見てきましたが、私が最も見つけたのは、2D ポイント (x 座標と Y 座標のみ) での実装です。

しかし、私の問題は次のとおりです。画像1からわかるように、3Dにポイントがあります。

Delaunay 三角形分割または制約付き Delaunay 三角形分割は、3D ポイントでうまく機能しますか? はいの場合、どのように？それとも、3D ポイントからメッシュを生成するための別のアルゴリズムを見つける必要がありますか?

注: 2D 点の Delaunay 三角形分割の 1 つの良い説明は、ここにあります。

一連のポイントの中から「近くの」隣人を見つける必要があります。

上の画像には10個のポイントがあります。赤い線はドロネー三角形分割からのエッジであり、黒い星はエッジの正中線を示し、青い線はボロノイテッセレーションです。ポイント1には、3つの「近い」ネイバー、つまり4、6、および7がありますが、2と3はありません。これらは、エッジ1〜7とほぼ一致していますが、はるかに離れています。

近くの隣人（または「良い」エッジ）を識別するための良い方法は何ですか？図を見ると、中点がボロノイ線との交点に当たるエッジを選択するか、ボロノイセルに接触しているエッジを「近く」と見なすのが良い解決策であると思われます（3〜5の分類）。どちらにでも行くことができます）。Matlabでいずれかのソリューションを実装する効率的な方法はありますか（Matlabに変換できる優れた一般的なアルゴリズムを入手できれば幸いです）？

matplotlib を使用してポイント グループのドローネ三角形分割を生成する場合、生成された三角形の外心を取得する最も適切な方法は何ですか? これを行うための明白な方法を Triangulation ライブラリでまだ見つけることができませんでした。

x と y が通常のグリッド上にない (x、y、z) 形式のデータがあります。これらのデータの 2D カラーマップを、強度 (グレースケールなど) を z 変数にマッピングして表示したいと考えています。明らかな解決策は、通常のグリッドで補間 (以下を参照) することです。

ただし、これにより初期メッシュの情報 (実際のデータを含むポイントの位置) が失われ、特定の場所で非常に細かくまたは非常に粗くなる可能性があります。私の好みは、元のデータ ポイントの実際の位置と密度を正確に表す、三角形を使用した delaunay タイリングです。

理想的には、ソリューションは

• ggplot2結果のポリゴンが、lattice、またはベース グラフィックスのいずれかでプロットされるように、プロット関数の外でテッセレーションを計算します。

• 早くして。私の実際の例 (~1e5 ポイント) では、テッセレーション ビアの計算deldirが非常に遅くなる可能性があります。

「テッセレーション」とは、ドロネー三角形またはボロノイ図のいずれかを意味しますが、私の好みは前者です。ただし、元のデータ ポイントに基づいて各三角形の色を補間する複雑さが増します。

複雑な（ただし自己交差しない）ポリゴンを穴で三角形分割して、結果の三角形がすべてポリゴンの内側に配置され、そのポリゴンを完全に覆い、ドロネー三角形の規則に従うようにします。

もちろん、すべてのポイントに対してDelaunay三角形分割を作成することもできますが、ポリゴンの一部のエッジが結果の三角形分割に含まれないのではないかと心配しています。

それで、そのような三角測量は可能ですか？はいの場合、どうすればそれを行うことができますか？

念のため-ポリゴンの内側軸の近似を作成するために必要です（結果の三角形のすべての円周点を接続することで実行できることを願っています）。

私はこの Java コードを持っています。この Java コードは、一連の Point in input を使用して、Delaunay 三角形分割を表す一連のグラフのエッジを返します。

これを行うためにどのような戦略が使用されたか、存在する場合は使用されたアルゴリズムの名前を知りたいです。

このコードでは、GraphEdge は 2 つの awt Point を含み、三角形分割のエッジを表し、GraphPoint は Awt Point を拡張し、最終的な三角形分割のエッジは TreeSet オブジェクトで返されます。

私の目的は、この方法がどのように機能するかを理解することです。

この三角形分割の完全なソース コードの下:

これが入力ポイントの場合:

を Delauny Mesh Triangulation アルゴリズムに追加すると、3 次元のDelauny Mesh Triangulation アルゴリズムの出力はどうなるでしょうか?

A. これ:

またはB.これ [指定されたすべての入力ポイントの凸包]

答えは？AまたはB

Delaunay/Voronoi 三角測量機をほぼ完成させましたが、大変でした。Fortun のコードは使用していません。Delaunay 三角形分割器を作成し、そこからボロノイ図を導き出しました。

ただし、問題があります。無限の線。これらの無限の線で区切られたボロノイ セルを定義する方法が見つかりません。ほとんど何でも試しました。なにか提案を？

ポイントリスト=[p1、p2、p3 ...]があります。ここで、p1 = [x1、y1]、p2 = [x2、y2]..。

scipy.spatial.Delaunayを使用して、これらの点群で三角測量を行い、それをプロットしたいと思います。

これどうやってするの ？

Delaunayのドキュメントは本当に不足しています

これまでのところ私はこのコードを持っています

ありがとう

それについて読んだ後、私はこれに来ました：

これにより、外接円に点が含まれている面が見つかります。その後、これらの三角形を取得し、ポイントが三角形の内側にあるかどうかをテストする方法を使用する必要があります（CGALはこれを実行しますか？実装は簡単ですが）。

とにかく、どうすれば三角形を面から取り除くことができますか？

答えは

等

Triangleクラスの使い方はよくわかりませんが、少なくとも始まりです。

私は実際に答えるつもりでしたが、stackoverflowではそうすることができませんでした。