[postgis-users] line simplication

[Kevin Webb]

Dear PostGIS folks,

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.

I would like to implement at a way to store multiple resolutions of data
inside a geometry column such that client applications can requests a given
level of granularity without having to keep separate copies of the same data
all of the needed resolutions (or at least not make the client worry about
the different copies). If done properly this would significantly reduce the
load on the DB server and the client in order process large datasets (e.g.
viewing a map at full extent).

My experimentation with PostGIS/Mapserver has led me to believe the biggest
slowdowns steam from throughput issues when dataset size starts increasing.
Some of this gets solved with intelligent map design (making sure that
unnecessary levels of detail get striped out as the scale increases) but
there’s a point where that no longer helps. For example if I’d like to
create a map that can be viewed both at a city level and at a national scale
I can’t expect my road layer (even when striped down to just Interstates and
national highways) to work at both scales effectively. There’s just too much
information in there at the national level.

So I want to be able to strip some of it out when it’s not needed.

I think there are a two different ways this could be done:

1)	Apply some sort of line simplification algorithm to the data at load time
(e.g. inside shp2pgsql) that adds a secondary index inside the geometry
column which is then used by PostGIS to grab the relevant points prior to
sending the data back to the client.  For example you could run something
like Douglas-Plucker, or another recursive simplification method on the data
and specify which of the n-levels of hierarchy is associated with each of
the points. The client then request level they need and the DB masks out all
the points at a lower level of detail. The masking process is, of course,
non-trivial and could be implemented in a variety of ways. But I think the
benefits coudl be tremendous. The problem is that the internal structure of
the geometry object would change to inherently understand levels of detail.

2)	Have PostGIS transparently create (and synchronize) multiple copies of
each geometry object at various resolutions.  For example, you could specify
in the AddGeometryColumn call how many different levels of resolutions you
want to store and then PostGIS would internally manage multiple copies of
the data applying simplification algorithms on the fly. Then, at request
time the DB would simply choose the copy of the data that best meets the
client’s needs and return the geometry object just as it would now. This
method has the advantage of not requiring internal changes to the geometry
object format, but would also require more disk space as data would be
replicated for each level of detail.

I’m at a point where I would like to try and start implementing one of these
methods but I’d like to hear ideas from others, as I’m sure much thought as
already been put into this issue. Is it worth it? I am I headed down the
right path?

Any thoughts would be greatly appreciated!

Thanks,
Kevin Webb



--
e: kpw[at]jump9.com
p: (919)260-8375

w: kpw.jump9.com