function [v, c] = voronoin(x)
%VORONOIN  N-D Voronoi diagram.
%   [V, C] = VORONOIN(X) returns Voronoi vertices V and the Voronoi cells C
%   of the Voronoi diagram of X. V is a numv-by-n array of the numv Voronoi 
%   vertices in n-D space, each row corresponds to a Voronoi vertex. C is
%   a vector cell array where each element is the indices into V of the vertices
%   of the corresponding Voronoi cell. X is an m-by-n array, representing m
%   n-D points.
%  
%   Example: 
%   If 
%     x = [ 0.5 0; 0 0.5; -0.5 -0.5; -0.2 -0.1; -0.1 0.1; 0.1 -0.1; 0.1 0.1]
%   Then
%    [V, C] = VORONOIN(x);
%   gives
%
%   V = [Inf       Inf
%        0.3833    0.3833
%        0.7000   -1.6500
%        0.2875    0.0000
%       -0.0000    0.2875
%       -0.0000   -0.0000
%       -0.0500   -0.5250
%       -0.0500   -0.0500
%       -1.7500    0.7500
%       -1.4500    0.6500]
%
%   C{:} = 4 2 1 3
%	       10 5 2 1 9
%	       9 1 3 7
%	       10 8 7 9
%	       10 5 6 8
%	       8 6 4 3 7
%	       6 4 2 5
%
%   In particular, the fifth Voronoi cell consists of 4 points: V(10,:), V(5,:),
%   V(6,:), V(8,:).
%
%   For 2-D, vertices in C are listed in adjacent order, i.e. connecting
%   them will generate a closed polygon (Voronoi diagram). For 3-D
%   and above, vertices are listed in ascending order. To generate
%   a particular cell of the Voronoi diagram, use CONVHULLN to compute
%   the facets of that cell, e.g. to generate the fifth Voronoi cell,
%
%    X = V(C{5},:);
%    K = convhulln(X);

%
%   VORONOIN is based on Qhull.
%
%   See also VORONOI, QHULL, DELAUNAYN, CONVHULLN.

%   Copyright 1984-2000 The MathWorks, Inc.
%   $Revision: 1.10 $ $Date: 2000/08/22 15:47:35 $

[m,n] = size(x);
if any(isinf(x(:)) | isnan(x(:)))
  error('Data containing Inf or NaN cannot be tessellated.');
end
if m < n+1,
  error('Not enough points to do tessellation.');
end

% qhull needs the sum of squares at the end of the points
x = [x sum(x.*x,2)];
[v, c] = qhullmx(x', 'v ', 'QJ ', ' o', ' Pp');


