Re: [Chicken-users] Computational geometry for chicken?

[Ivan Raikov]

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/address@hidden/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 <address@hidden> 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
> -=-