Sign in to follow this  
MxADD

Finding a minimal number of BBoxes in volume

Recommended Posts

Hi I have a 3D volume (regular grid, say 128x128x128) in this volume each cell has value 0 (empty) or 1 (occupied). Now I need to find a minimal (sub-optimal solution also will do :)) number of bounding boxes that encapsulates ALL non-empty cells. Is there any algorithm that can do this ? For more clearance below is some ASCII art showing what i want to accomplish in simple 2D case. grid 8x8: <code> 0 1 2 3 4 5 6 7 +-+-+-+-+-+-+-+-+ |1|1| | | | | | | 0 +-+-+-+-+-+-+-+-+ |1|1|1|1|1|1|1|1| 1 +-+-+-+-+-+-+-+-+ |1|1| | |1|1|1| | 2 +-+-+-+-+-+-+-+-+ | | | | |1| | | | 3 +-+-+-+-+-+-+-+-+ | | | | |1| | | | 4 +-+-+-+-+-+-+-+-+ | | | | |1|1|1|1| 5 +-+-+-+-+-+-+-+-+ | | | | |1|1|1|1| 6 +-+-+-+-+-+-+-+-+ | | | | | | | |1| 7 +-+-+-+-+-+-+-+-+ </code> the result should be 6 BBoxes: <code> 0 1 2 3 4 5 6 7 +-+-+ |111| 0 +111+-+-+-+-+-+-+ |111|22222222222| 1 +111+-+-+-+-+-+-+ |111| |33333| 2 +-+-+ +-+-+-+ |4| 3 +4+ |4| 4 +-+-+-+-+ |5555555| 5 +5555555+ |5555555| 6 +-+-+-+-+ |6| 7 +-+ </code> 1st box is min: (0, 0), max (2, 3) 2nd box is ... etc. Any ideas how to do this ? Thanks for any ideas.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this