Main Content

이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.

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

이산 점 집합 X에 대한 보로노이 다이어그램은 각 점 X(i)의 주변 공간을 영향 영역 R{i}로 분해합니다. 이러한 분해에서는 영역 R{i} 내에 있는 임의의 점 P가 어떤 점보다도 점 i에 더 가깝다는 특성을 가집니다. 이러한 영향 영역을 보로노이(Voronoi) 영역이라고 하며, 모든 보로노이 영역의 모음이 보로노이 다이어그램입니다.

보로노이 다이어그램은 N차원 기하학 구조이지만, 실제로는 대부분 2차원 공간과 3차원 공간에 사용됩니다. 보로노이 다이어그램의 특성은 예를 통해 가장 잘 이해할 수 있습니다.

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

Figure contains an axes. The axes contains 19 objects of type line, text.

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

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

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

Figure contains an axes. The axes contains 20 objects of type line, text.

이 플롯을 보면 점 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

Figure contains an axes. The axes contains 21 objects of type line, text.

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

볼록 껍질의 점과 연결된 보로노이 영역(예를 들어, 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가 주어진 경우, 보로노이 다이어그램의 위상을 구하는 방법은 다음과 같습니다.

  • voronoin 함수 사용

[V,R] = voronoin(X)

  • voronoiDiagram 메서드 사용

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

Figure contains an axes. The axes contains 66 objects of type line, text.

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

Figure contains an axes. The axes with title 3-D Voronoi Region contains an object of type patch.

관련 항목