vertex simplification

[thomas bonfort]

tamas,
this is so very dependant on the data you have that actual figures
make little sense
* on layers where no simplification would occur: there's a penalty,
you have to compute a distance between each feature: a loop , inside
of which you do two subtractions, one addition and two
multiplications. nothing much as in that case the number of features
should be reasonably low.
* on complex layers very zoomed out (this is with the canadian roads
plotted on a 1000*500 image, drawn three times to factor out some of
the side costs): 1.4 s -> 0.7s (from the back of my head, could be
somewhat different)

cheers,
thomas

On 10/29/07, Tamas Szekeres <szekerest at gmail.com> wrote:
> Yes, indeed it might be reasonable to do some simplification at the
> pixel space at least by checking the neighbouring points along the
> subsequent points of the poligons or linestrings.
> However I've no experience how much increment in the performance can
> be gained do you have any tests?
>
>
> Best regards,
>
> Tamas
>
>
> 2007/10/29, thomas bonfort <thomas.bonfort at gmail.com>:
> > I don't have much more to add, as Steve's reply is right on track.
> > Tamas, I do think that the naive simplification should be done at the
> > renderer level, whatever preprocessing was done beforehand at the data
> > source level: it doesn't make much sense for a pixel based renderer to
> > spend large amounts of time rendering features that are below the
> > pixel level, but it does make sense for svg for example, when you may
> > not know the scale at which the output will be seen. so let the
> > renderer decide what level of detail it can provide and discard what
> > it knows will carry little if not no additional information.
> >
> > as for the douglas-peukel simplification, I agree this could/should be
> > done at the data source. I was just throwing in the idea after looking
> > at http://freemap.in/world/index.cgi , where the cartographic quality
> > actually decreases at large scales because the data being drawn is too
> > complex. So to have some kind of simplification going on that keeps
> > cartographic quality whatever the scale, you'd either have to call the
> > simplification methods with  some kind of scale dependand tuning
> > parameters, or else have it done at the pixel level which seems a bit
> > more straightforward.
> >
> > subsidiary question: should we apply vertex simplification for point
> > layers, when multiple points fall in the same image pixel?
> >
> > thomas
> >
> > On 10/28/07, Stephen Woodbridge <woodbri at swoodbridge.com> wrote:
> > > Tamas,
> > >
> > > I don't think these two things are mutually exclusive. The fact is that
> > > once you get the lines projected into pixel space there is still a need
> > > to remove redundant vertices as Thomas has already identified because it
> > > generates a significant speedup. I think Thomas should move forward on
> > > that front regardless of other steps that might get taken.
> > >
> > > Regarding adding douglas-peuker at the raster level, I think that the
> > > jury is not in on that yet. The value of doing this would be because it
> > > can speed up the rendering without a significant impact to the display
> > > quality. I think Thomas needs to perform some test in this area and
> > > report on the findings.
> > >
> > > There are advantages to doing simplification at the source level and
> > > potentially caching the source data, in that there is less data to move
> > > into mapserver and less data to manipulate and this has some savings
> > > that can be pretty big depending on  a lot of variables. But once that
> > > data or any data is in pixel space there are a whole other set of
> > > optimizations that can/need to be applied regardless of the source data
> > > that can speed up specifically the rasterizing task and this is what
> > > Thomas is looking at.
> > >
> > > So we should get champions to move both fronts forward.
> > >
> > > Best regards,
> > >    -Steve
> > >
> > > Tamas Szekeres wrote:
> > > > Thomas,
> > > >
> > > > I think this kind of feature preprocessing task should not be bound
> > > > tightly to the rendering process and should be treated differently.
> > > > The concept around MS-RFC-22 (
> > > > http://mapserver.gis.umn.edu/development/rfc/ms-rfc-22a ) is a kind of
> > > > preliminary invocation for satisfying this need.
> > > > We should also allow the user to define the desired processing
> > > > pipeline along with some caching to prevent from doing the same
> > > > operation twice in the further drawings or among the layers if
> > > > possible.
> > > > The concept out there would also allow to drag in the capabilities of
> > > > the GEOS library to make more functions available like the
> > > > Douglas-Peuker simplifier as it happens.
> > > >
> > > > In many cases however it might be desirable to make the simplification
> > > > at the data source to decrease the amount of data to be retrieved.
> > > >
> > > > Best regards,
> > > >
> > > > Tamas
> > > >
> > > >
> > > > 2007/10/27, thomas bonfort <thomas.bonfort at gmail.com>:
> > > >> hi all,
> > > >>
> > > >> I'm looking into adding some vertex simplification at the image level,
> > > >> for the time being limited to the agg renderer. I've got two questions
> > > >> I'd like to have feedback on:
> > > >>
> > > >> * it's very easy to add a local simplification, by removing vertexes
> > > >> in a linestring that are closer than some threshold to their preceding
> > > >> vertex. I'm getting nice speedups by mimicking what's currently (more
> > > >> or less implicitely) done with gd, by removing vertexes that fall in
> > > >> the same pixel than its predecessor (of course these speedups would
> > > >> only happen for complex line layers. I'm currently testing with the
> > > >> canadian road data mentionned in
> > > >> http://wiki.osgeo.org/index.php/FOSS4G2007_IntegrationShowcase). I
> > > >> know agg is all about subpixel accuracy and such, but I'd think this
> > > >> behaviour could be enabled by default ( as in this case the maximum
> > > >> error for a vertex is less than a pixel)
> > > >>
> > > >> * is anyone interested in having a global and tunable vertex
> > > >> simplification functionality. I don't think it would be too much work
> > > >> work to implement a douglas-peuker line generalisation algorithm, that
> > > >> could be turned on and tunable with a new mapfile keyword. That's
> > > >> basically doing what postgis' SIMPLIFY can already do, except this
> > > >> would be done in pixel coordinates, and therefore would not have to be
> > > >> tuned w.r.t. scale.
> > > >>
> > > >> thomas
> > > >>
> > >
> > >
> >
>