2차원 보로노이 다이어그램(Voronoi Diagram)과 들로네 삼각분할(Delaunay Triangulation) 플로팅하기

이 예제에서는 동일한 2차원 플롯에 보로노이 다이어그램과 들로네 삼각분할을 보여줍니다.

2차원 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

P가 X의 어떤 점보다도 X9에 더 가까이 있는지 관찰해 보면, X9의 경계 영역 내에서 점 P가 그러한 것을 알 수 있습니다.

점 집합 X에 대한 보로노이 다이어그램은 X에 대한 들로네 삼각분할과 밀접한 관련이 있습니다. 이러한 관계를 보려면 점 집합 X에 대한 들로네 삼각분할을 생성하고 삼각분할 플롯을 보로노이 다이어그램에 겹쳐 놓으십시오.

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

이 플롯을 보면 점 X9와 연결된 보로노이 영역이 X9와 연결된 들로네 모서리의 수직이등분선으로 정의됨을 알 수 있습니다. 또한, 보로노이 모서리의 꼭짓점은 들로네 삼각형의 외심에 있습니다. 삼각형 {|X9|,|X4|,|X8|}의 외심을 플로팅하여 이러한 연관 관계를 표시할 수 있습니다.

이 삼각형에 대한 인덱스를 구하려면 삼각분할을 쿼리하십시오. 삼각형은 위치 (-1, 0)을 포함합니다.

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

이제, 이 삼각형의 외심을 구하고 이를 녹색으로 플로팅합니다.

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

들로네 삼각분할과 보로노이 다이어그램은 기하학에서 서로 쌍대입니다. 들로네 삼각분할에서 보로노이 다이어그램을 계산하거나 보로노이 다이어그램에서 들로네 삼각분할을 계산할 수 있습니다.

볼록 껍질의 점과 연결된 보로노이 영역(예를 들어, X13과 연결된 보로노이 영역)이 비유계(Unbounded)인지 살펴봅니다. 이 영역의 모서리는 무한대에서 "끝납니다". 들로네 모서리 (X13, X12)와 (X13, X14)를 이분하는 보로노이 모서리는 무한대로 이어집니다. 보로노이 다이어그램은 점 집합에 포함된 각 점의 주변 공간에 대해 최근접이웃 분해를 제공하지만, 최근접이웃 쿼리를 직접적으로 지원하지는 않습니다. 그러나, 보로노이 다이어그램을 구하는 데 사용되는 기하학 구조는 최근접이웃 탐색(쿼리)에 사용됩니다.

보로노이 다이어그램(Voronoi Diagram) 구하기

이 예제에서는 2차원 보로노이 다이어그램과 3차원 보로노이 다이어그램을 계산하는 방법을 보여줍니다.

MATLAB^®은 2차원 보로노이 다이어그램을 플로팅하는 함수와 N차원 보로노이 다이어그램의 위상을 계산하는 함수를 제공합니다. 6차원이 넘는 차원에서 보로노이 계산을 수행하는 것은 필요한 메모리가 기하급수적으로 증가하므로 중간 규모나 큰 규모의 점 집합에는 잘 사용되지 않습니다.

voronoi 플롯 함수는 2차원 점 집합에 대한 보로노이 다이어그램을 플로팅합니다. MATLAB에서는 다음 두 가지 방법으로 점 집합의 보로노이 다이어그램 위상을 계산할 수 있습니다.

voronoin 함수를 사용하면 N차원(N ≥ 2)에 있는 이산 점의 보로노이 위상을 계산할 수 있습니다. voronoiDiagram 메서드를 사용하면 2차원이나 3차원에 있는 이산 점의 보로노이 위상을 계산할 수 있습니다.

voronoiDiagram 메서드는 더 견고하며 대규모 데이터 세트에 사용할 때 뛰어난 성능을 제공하므로 2차원이나 3차원 위상을 계산하는 데 권장됩니다. 이 메서드는 점의 단계별 삽입과 제거 및 상호 보완적 쿼리(예: 최근접이웃 점 탐색)를 지원합니다.

voronoin 함수와 voronoiDiagram 메서드는 행렬 형식을 사용하여 보로노이 다이어그램의 위상을 나타냅니다. 이 데이터 구조에 대한 자세한 내용은 삼각분할 행렬 형식 항목을 참조하십시오.

점 집합 X가 주어진 경우, 보로노이 다이어그램의 위상을 구하는 방법은 다음과 같습니다.

[V,R] = voronoin(X)

dt = delaunayTriangulation(X);

[V,R] = voronoiDiagram(dt)

V는 보로노이 꼭짓점의 좌표를 나타내는 행렬입니다(꼭짓점은 보로노이 모서리의 끝점임). 일반적으로 V의 첫 번째 꼭짓점은 무한 꼭짓점입니다. R은 벡터 셀형 배열의 길이 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

     8    12    17    10    14

보로노이 꼭짓점들의 인덱스는 V 배열에 대한 인덱스입니다.

마찬가지로, R{4}는 점 영역 X4와 연결된 보로노이 꼭짓점들의 인덱스를 제공합니다.

R{4}

ans = 1×5

     4     8    14     9     7

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')