問題タブ [voronoi]

画像に線を引くための関数ファイルを作成しました[img]=drawline(point1,point2,color,img)。これは、画像内にある任意の2点を接続するために使用されます。画像にボロノイ図を作成するように求められます（プロット機能を使用していません）。今のところ、画像に線を表示しようとしていますが、ポリゴンのエッジの頂点を取得する方法がわかりません。

私はいくつかのテストコードを使用しています：

私は上までしか知りません、次に私for loopは頂点を並べるために使う必要があると思います。どうやって始めたらいいのかわからない。また、ネガティブで無限の問題を画像（ピクセル座標）で表示する必要がある場合、それらを解決する方法にもこだわっています。

楕円を囲むボロノイ図を実装するアルゴリズムはありますか? 図は、ここの写真のようになります楕円のボロノイ図

それに関連するリンク、チュートリアル、コードなどを共有できますか?

前もって感謝します。

Mathematica で大きな問題が発生しました（バージョン8を使用）。ボロノイ図をプロットするのは簡単ですが、ノルムを変更するのはどうでしょうか?

L_2 ノルム (ユークリッド ノルム) に対応するボロノイ図が表示されます。L_1-norm と L_infinity-norm に対応するダイアグラムも必要です...

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

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

前もって感謝します

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

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

2D空間に2つの凸多角形がある場合、線上の任意の点で、いずれかの凸多角形の最も近い点から等距離にある線分をどのように作成しますか？

点ではなく凸多角形のボロノイ図の実装を検討していますが、2つの多角形だけの線の計算を開始する方法がわかりません。だから私はこれを一度に一歩踏み出してここから始めると思いました。

編集質問をもう少し明確にするために、平面（またはそのサブセット）を二等分したいと思います。

左側にポリゴンA、右側にポリゴンBがあるとします。平面を左側の点と右側の点に分割する二等分線があります。線上のすべての点は、どちらのポリゴンからも等距離にあります。線の左側のすべての点は、ポリゴンBよりもポリゴンAに近くなります。線の右側のすべての点は、ポリゴンBに最も近くなります。

これは、私が書いたMatlabスクリプトによって生成された、ブルートフォース近似を強制する画像です。

問題は、2つのポリゴンの「間」のスペースを調べるほど単純ではないと思います。これは、線が2つの形状の間の領域を直接超えて延びる必要があるためです。そして理想的には、2つ以上の形状に一般化する解決策を見つけたいと思います。これは、私には、問題をさらに複雑にしているように見えます。これは、それがどのように見えるかについての（明らかに非常に大まかな）概算です：

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

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

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

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

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

出力は次のとおりです。

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

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

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

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

ノード割り当ての問題

私が解決したい問題は、指定された入力ポイントとして指定されたブルー ノード (ソース ノード) で指定されたマップをテッセレーションすることです。これができたら、各セル内にいくつのブラック ノード (デマンド ノード) があるかを確認したいと思います。そのセルに関連付けられた青色ノードに割り当てます。

フォーチュンのアルゴリズムを使用せずにこれを行う簡単な方法があるかどうかを知りたいのですが、Mahotas.segmentation.gvoronoi(image) sourceと呼ばれるこの関数に出会いました。しかし、これで問題が解決するかどうかはわかりません。

また、このセグメンテーションを行うより良い方法があれば教えてください (ボロノイ テッセレーション以外)。クラスタリング アルゴリズムが適切な選択であるかどうかはわかりません。私はプログラミング初心者です。

QT の QGraphicsScene にいくつかの点をプロットし、それらを点クラスにカプセル化しました。これらの点のボロノイ図を計算してシーンに表示したいと思います。これを行う最善の方法は何ですか？

CGALを使おうと思っていたのですが、いい方法が見つかりません。

ボロノイ図を作成するためのFortunes アルゴリズムを実装する必要があります。

アルゴリズムの重要な部分は、「Beach Line Data Structure」と呼ばれるデータ構造です。

これは、AVL に似たバイナリ バランス ツリーですが、データがリーフにのみ格納されるという点で異なります (他にも違いがありますが、質問には重要ではありません)。

実装方法がわかりません。明らかに、AVL を「そのまま」使用することは機能しません。これは、AVL ツリーのリーフ ノードをバランスさせると、内部ノードになり、その逆になる可能性があるためです。

ウィキペディアで他の既知のデータ構造も調べてみましたが、ニーズに合ったものはありませんでした。連結リストでこれを行ういくつかの実装を見てきましたが、連結リストの検索は O(n) であり、アルゴリズムを効率的にするには O(log n) である必要があるため、これは良くありません。

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

フィリップ