From: Michael Bedward <michael.bedward@gm...> - 2008-12-18 00:27:06
I've been working on some code that stores a list of rectangles
defining areas of a map that need to be updated prior to servicing the
next data request. The rectangles frequently overlap. Since the map
updating process is time-consuming I looked for an algorithm to
decompose the polygon formed by the outline of the overlapping
rectangles into a set of non-overlapping rectangles.
I found some papers in the computational geometry literature but most
were concerned with finding 'optimal' solutions: e.g. minimizing side
lengths. I also looked through JTS (where I'm sure there must be a
solution that I'm too uneducated to spot - perhaps in the graph
algorithms ?) and posted a query on the JTS mailing list.
I've now hacked a partial solution to the problem: ie. one that works
for many, but not all configurations of overlapping rectangles - as
I've just discovered :-( It is a simple algorithm based on
identifying convex / concave vertices in the input rectilinear
polygon. I think (hope) that a bit more tweaking will make it robust,
but before I do this I wonder if anyone here has an alternative -
perhaps some bit of geotools code that I'm unaware of ?
My code seems to be decomposing happily now :-)
Probably unlikely, but in case it's any use to anyone or to gt I've
attached the code.
ps. I'd still be keen to hear how this should really be done !