1

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

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

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

dt = delaunay(dataset); %using delaunayn() since dataset can be multidimensional

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

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

voronoi(dataset(:, 1),dataset(:, 2));
hold on;

dt = delaunayn(dataset);
triplot(dt, dataset(:, 1), dataset(:, 2), 'red');

出力は次のとおりです。ボロノイ ドローネー プロット

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

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

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

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

4

1 に答える 1

2

私が見る限り (図の品質はあまり良くありません)、X と Y の領域はプロットされた部分の下に隣接している必要があります。十分にズームアウトすると、それらが表示されるはずです。

つまり、X と Y が交わるエッジは存在しますが、プロットには表示されません。

次の図は、プロット領域の外側のボロノイ図を示していませんが、上記の交点を見つける方法を示しています (二等分線はここには表示されていないことに注意してください)。 拡張ボロノイ図

于 2011-11-24T07:23:02.033 に答える