Hi Matt, I am not an expert in the field, and I am not at work, so my access to scientific journals is limited, but a quick and careless Google search reveals several papers that discuss efficient set operations on polygons using quad trees:
_Using quadtrees to represent spatial data_ Hanan Samet in _Computer Architectures for Spatially Distributed Data_. PDF available online: http://www.cs.umd.edu/~hjs/pubs/Samet85k.pdf In this paper, the author briefly mentions algorithms for obtaining polygon union and intersection with quadtrees, and refers to several other papers for details, of which papers at least one is available online: _Operations on Images Using Quad Trees_ Gregory Hunter and Kenneth Steiglitz in IEEE Transactions on Pattern Analysis and Machine Intelligence. PDF available online: http://www.cs.princeton.edu/~ken/quadtrees79.pdf There seem to be several other relevant papers, but since they are from the late 70s and early 80s, not all seem to have electronic editions available. There also seems to be a Haskell implementation of quad-tree: http://www.opensubscriber.com/message/[email protected]/11477331.html This is probably something worth checking out, the author might be interested in similar problems to what you are interested in. -Ivan Matthew Welland <[email protected]> writes: > I definitely need only a very small subset of what CGAL can do. For now at > least I need 2D polygon operations. I'm not familiar with how a quad tree is > used in polygon operations. Do you have a reference? I see lots of very > interesting stuff on quad trees (although quite a bit of it is pay to read) > and they look very useful. > > For comparison here is a description of how one implementation of polygon > operations was done: > > http://boolean.klaasholwerda.nl/bool.html#document > > Matt > -=- _______________________________________________ Chicken-users mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/chicken-users
