# Divide a 3D shape into equal-volume subregions?

34 views (last 30 days)
KAE on 24 Feb 2020
Edited: KAE on 26 Feb 2020
I have a 3D shape that can be approximated with Delauny triangularization or a convex hull. I would like to divide the shape into a certain number of equal-volume subregions; ideally each subregion would have nearly the same surface area. Here are a couple places I looked but did not find a solution,
Below is an example conical 3D shape. How can I divide the volume enclosed by the shape into 100 equal-volume subregions? The subregions can all be entirely enclosed by the hull, leaving some of the shape's volume unenclosed by subregions, as if you were to fill a conical container with ice cubes.
Is the best way just to grid the region in xyz and adjust the grid spacing until I get 100 cubes?
load('seamount.mat', 'x', 'y', 'z'); % Generic data that comes with Matlab; contains 3D points
DT = delaunayTriangulation(x,y,z); % 3D triangulization of points
[C, volHull] = convexHull(DT); % Compute convex hull, which is cone-shaped
figure('Name', 'Convex Hull');
hPatch = trisurf(C,DT.Points(:,1),DT.Points(:,2),DT.Points(:,3), ...
'FaceAlpha', 0.1);
% Now how to find 100 subregions of equal volume within this shape
KAE on 25 Feb 2020
Perhaps I should take my cue from the fact that voxels are usually shown as cubes, and stick to cube shapes. Thanks for the suggestion to define the problem more clearly: I am trying to come up with regular locations inside a 3D shape for a sampling problem. So I will divide the shape up into 3D cubes of equal size, requiring that the cubes fit fully inside. I put a draft of how to do this in my answer.

KAE on 26 Feb 2020
Edited: KAE on 26 Feb 2020
Based on the comments, my original question was too open ended, so I am answering this to bring it to a close. A simple 3D division of the space inside the volume into cubes is good enough, something like,
load('seamount.mat', 'x', 'y', 'z'); % Generic data that comes with Matlab; contains 3D points
% Make the example shape less flat!
x = x*5000;
y = y*8000;
DT = delaunayTriangulation(x,y,z); % 3D triangulization of points
[C, volHull] = convexHull(DT); % Compute convex hull, which is cone-shaped
figure('Name', 'Convex Hull');
hPatch = trisurf(C,DT.Points(:,1),DT.Points(:,2),DT.Points(:,3), ...
'FaceAlpha', 0.1);
nCubesDesired = 100;
cubeLength = range(z)/round(nCubesDesired^(1/3));
xGrid = min(x):cubeLength:max(x);
yGrid = min(y):cubeLength:max(y);
zGrid = min(z):cubeLength:max(z);
% Loop through each cube and check if it is inside the volume using
% in_polyhedreon from File Exchange
% https://www.mathworks.com/matlabcentral/fileexchange/48041-in_polyhedron
% If it is not inside the volume, throw the cube out.
set(gca, 'xtick', xGrid, 'ytick', yGrid, 'ztick', zGrid);
grid on;
% Iterate on cubeLength until you get the desired number of cubes
##### 2 CommentsShowHide 1 older comment
KAE on 26 Feb 2020
Sorry, I was not clear. I just meant I would slice up the 3D space's volume into equal-sized cubes. I moved the draft of how to do this from my comment to the answer.