[mapserver-users] abutters lists....

[Steve Lime]

MapServer already employs a quad tree algorithm for spatial indexing,
don't know if it
would be of use. Way back I used an r-tree implementation from the
University of Athens.
Worked great but was a bit unstable, so when Frank wrote his first
version of the quad
tree code I made the switch.

Steve

>>> "John Newton" <john_mapserver at hotmail.com> 11/19/02 09:26PM >>>
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 at swoodbridge.com>
To: "Steve Lime" <steve.lime at dnr.state.mn.us>;
<mapserver-users at lists.gis.umn.edu>; <kevin at peoplegis.com>;
<kevinflanders at 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 at 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
> >
> >
> >
>