**comp.graphics.algorithms**

## Subject: **Simplifying a set of boxes**

Hello-

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:

A:

+-----+------------+

| | |

| | |

| | |

+-----+------------+

B:

+----------------+

| |

+---+----+-+-----+

| | | |

| +----+-+

| | |

+---+------+

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.)

Thanks,

-matt

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Replies:

Re: Simplifying a set of boxes

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.