Fitting cube of maximum volume into a body/volume of arbitrary shape
7 views (last 30 days)
Show older comments
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
4 Comments
Ahmet Cecen
on 23 Apr 2015
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.
Answers (1)
Image Analyst
on 23 Apr 2015
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.
1 Comment
Ahmet Cecen
on 23 Apr 2015
Edited: Ahmet Cecen
on 23 Apr 2015
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...
See Also
Categories
Find more on Point Cloud Processing in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!