ボロノイ線図

離散点 X の集合のボロノイ線図は、各点 X(i) のまわりで空間を領域 R{i} へ分解します。この分解は、R{i} 領域内にある任意の点 P が他の点よりも点 i に近い性質をもっています。影響範囲は、ボロノイ領域と呼ばれ、ボロノイ領域のすべての集合がボロノイ線図です。

ボロノイ線図は N 次元の幾何構成ですが、実際の用途は 2 次元および 3 次元空間であることがほとんどです。ボロノイ線図の性質は例を使うと理解が深まります。

2 次元ボロノイ線図と Delaunay 三角形分割のプロット

この例では、同じ 2 次元プロットにボロノイ線図と Delaunay 三角形分割を表します。

2-D の関数 voronoi を使用して、点集合のボロノイ線図をプロットします。

figure()
X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; ...
      0.8 1.2; 3.3 1.5; -4.0 -1.0;-2.3 -0.7; ...
      0 -0.5; 2.0 -1.5; 3.7 -0.8; -3.5 -2.9; ...
     -0.9 -3.9; 2.0 -3.5; 3.5 -2.25];
 
voronoi(X(:,1),X(:,2))

% Assign labels to the points.
nump = size(X,1);
plabels = arrayfun(@(n) {sprintf('X%d', n)}, (1:nump)');
hold on
Hpl = text(X(:,1), X(:,2), plabels, 'FontWeight', ...
      'bold', 'HorizontalAlignment','center', ...
      'BackgroundColor', 'none');

% Add a query point, P, at (0, -1.5).
P = [0 -1];
plot(P(1),P(2), '*r');
text(P(1), P(2), 'P', 'FontWeight', 'bold', ...
     'HorizontalAlignment','center', ...
     'BackgroundColor', 'none');
hold off

X9 の境界を示す領域内にある任意の点 P に対して true になる、X 内の P は他のどの点よりも X9 に近いことを確認します。

点集合 X のボロノイ線図は、X の Delaunay 三角形分割と密接に関連しています。この関係を見るには、点集合 X の Delaunay 三角形分割を作成し、ボロノイ線図に三角形分割プロットを重ね合わせます。

dt = delaunayTriangulation(X);
hold on
triplot(dt,'-r');
hold off

点 X9 と関連付けられるボロノイ領域は、X9 に接続された Delaunay エッジの垂直な二等分線で定義されることがプロットからわかります。また、ボロノイ エッジの頂点は、Delaunay 三角形の外心に配置されています。この関係は三角形 {|X9|,|X4|,|X8|} の外心をプロットすることで、示すことができます。

この三角形のインデックスを求めるには、三角形分割にクエリを行います。三角形は位置 (-1, 0) を含みます。

tidx = pointLocation(dt,-1,0);

ここで、この三角形の外心を求めて、それを緑色でプロットします。

cc = circumcenter(dt,tidx);
hold on
plot(cc(1),cc(2),'*g');
hold off

Delaunay 三角形分割とボロノイ線図はお互いに幾何双対です。ボロノイ線図を Delaunay 三角形分割から、またはその逆に計算できます。

凸包上の点と関連付けられるボロノイ領域は境界がありません (たとえば、X13 と関連付けられたボロノイ領域)。この領域のエッジは、無限で "終わります"。Delaunay エッジ (X13、X12) と (X13、X14) を二等分するボロノイ エッジは、無限に広がります。ボロノイ線図は、セットの各点の周りにある空間の最近傍分解を提供する一方、それは最近傍境界線を直接サポートしていません。ただし、ボロノイ線図を計算するために使用される幾何構造は、最近傍探索を実行するためにも使用されます。

ボロノイ線図の計算

この例では、2 次元および 3 次元ボロノイ線図を計算する方法を示します。

MATLAB^® は、2 次元にボロノイ線図をプロットし、N 次元でのボロノイ線図のトポロジを計算するための関数を提供します。実際には、必要なメモリが指数関数的に増えるため、中規模から大規模のデータセットの 6 次元を超える次元では、ボロノイ計算は実際的ではありません。

プロット関数 voronoi は、2 次元空間の点集合のボロノイ線図をプロットします。MATLAB では、点集合のボロノイ線図のトポロジを計算するため以下の 2 つの方法があります。

• 関数 voronoin を使用します。

• delaunayTriangulation メソッド voronoiDiagram を使用します。

関数 voronoin は、N 次元 (N ≥ 2) の離散点に対するボロノイ線図のトポロジの計算をサポートします。voronoiDiagram メソッドは、2 次元または 3 次元の離散点に対するボロノイ線図のトポロジの計算をサポートします。

voronoiDiagram メソッドは、よりロバストであり、大規模なデータセットに対してより優れた性能を発揮するので、2 次元または 3 次元のトポロジの計算に推奨されます。このメソッドは、インクリメンタルな挿入や点の削除、最近傍での点探索のような補完的探索要求をサポートしています。

関数 voronoin と voronoiDiagram メソッドは、行列形式を使用してボロノイ線図のトポロジを表します。このデータ構造体に関する詳細は、三角形分割の行列形式 を参照してください。

点集合 X が与えられた場合、ボロノイ線図のトポロジは次のようにして求めます。

• 関数 voronoin を使用する

[V,R] = voronoin(X)

• voronoiDiagram メソッドを使用する

dt = delaunayTriangulation(X);

[V,R] = voronoiDiagram(dt)

V は、ボロノイ頂点の座標を表す行列です (頂点はボロノイ エッジの終点)。慣例により、V の最初の頂点は無限遠頂点です。R は、ベクトルの cell 配列の長さ size(X,1) で、各点に関連付けられているボロノイ領域を表します。したがって、点 X(i) に関連付けられているボロノイ領域は R{i} です。

点集合のボロノイ線図を定義してプロットします。

X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; 0.8 1.2; ...
      3.3 1.5; -4.0 -1.0; -2.3 -0.7; 0 -0.5; 2.0 -1.5; ...
      3.7 -0.8; -3.5 -2.9; -0.9 -3.9; 2.0 -3.5; 3.5 -2.25];
[VX,VY] = voronoi(X(:,1),X(:,2));
h = plot(VX,VY,'-b',X(:,1),X(:,2),'.r');
xlim([-4,4])
ylim([-4,4])

% Assign labels to the points X.
nump = size(X,1);
plabels = arrayfun(@(n) {sprintf('X%d', n)}, (1:nump)');
hold on
Hpl = text(X(:,1), X(:,2)+0.2, plabels, 'color', 'r', ...
      'FontWeight', 'bold', 'HorizontalAlignment',...
      'center', 'BackgroundColor', 'none');
  
% Compute the Voronoi diagram.
dt = delaunayTriangulation(X);
[V,R] = voronoiDiagram(dt);


% Assign labels to the Voronoi vertices V.
% By convention the first vertex is at infinity.
numv = size(V,1);
vlabels = arrayfun(@(n) {sprintf('V%d', n)}, (2:numv)');
hold on
Hpl = text(V(2:end,1), V(2:end,2)+.2, vlabels, ...
      'FontWeight', 'bold', 'HorizontalAlignment',...
      'center', 'BackgroundColor', 'none');
hold off

R{9} は、点の場所 X9 に関連付けられているボロノイ頂点のインデックスを返します。

R{9}

ans = 1×5

     5     7    17    12     9

ボロノイ頂点のインデックスは、配列 V に対するインデックスです。

同様に、R{4} は、点の場所 X4 に関連付けられているボロノイ頂点のインデックスを返します。

R{4}

ans = 1×5

     5     9    11     8     6

3 次元では、ボロノイ領域は凸多面体であり、ボロノイ線図を作成するための構文は類似しています。ただし、ボロノイ領域の形状はより複雑になります。次の例では、3 次元ボロノイ線図の作成と、単一領域のプロットについて説明します。

3 次元空間の 25 個の点のサンプルを作成し、この点集合のボロノイ線図のトポロジを計算します。

rng('default')
X = -3 + 6.*rand([25 3]);
dt = delaunayTriangulation(X);

ボロノイ線図のトポロジを計算します。

[V,R] = voronoiDiagram(dt);

原点に最も近い点を見つけ、この点に関連付けられたボロノイ領域をプロットします。

tid = nearestNeighbor(dt,0,0,0);
XR10 = V(R{tid},:);
K = convhull(XR10);
defaultFaceColor  = [0.6875 0.8750 0.8984];
trisurf(K, XR10(:,1) ,XR10(:,2) ,XR10(:,3) , ...
        'FaceColor', defaultFaceColor, 'FaceAlpha',0.8)
title('3-D Voronoi Region')

関連するトピック

• 空間探索

×

例を開く

この例の変更されたバージョンがあります。編集された方の例を開きますか?

いいえ、変更されたバージョンを上書きします。 はい