There is buffering code in JTS (http://www.vividsolutions.com/jts/jtshome.htm)
and in the latest version (may or may not have been released yet) there is some
spatial indexing code (quadtree I think). You can crib r-tree code from the
PostgreSQL source, although I do not know how well commented or portable it is
to other applications. JTS is being ported to C++ in the GEOS project
(geos.refractions.net) but do not expect the buffer/difference/union code to be
complete until some time in the spring.

Quoting John Newton <john_mapserver@hotmail.com>:

> I have been researching buffering for a few weeks, and found a partial
> algorithm described in the following paper:
> 
> http://www.cg.tuwien.ac.at/studentwork/CESCG99/SKrivograd/
> 
> However, to optimize for large number of vertices, it would require the
> ability to build a spatial index on the fly.  (The end of the paper refers
> to it as "plane subdivision".)
> 
> By "large number of vertices", I mean more that 100-500 (your mileage may
> vary).  I am interested in buffering polygons with potentially 1k to 10k
> vertices, which would require some sort of index (quad-tree?).
> 
> Has anyone seen an OpenSource quad tree or r-tree?
> 
> -john
> 
> 
> 
> ----- Original Message -----
> From: <woodbri@swoodbridge.com>
> To: "Steve Lime" <steve.lime@dnr.state.mn.us>;
> <mapserver-users@lists.gis.umn.edu>; <kevin@peoplegis.com>;
> <kevinflanders@rcn.com>
> Sent: Tuesday, November 19, 2002 3:47 PM
> Subject: Re: [mapserver-users] abutters lists....
> 
> 
> > The buffering algorithm is tricky, but an interesting problem.
> > Growing the vectors from the centriod only works for convex polygons,
> > it will fail for concave polygons like:
> >
> >       +---------+       +---------+
> >        |          |        |          |
> >        |          +------+          |
> >        |                              |
> >        +----------------------------+
> >
> > The right way to do this, I think, is to walk around the polygon and
> > construct offsets, then interest the offsets and re-chain the
> > segments into a new polygon, you also have to eliminate loops on the
> > new polygon caused by the fact that the offset can eliminate some
> > features from the new polygon. For example with a large enough offset
> > the notch in the above would be eliminated from the topology of the
> > new offset polygon changing it from 6 vertices to 4 vertices.
> >
> > -Steve W.
> >
> > On 19 Nov 2002 at 15:14, Steve Lime wrote:
> >
> > > Ed: Hey, it was worth a shot. Everything is square here.
> > >
> > > I see two needs. One for a buffering algorithm (I've looked and
> > > haven't found much of anything.)
> > >
> > > The other is for a process to compute the distance between arbitrary
> > > shapes. The point to vector code already exists.
> > >
> > > Anyone want to help?
> > >
> > > Steve
> > >
> > > Stephen Lime
> > > Data & Applications Manager
> > >
> > > Minnesota DNR
> > > 500 Lafayette Road
> > > St. Paul, MN 55155
> > > 651-297-2937
> > >
> > > >>> kevinflanders@rcn.com 11/19/02 11:40AM >>>
> > > It's great to see so many reactions to this abutters list need....and
> > > buffering seems to be the way to go.  I totally agree with Ed that
> > > "close" is not going to be enough....especially for legal abutter's
> > > lists that are subject to questions.
> > >
> > > How would we go about addressing the code to open the door to this
> > > functionality?
> > >
> > >
> > >
> > > Kevin
> > >
> > >
> > >
> >
> 





