Partition Domain Given Data of the Form w = f(x,y,z)

I have 4 vectors of size 1 x 15e8. The data is of the form

w = f(x,y,z)

I want to break the domain of x,y,z into cells or elements just like dividing a prism into smaller parts. This can be done by dividing x into 50 segments, y into 100 segments, and z into 400 segments. Therefore the number of elements of the whole domain of x, y, z is 50*100*400 = 2,000,000 cells. However, not all the cells will contain data. The way I handled this was to use a triple for loop like so

 xPartitions = linspace(min(x), max(x),50);
 yPartitions = linspace(min(y), max(y),100);
 zPartitions = linspace(min(z), max(z), 400);
 xWidth = diff(xPartitioned(1:2));
 yWidth = diff(yPartitioned(1:2));
 zWidth = diff(zPartitioned(1:2));

 wPartitioned = zeros(50*100*400,1);
 xPartitioned = zeros(50*100*400,1);
 yPartitioned = zeros(50*100*400,1);
 zPartitioned = zeros(50*100*400,1);

 for iX=xPartitions
     for iY=yPartitions
         for iZ=zPartitions
    % index of x,y,z within current cell
    index = (x >= iX - xWidth/2  & x <= iX + xWidth /2) & ...
      (y >= iY - yWidth/2  & y <= iY + yWidth/2 ) & ...
      (z >= iZ - zWidth/2  & z <= iZ + zWidth/2 );
    xPartitioned = mean(x(index));
    yPartitioned = mean(y(index));
    zPartitioned = mean(z(index));
    wPartitioned = mean(w(index));
    end % end for, z
  end % end for, y
 end % end for, x

 % delete cells that did not have any points in them
 index2 = isnan(xPartitioned);
 xPartitioned(index2) = [];
 yPartitioned(index2) = [];
 zPartitioned(index2) = [];
 wPartitioned(index2) = [];

 save('data.mat', 'xPartitioned', 'yPartitioned', 'zPartitioned', 'wPartitioned');

 % plot
 scatter3(xPartitioned, yPartitioned, zPartitioned,[], wPartitioned,'.');

The problem is this takes all night to run. Also, this method does not expand well for higher dimensions.

So finally, my question is:

Is there a way I can exploit the structure of the x,y,z points to speed up this process of partitioning the domain?

Answer 1

[Jason Nicholson]

The function below exploits the fact that you can use the point u = [x,y,z] to calculate the partition location of the point. Once this is done, only partition containing points need processed. This converts the above problem from an O(n^3) problem to an O(n) problem. I have found that this method works really well for dividing data into partitions and finding the local mean in the partitions. This is about 10,000 times faster than the code listed above in my experience.

See File Exchange for code:

http://www.mathworks.com/matlabcentral/fileexchange/46970-partition-domain