%% Computing the Voronoi Diagram
% This example shows how to compute a 2-D and 3-D Voronoi diagram.
%% Section 1
% Given a set of points, X, obtain the topology of the Voronoi diagram as follows:
% Using the voronoin function
%    [V,R] = voronoin(X)
% Using the voronoiDiagram method
%    dt = delaunayTriangulation(X);
%    [V,R] = voronoiDiagram(dt)
% V is a matrix representing the coordinates of the Voronoi vertices (the vertices are the end points of the Voronoi edges). By convention the first vertex in V is the infinite vertex. R is a vector cell array length size(X,1), representing the Voronoi region associated with each point. Hence, the Voronoi region associated with the point X(i) is R{i}.
% Define and plot the voronoi diagram for a set of points

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} gives the indices of the Voronoi vertices associated with the point site X9.

R{9}

% The indices of the Voronoi vertices are the indices with respect to the V array.
%
% Similarly, R{4} gives the indices of the Voronoi vertices associated with the point site X4.

R{4}

% In 3-D a Voronoi region is a convex polyhedron, the syntax for creating the Voronoi diagram is similar. However the geometry of the Voronoi region is more complex. The following example illustrates the creation of a 3-D Voronoi diagram and the plotting of a single region.
%
% Create a sample of 25 points in 3-D space and compute the topology of the Voronoi diagram for this point set.

X = -3 + 6.*gallery('uniformdata',[25 3],0);
dt = delaunayTriangulation(X);

%
% Compute the topology of the Voronoi diagram.

[V,R] = voronoiDiagram(dt);

%
% Find the point closest to the origin and plot the Voronoi region associated with this point.

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

% Copyright 2015 The MathWorks, Inc.