**comp.graphics.algorithms**

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

"Matteo"

news:1146676122.113649.19140@u72g2000cwu.googlegroups.com...

> 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:

Does your input set of boxes include known adjacency information?

For example, in your case A, the two smaller boxes share an edge.

Do you know that in advance? In your case B, the top box and

the lower-left box have edges on the same line. Let the top edge

of the lower-left box have endpoints P and Q, P on the left and

Q on the right. P is a box vertex shared by the top box and the

lower-left box. Does the top box know about Q?

In the absence of any known adjacency information (i.e., you

know only the individual boxes), and ignoring floating-point

round-off errors (i.e., assume exact arithmetic), you can

create a hash table of edges. Each edge is defined by two

endpoints and has two pointers to boxes sharing the edge.

At least one pointer is nonnull, but the other can be null if

only one box shares the edge. Iterate over the input boxes

and update the hash table for all the edges you visit. Iterate

over the edges if an edge is shared by two boxes, throw out

the edge and merge the boxes. The updating of the hash

table when you merge might be a tricky thing to get right.

As boxes merge, there might also be a need to add new

edges to the hash table. I have not thought carefully through

the details, so there might be other "gotchas".

There might be some relevant algorithms associated with

"minimum cycle basis" for a graph. Your input boxes are minimum

cycles, and you would like to merge as many minimal cycles

as possible into larger cycles.

If you do compute all the points of intersection of all the

edges, creating a vertex-edge graph, there might be some

tricks to apply by looking for "minimum spanning trees".

--

Dave Eberly

http://www.geometrictools.com

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Simplifying a set of boxes =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.