このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

ボロノイ線図

離散点 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 メソッドは、行列形式を使用してボロノイ線図のトポロジを表します。このデータ構造体に関する詳細は、三角形分割の行列形式 を参照してください。

関連するトピック

• 空間探索