Voronoi Tessellation - Volume Calculation

Dear all,

I have a large 3D dataset of points within the unit sphere. My aim is to perform a Voronoi tessellation on this point-set and then to determine the volume of each Voronoi cell. In order to do so I wrote the following programme which has worked tremendously fine until now.

% X is the set of 3d points with dimension Nx3
    [C, ia, ic] = unique(X,'rows'); % All non unique points are removed
    B = 1:size(X,1);
    missingvalues = setdiff(B,ia); 
    [Y,PS] = removerows(X,'ind', missingvalues);
    volume = zeros(1,size(Y,1));
    tic
    [V,C] = voronoin(Y, {'Qbb'}); % Calculate Tessellation
    toc
    V(~isfinite(V)) = 0;
    tic
     for j=1:length(C)
         X2 = [V(C{j},1) V(C{j},2) V(C{j},3)];
         [K, V2] = convhulln(X2);
         volume(j) = V2;
     end 
    toc
      end

Now the problem is the following: Every time I run the shown code section with a given data-set (double values) the code crashes during the very last execution of [K, V2] = convhulln(X2) for j=length(C), showing the message:

Error using cgprechecks (line 40)
Not enough unique points specified.
Error in convhulln (line 41)
cgprechecks(x, nargin, cg_opt);

The input dataset X has dimensions 4.214.761x3 (double). If I randomly choose 100.000 3d points out of this dataset using

US_Pts = 100000;
Sze = size(X,1) 
p = randperm(Sze);
for i = 1:US_Pts
  US(i) = p(i);
end
X = X(US,:);

then the volume calculation runs through and delivers correct volumes. If I randomly choose e.g. 200.000 pts or more, then the code crashes under the same error. In the past, the code segment worked fine even for more than 1 million 3D points. I have no clue what causes the problem and why it always crashes during the last iteration although all points are randomly picked and ordered. If the programme crashes all calculated volumes do not appear to be plausible although it's executed fine up to the last iteration.

Any help or suggestions are highly appreciated! Thanks, Toby

Answer 1

[Toby997]

See the reduced point-set attached (200.000 pts) for which it already crashes.