Home Products Download Order Contacts


Subject: Re: Simplifying a set of boxes

"Matteo" wrote in message

> 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


View All Messages in comp.graphics.algorithms

Simplifying a set of boxes =>


Copyright 2006 WatermarkFactory.com. All Rights Reserved.