問題タブ [delaunay]

三角測量を構築するためのコード:

その後、ポイントの 1 つを使用してクエリを作成します。

結果が得られたら、ポイントが該当するかどうかを確認する必要があります。

• ファセット
• 縁
• バーテックス
• 定義された三角測量/長方形の外側

この場合、それは頂点です。

しかし、それに対する私のアプローチは両方とも失敗しました。最初の 3 行でlocate、パラメーターに正しいエッジが設定されているかどうかを確認してみました。そうではなく、セグメンテーション違反が発生しました。first2 番目のブロックで、構造体の要素にアクセスしようとしましたCvSubdiv2DPointが、これも機能しません。セグメンテーション違反です。ポイントを見つけることができずfirst、他のエッジで反復して使用することもできません。

役に立たない理由CvSubdiv2DPointは、構造を反復処理して実際に三角形を見つけるために が必要CvSubdiv2DEdgeだからですが、ポイントからエッジに変換できないため、関数の結果は役に立たないからです。

私は何かを見落としているかもしれませんが、私には壊れているようです。これがドキュメントです。何かご意見は？

一連の点からドロネー三角形分割を構築する.NET実装を探しています。

私はすでにいくつかの実装をテストしましたが、それらはすべて少量のポイント（最大20,000）でしか機能しませんでした。

リーズナブルな時間で50万点を扱えるものが必要です。

CGAL（C ++）の2Dドロネーグラフのすべてのエッジを取得/反復する方法は？

たとえば、MATLABでは、これは単なるedges（dt）です。

delaunay3()こんにちは、オクターブの関数の出力で四面体を視覚化する方法を知っている人はいますか?

http://www.obihiro.ac.jp/~suzukim/masuda/octave/html3/octave_151.html

MATLAB では、この可視化は関数で行われtetramesh()ますが、Octave にはこの関数が組み込まれていません!

リンクにはtriplotおよびtrimesh関数が記載されていますが、それらは三角形のみを作成し、四面体は作成しません。

私はCGALを初めて使用しています。私の質問は非常に簡単だと確信しています。

Delaunay 三角形分割を行うために CGAL を使用しようとしています。球体上に N 個の 3D ポイントを持つグリッドがあり、それらの点を三角形の頂点として使用して球体を三角形分割したいと考えています。そのような結果の三角形の頂点のリストを取得する必要があるだけです:

id_triangle1 vertex_1 vertex_2 vertex_3 id_triangle2 vertex_1 vertex_2 vertex_3 .......

私は三角測量を実行するためにそれをしました：

私が抱えている問題は、結果の三角形分割を取得する方法がわからないことです。face_iterator を取得する方法はわかりましたが、そこから何をすればよいかわかりません。

それが三角形を反復するのが正しいかどうかはわかりません。もしそうなら... 三角形 = 面 ??¿ 、つまり、各反復子の位置には三角形しかありません。各三角形の x、y、z を正しく取得するにはどうすればよいですか??

ボロノイ分割からk最近傍の集合を計算するのは比較的簡単です。逆の問題はどうですか？私はすでにk最近傍のセット（3D）を持っており、ボロノイセルの体積と中心を計算したいと思います。直感的には、それを行うO（n）アルゴリズムがあるはずですよね？

誰かがこのようなものがどこかに実装されているのを見たことがありますか？

前もって感謝します

PS：ボロノイセルにはk個を超えるエッジがないと思います（ポイントの位置に関するこの事前知識は、次元に関係なく、O（n）でダイアグラムを計算することを可能にするものです）。

PPS：さらに、特定の点について、ボロノイセルの頂点がkNNのセットに属していると仮定します（以下のコメントを参照）。

scipy (0.9.0) と matplotlib (1.0.1) の Delaunay 三角形分割ルーチンを比較すると、説明のつかない動作に気付きました。私のポイントは、に保存されている UTM 座標numpy.array([[easting, northing], [easting, northing], [easting, northing]])です。Scipy のエッジには私のポイントの一部がありませんが、matplotlib のエッジはすべてそこにあります。修正はありますか、それとも何か間違っていますか?

OpenCV 2.3.1 で輪郭の Delaunay 三角形分割をうまく実装しました。

cvPointPolygonTest を使用すると、凸包内のすべての三角形を取得できます。次に、三角形の重心に対して別の cvPointPolygonTest を実行して、それらが主な輪郭にあるかどうかを確認しようとしたため、輪郭の三角形分割を制限できます。

しかし、一部の三角形は (たとえば、2 本の足を離して歩いている人では)穴の上にあるため、うまく機能しません。

制約付き三角形分割を実行する方法を知っている人はいますか? 私は凸性欠陥について考えましたが、これから始める方法を理解することができません。

前もって感謝します ！

ベン

実際、これは凸包欠陥の問題ではなく、三角測量の問題です。この画像はあなたの問題を示します：

特に三角形分割されたハルの下部では、OpenCV が凸包を三角形分割しているため、三角形分割が輪郭の内側と外側にあることがわかります。輪郭自体を三角測量する方法を見つけたいと思います。

輪郭自体に Steiner Points を追加することについていくつかのアイデアを見つけましたが、OpenCV をどこから始めればよいかわかりません。

私の考えは次のとおりでした：

• 三角形が輪郭の内側と外側にあるかどうかをテストします。
• true の場合: 交点を取得します。
• cvSubdiv2D に追加します。

私はこれで正しいですか？

あなたの忍耐とあなたの答えに感謝します!

特定のデータセットでエッジに隣接するボロノイ領域を持つポイントを見つけようとしています。私は計算幾何学は初めてですが、オンラインで読んだところ、Delaunay テッセレーションを使用するとこれを行う簡単な方法になるようです。特にこのPDFには、次のような補題もあります

補題 2.4 S の 2 点は、それらのボロノイ領域が辺に隣接している場合、ドロネー辺によって結合されます。

だから、私は自分のデータセットのドローネーテッセレーションを次のように見つけました

しかし、これをこのデータセットのボロノイ図と一緒にプロットすると、ドロネー エッジが、実際にはエッジに隣接していない領域の接続点を返していることがわかります。

ボロノイとドローネを一緒にプロットするために使用したコードは次のとおりです。

出力は次のとおりです。

問題の例として、図の右端の X 点と、左下隅近くの Y 点を結びます。

もう 1 つの例は、この SO の質問にあります。ポイント 1 は、隣接していなくても 2 と 3 に接続されており、1 と 2 が無限に拡張されたとしてもエッジを共有できる方法はないようです。この質問は、実際に上記のコードで delaunayn の出力をテストするよう促したものです。

なぜこれが起こっているのですか? また、必要なエッジ隣接領域を実際に取得するにはどうすればよいですか?

注: 画像をフル サイズで明瞭に表示するには、右クリックして [画像を表示] などを選択してください。

三角形分割を含むオブジェクトがあり、オブジェクトで使用して、ポイントが三角形の内側にあるかどうかを確認しTriRepたいと考えています。pointLocationしかし、はのサブクラスである クラスpointLocationに対して定義されたメソッドです。DelaunayTriTriRep

TriRepでは、オブジェクトを変換しDelaunayTriて使用できるかどうかを尋ねたいと思いpointLocationますか?