[postgis-users] Re: line simplication

Erik Brenn erik at fastmail.fm
Fri Jan 10 23:41:24 PST 2003


> 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.

 Erik Brenn

Peter van Oosterom
Reactive Datastructures for Geographic Information Systems (Book: ISBN

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

More information about the postgis-users mailing list