問題タブ [triangulation]

私はDelaunay 三角形分割を研究しており(宿題ではありません)、次の問題について考えました:S平面上の点のセット (濃度がn) と三角形のセットT(濃度n-2が三角形のセットTは Delaunay 三角形分割を形成しDT(S)ますか?

最初の問題は、ドロネー三角形分割が一意ではないことです。そのため、ポイント セットを再構築して三角形セットと比較しても、答えが得られません。さらに、最適な Delaunay 三角形分割アルゴリズムを実装するのはかなり困難です (ただし、CGAL などのライブラリを使用することは問題ありませんでした)。

三角形集合が三角形分割であるかどうかをチェックする方法を知っていると仮定します (必ずしも Delaunay である必要はありません)。次に、Delanuay 三角形分割の定義を使用する必要があります。三角形分割のすべての三角形についてt、 の点はSの円周内に厳密にはありませんt。これにより、次の方法が得られます。

1. 些細なアプローチ。を反復しT、円周を計算して を反復しS、点が円周の内側にあるかどうかを確認します。ただし、これにはO(n^2)時間がかかり、最適とは言えません。
2. 魅惑のアプローチ。繰り返し、T円周を計算します。円周の内側にある点sは、円周の中心までの距離が半径よりも小さいことを意味します。上の最近傍探索構造を使用Sして、アルゴリズムを高速化します。たとえば、単純なkd ツリー構造からO(n log n)、平均的なアルゴリズムとO(n sqrt(n))最悪のケースのアルゴリズムが導き出されます。
3. もっと簡単なことを考えている人はいますか？

Tが三角形分割かどうかをチェックする問題に戻りましょう。の等価性や三角形の頂点のセットなどの些細な事前要件はS、 よりも速く実行できませんO(n log n)。残っていること — の 2 つの三角形ごとにT共通の面で交差するか、まったく交差しないかを確認します。

1. 繰り返しますが、交差をチェックしてTを何度も反復することでこれを行うことができますが、これはアルゴリズムです。TO(n^2)
2. t1«三角形とt2交差» の意味を考えてみましょう。それらのエッジが交差する場合、または 1 つの三角形が完全に別の三角形の中にある場合、それらは交差します。すべてのエッジを交差させる問題は、Bentley-Ottmann アルゴリズムO(n log n)を使用して一度に解決できます(最悪の場合は、は交差の数ですが、最初の交差が見つかった時点でアルゴリズムを停止できます)。また、ある三角形が別の三角形を完全に含む場合も認識していませんでしたが、Bentley-Ottmann アルゴリズムを修正して、セグメントではなくスイープ ラインと交差する三角形を維持できると信じています。ただし、実装は非常に複雑です。O((n + k) log n)kO(n log n)
3. 私は反復アルゴリズムについて考えました — 交差しない (またはエッジでのみ交差する) 三角形の構造を維持しましょう (kd-tree に非常に似たものにする必要があります)。次に、次の三角形 を追加しようとしますt。まず、tの頂点のいずれかが既に三角形の 1 つに含まれているかどうかを確認します。次に、交点が得られます。それ以外の場合は、構造に追加tします。ただし、検索してクエリを追加する時間が必要な場合はO(log n)、O(sqrt(n))この構造の高さのバランスを取る必要があります。これは、kd ツリーの場合でも困難です。

では、この問題の簡単な解決策を知っている人はいますか?

openmpを使用してGuibas Stolfi delaunay 三角形分割を並列化しようとしています。

ここで並列化することが 2 つあります。私はすべての可能なアプローチを試みましたが、無駄でした。

分割 () で従うアプローチ (分割 n 征服) は、マージソート () のアプローチと同じですが、同じ並列化手法 (omp セクション) の適用は、マージソートに対してのみ機能します。

ここに示す並列化手法を試しましたが、それでもうまくいきません。ネストされた並列処理についてどこかで読みましたが、それを実装する方法がわかりません。分割統治アルゴリズムがどのように並列化されているか説明できる人はいますか?

CODE:メイン関数と適用されたセクション構成でマージソートが 2 回呼び出されました。除算関数で同じことを行っても機能しません

GLUtesselator を使用して Text エンティティを三角測量しようとしたときに、この問題に遭遇しました。ただし、GLUtesselator を使用したポリゴンの三角形分割中に発生する可能性があります。問題は、GLUtesselator が面積ゼロの三角形を生成する場合があることです。ほとんどの場合は無視できますが、無視できない場合もあります。特定のポリゴンの最終的な三角形分割に面積ゼロの三角形または T 字路が含まれないように、解決策を見つけようとしています。私の知る限り、GLUtesselator は利用可能な最も堅牢で安定したテッセレータの 1 つであるため、自分で新しいテッセレータを作成するのではなく、後処理を行って三角測量を修正することを気にしません。

文字「H」のテッセレーションの問題を実証しようとします。私はスタックフローの新しいユーザーであるため、まだ画像を投稿することはできず、画像なしでこの問題を説明することは不可能であるため、問題を説明したブログに URL を投稿しているだけであることに注意してください。GLUtesselator で確認することもできます: 面積ゼロの三角形と T 交差に関する問題http://www.dixittech.com/blog

これは非常に根本的な問題であり、その解決策は、同様の分野で働く多くの開発者に利益をもたらすと思います。私はそれにつまずいた最初の人ではないと確信しています。それを行う方法について何か提案はありますか？代替アプローチも大歓迎です。

巡回セールスマンの問題に相当する経路計画アルゴリズムに取り組んでいます。ノードの数がわからないので、速度のために精度を犠牲にしてもかまいません。私の問題は、完全に接続されたグラフとしてモデル化できます。ノード間の遷移のコストは、ノード間の距離だけではありません。検索スペースをドロネー三角形分割上にある接続に制限したいのですが (私が読んだ調査では、TSP の解の接続の 95 ～ 100% がドロネー三角形分割上にあると書かれています) が、私のグラフは表現できないため、 2D または 3D ジオメトリとして、表現に直接使用することはできません。

3次元（4〜6）の場合よりも大きい三角形分割を作成したいと思います。非凸面を表すポイントがあります。2Dおよび3Dの場合、DelaunayTriが最適です。高次元はどうですか？

（元々の問題は、いくつかの非線形超曲面を線形超平面で近似することです）

よろしく、アンドレイ

メッシュ操作（データ構造、メッシュ単純化アルゴリズム、三角測量）用のツールを含むJava用のライブラリを探しています。http://gts.sourceforge.net/index.htmlのようなものですが、Java用です。

Stackにも同様の質問がありましたが、それは2009年のものであり、満足のいく答えはありませんでした...もう一度。

単調多角形のドロネー三角形分割に関する論文をインターネットと科学データベース全体で検索しました。私はポリゴンの任意の三角形分割を検索しているのではなく、ドロネー三角形分割のみを検索しています。単調多角形がドロネー三角形分割されているそのような出版物を知っている人はいますか？どうも！

私は非常にまばらなデータセットからワイヤレスネットワークの信号強度をマッピングしようとしていましたが、これを数学的に行うことさえ可能かどうか疑問に思いました。

携帯電話にアプリケーションがインストールされていて、各携帯電話が位置と信号強度を中央データベースにアップロードしていると想像してみてください。目標は、この非常にまばらなグラフを取得し、信号強度のマッピングを試みてから、ワイヤレスネットワークの有用な範囲を2次元または3次元で推測できるようにすることです。また、アクセスポイントのすぐ隣には誰も立っていないので、中心は不明だと思います。ポリゴンを描画するためのワイヤレスネットワークの有用なメッシュを生成する前に、非常に大まかにどの密度のポイントが必要でしょうか？

DBMで測定されたワイヤレスネットワークの強度は、距離に反比例して線形にスケーリングすることが期待できます。これを使用して、ドローネ変換の追加ポイントを生成できるかどうか疑問に思いました。

ワイヤーモードで多くの地形を見てきましたが、それらはすべて三角形を使用していました。さまざまな高さで使用するとわかりますが、なぜ人々は地形の平坦な領域にこれほど多くの三角形を使用するのでしょうか。大きな平らな領域がある場合は、小さなものをたくさん使用するのではなく、1つの大きな正方形または少なくとも1つの大きな三角形（できるだけ大きな）を作成するのが賢明ではないでしょうか。

だから私の質問は、これを行う理由はありますか（おそらくテクスチャのために）？テッセレーションがこのようなことをすることは知っていますが、それでも私の観点からは三角形が多すぎます。

次のコード（Pg.187、RourkeによるCのComputational Geom）は、シリアルおよびパラレル（2 proc）で実行するのに同じ時間がかかります。問題を特定するのを手伝ってください。これが平行部分です