[postgis-users] Re: line simplication

[Adrian Custer]

Hey all,

The book "Reactive data structures..." is one of the better books I've
read on algorithms in GIS. I second Erik Brenn's recommendation. With
the rise of the GIST, I assumed that a "reactive" data structure could
be built into PostGIS.

As far as simplification goes, it might help you all to think of two
different kinds, semantic and geometric. I would distinguish one kind of
simplification that say removes the names of the suburbs of a big city
as you zoom out to include greater extents. For instance, a map of the
east coast of the united states would only have New York City displayed
but a map of of the local area would have the five parts of New York
labelled separately. I would define a second kind of simplification, a
geometric simplification, as something like removing internal points in
a geometry. Note that you must maintain the points that define topology,
but you can drop intermediate points and straighten structures.

So for semantic simplifications, I don't think there is a way for the
machine to figure it out on the fly. This means that you would have to
pre-define a hierarchy in the data structure. For geometric
simplification, there are endless alternatives in computational
geometry. The only time I can think of that you would need additional
information is if you had two independent layers that were interrelated.
For instance, think of a bridge in a road network. If the road network
had been build along with a river network, then you would want to keep
the bridge fixed as a "topological" point rather than moving it in the
simplification algorithm. So I can see a need for points to have a
"don't simplify me out" tag that would not be automatically determined
by the simplification strategy. Note that "topological" points internal
to the layer (i.e. road intersections) can be determined on the fly. 

cheers,
adrian



On Fri, 2003-01-10 at 23:41, Erik Brenn wrote:
> Hi,
> 
> > I know this has been talked about before (last spring I think)
> > but I'd like to reopen the discussion on implementing line
> > simplification on the DB side for applications like Mapserver.
> 
> When I did my diploma thesis in 1994 I briefly studied a multiscale spatial
> index method developed by two Dutch scientists, Peter Van Oosterom and Tom
> Viljbrief. I've included some links to their work below. Their work was done
> in 1993 and 1994 and was also implemented on top of the Postgres system at
> that time, and integrated into something they called GEO++. After I just
> googled "GEO++" I see that this is now a commercial product (www.pgs.nl)
> 
> They developed something called Reactive data structures on top of a R-tree
> structure and an improved D-P algorithm that they called BLG trees. The end
> result was a much more intelligent index that offered selection of objects
> based on object importance (e.g. scale) and also on-the-fly simplication of
> line objeccts that was actually retrieved. As you know standard R-trees keep
> all geometry objects in the leaf-nodes. A reactive R-tree keeps geometry
> also in the intermediate levels, together with an importance value. This
> make the threes more difficult to balance.
> 
> I once watched a demo of their GEO++ system on top of Postgres, and it was
> very impressing at that time to see object details and selections changing
> while they soomed in and out. The computers where not all that fast in 1994,
> but the database access and rendering was extremely fast I remember.
> 
> I think it would be a great asset to PostGIS to offer something like an
> optional reactive datastructure with its GIST index, but it's probably quite
> hard to code.
> 
> If you only want to do the line simplification stuff then take a look at
> their BLG trees or use standard D-P, but my experience is tacky lines not
> looking like I want. And as other people on this list said, automatic
> generalisation like this yields many problems like crossing lines, point
> objects ending up on wrong side of lines etc.
> 
> regards,
>  Erik Brenn
> 
> refs:
> Peter van Oosterom
> Reactive Datastructures for Geographic Information Systems (Book: ISBN
> 0-19-823320-5)
> 
> Tom Viljebrief, Peter van Oosterom
> Integrating Complex Spatial Analysis Functions in a GIS. Proceedings of the
> 6th Int.Symp. on Spatial Data Handling in 1994
> 
> Vincent Schenklaars, Tom Viljbrief, Peter van Oosterom
> The Design and Implementation of a Multiscale GIS. EGIS'93. Genua, Italy.
> p712-722, updated version 1993
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
>