The volume of requests for artificial blocks inside a convex hull

Question

Problem:

I have a three-dimensional point cloud, each centroid of a block representing a block. For simplicity, this example is simply two-dimensional. As shown in the figure, I want to include items of interest based on a parameter. In the case here, the block is 1,6,5,4. To continue processing them, I need to find the smallest enclosure around them using an alpha shape or convex enclosure. I have the coordinates of each centroid, and I know the extension of the block, so I can easily find the boundary point of the blocks:

xdimension=5; ydimension=5; block1=[5 15 1]; block2=[5 10 0]; block3=[5 5 0]; block4=[10 5 1]; block5=[10 10 1]; block6=[10 15 1]; block7=[15 5 0]; block8=[15 10 0]; block9=[15 15 0]; blocks=[block1;block2;block3;block4;block5;block6;block7;block8;block9] dimension=[xdimension/2 ydimension/2]; point1=[1 1].*dimension; point2=[1 -1].*dimension; point3=[-1 1].*dimension; point4=[-1 -1].*dimension; i=size(blocks,1); point1=repmat(point1,i,1); point2=repmat(point2,i,1); point3=repmat(point3,i,1); point4=repmat(point4,i,1); edges1=[blocks(:,1:2)+point1, blocks(:,3)] ; edges2=[blocks(:,1:2)+point2, blocks(:,3)]; edges3=[blocks(:,1:2)+point3, blocks(:,3)]; edges4=[blocks(:,1:2)+point4, blocks(:,3)]; edges=[edges1;edges2;edges3;edges4]; x=edges(edges(:,3)==1,1); y=edges(edges(:,3)==1,2); K=convhull(x,y) scatter(edges(:,1), edges(:,2)) hold on plot(x(K),y(K),'r-') hold off 

This creates an image similar to the image.

Question

How can I query for a surface (or in my real volume problem) that is included in the convex hull of blocks 2 and 3? I need the exact surface / volume of each individual block, included separately from those that I specify as (here with a binary indicator). Please note that this is an example, and I am looking for ideas on how to do this regardless of the example. I would really appreciate some help because I am very stuck here and I have no idea how to handle this.

Answer 1

In 2D, I would use the inpolygon function to check if the point is inside the intersection of the convex hull and squares 2 and 3.

For 3D, I did not find the equivalent in MATLAB, but the next mllab exchange file , which should be the solution.

An example of how to use the function to find the points of the areas inside:

 % Create a 3D cube cubePoints = randi(5,[500,3]); % Bounding volume boundingVolume = zeros(8,3); boundingVolume(1,:) = [1,3,1]; boundingVolume(2,:) = [1,3,3]; boundingVolume(3,:) = [3,3,1]; boundingVolume(4,:) = [3,3,3]; boundingVolume(5,:) = [3,1,3]; boundingVolume(6,:) = [3,1,1]; boundingVolume(7,:) = [2,1,1]; boundingVolume(8,:) = [2,1,3]; % Find points inside area inVol = inhull(cubePoints,boundingVolume); % Plot the point in the bounding volume in blue and the points outsode the % bounding volume in red scatter3(cubePoints(:,1).*inVol,cubePoints(:,2).*inVol,cubePoints(:,3).*inVol,36,'blue'); hold on scatter3(cubePoints(:,1).*~inVol,cubePoints(:,2).*~inVol,cubePoints(:,3).*~inVol,36,'red'); 

Answer 2

If you manage to find the covex package (using the convhull function), its second output variable will give you what you need (?).

 [IDs,V] = convhull(X,Y,Z) 

Here V is the volume enclosed in the convex hull of points (X,Y,Z) . Bless Matlab!

Answer 3

I believe this method works, but if the system is large, then from the point of view of memory consumption, it has nothing to show:

First, we construct the full convex hull in the form of a three-dimensional binary array . In addition, each block must form a three-dimensional binary array throughout the space, with true elements within the block and false elsewhere. (To accomplish this, check the link in Amitay's Answer .)

Now you can calculate the share of each block from it. If you configured everything as described, the rest is simple: you can directly calculate the overlap conv with each block as follows:

 num = numel(block); shareofblock = zeros(num, 1); for jj = 1:num overlap = block(jj) & conv; shareofblock(jj) = sum(overlap(:)); end