[mapserver-users] abutters lists....
steve.lime at dnr.state.mn.us
Wed Nov 20 15:29:16 EST 2002
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.
>>> "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:
However, to optimize for large number of vertices, it would require
ability to build a spatial index on the fly. (The end of the paper
to it as "plane subdivision".)
By "large number of vertices", I mean more that 100-500 (your mileage
vary). I am interested in buffering polygons with potentially 1k to
vertices, which would require some sort of index (quad-tree?).
Has anyone seen an OpenSource quad tree or r-tree?
----- 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
> 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
> 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
> > 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
> > buffering seems to be the way to go. I totally agree with Ed that
> > "close" is not going to be enough....especially for legal
> > lists that are subject to questions.
> > How would we go about addressing the code to open the door to this
> > functionality?
> > Kevin
More information about the mapserver-users