Fitting cube of maximum volume into a body/volume of arbitrary shape

Hi there,

I got an idea what I try to implement in Matlab. I got a volume of points in space, given by their carthesian coordinates, unequaliy distributed but there is a clear border. So a clowd of points. (In robotics we call this work space.) Two pictures, as they say more than 100 words. http://robothand.eu/uploads/img/catalog/1/arm2.jpg http://3.bp.blogspot.com/-YBXnPwDCUPs/TpxLD2rnanI/AAAAAAAAVis/2ElQGqQoz1w/s1600/Workspace.png (more complex)

Now I try to find a way to fit an maximum sized Square into that volume.

Maybe the representation of the work space it not perfect as a clowd of points, maybe transforming this to a geometric shape is better?

Basically it is a mathematical problem (optimisation maybe?), but I couldn't find any papers or so on that.

Any ideas?

Cheers Johannes

[Ahmet Cecen]

This is an interesting exercise, if you share a sample cloud, preferably with an irregular shape, I can play with a couple quick ideas that pop to mind and get back to you.

[Johannes Schürmann]

Good idea!

This (attached) are the X, Y and Z coordinates of an simple 3 rotational joint robot with some joint limitations. ( somthing like this: http://www.tareksobh.org/html/proj/sanjeev/Pic7.jpg )

plot-example:

figure(1);
plot3(X(:,1),Y(:,1),Z(:,1),'.');
xlabel('x');
ylabel('y');
zlabel('z');
grid on;

The workspace is rendered with 5 degree steps of each joint, just that you know where the data comes from.

Cheers and thanks,

Johannes

[Johannes Schürmann]

To understand the geometry of the work space and to get an idea, I personally plot slices of a certain thickness (e.g. .2) though the cloud.

[Ahmet Cecen]

Does it matter where this cuboid volume is, as in does it have to be centered? Or can it be biased on the, say, left hemisphere of motion, as long as it is the biggest cuboidal volume? The reason I ask is that will determine whether I can use certain heuristics or not.

Answer 1

[Image Analyst]

If you have a cluster/cloud of points, then you can use the Euclidean Distance transform to find the biggest object (such as a sphere, which is easiest) that can fit inside your cluster. Use bwdist() in the Image Processing Toolbox. It could be a little tricky for weird shapes, such as really spiky things, but for smooth, relatively convex objects you can find the max of the distance transform that is located within the convex hull of your points (there's a bwconvhull() function to help you). No, I don't have any demos - sorry.

[Ahmet Cecen]

The cloud he shared is like an apple with a bite on it. Even then using bwdist, you can find objects with long features to put inside, but not necessarily objects that have the largest volume. Consider for example that of the numbers that sum up to the same number (say 14), x+y+z, the cuboid with longest feature is 12,1,1 while the cuboid with the biggest volume is 5,5,4.

Maybe this is more a math stack exchange question than a MATLAB question...