Home Products Download Order Contacts


Subject: Simplifying a set of boxes

I have a set of disjoint (in the sense that their interiors do not
intersect), axis aligned boxes. Some of the boxes abut each other
though, sometimes even sharing faces:

(2D example: You probably need to view this in monospaced font:

| | |
| | |
| | |

| |
| | | |
| +----+-+
| | |

What I would like is an algorithm that can simplify these boxes - i.e.
it's output should be a smaller set of disjoint boxes, and the union of
the output boxes should be identical to the union of the input boxes.
Thus in the case of example A, the output should be a single box, and
in the case of B, it will need to be at least 2 boxes (preferably
exactly two, but the algorithm need not be optimal)

Can anybody provide any pointers to any work like this? I'm not quite
sure even what terms to search for.

(Some background - I ran into this problem when working with Adaptive
Mesh Refinement datasets. In particular, one of the processing steps
yields outputs with anywhere between 10K and 100K 3D boxes like this.
Visual inspection reveals that there are a LOT of boxes that could be
simplified, and even a poor algorithm (like the ones I've come up with
so far) can reduce the number of boxes by a third, but still leave a
lot of these box clusters behind.)



View All Messages in comp.graphics.algorithms


Re: Simplifying a set of boxes

Copyright 2006 WatermarkFactory.com. All Rights Reserved.