Finding a minimal number of BBoxes in volume
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement