[postgis-devel] Visvalingam’s simplification and twkb with zoom-levels

[Nicklas Avén]

Hallo strk

On Fri, 2015-01-09 at 20:17 +0100, Sandro Santilli wrote:
> Happy new year Nicklas,
> 
> On Fri, Jan 09, 2015 at 12:14:01AM +0100, Nicklas Avén wrote:
> 
> > I have written a function for simplification with Visvalingam’s algorithm
> 
> Are you aware of this ticket ?
> http://trac.osgeo.org/postgis/ticket/2227

No, I wan't aware of it. But anyway if I go on with the twkb-zoom level
project I want the simplification close. I have written the function so
I can avoid an extra memcopying of all the coodinates before copying
them into twkb (or whatever format with zoom levels it is used for. 

> 
> > The function stores the effective area of each vertex-point in the
> > m-value. There is also a second parameter in the function so it is
> > possible to set a limit what minimum effective area that the resulting
> > geometry vertex points shall have.
> 
> [...]
> 
> > The speed seems to be about the same as ST_Simplify.
> 
> I'd expect it to be faster than D&P in the worst case
> (tolerance so low that nothing gets removed).
The speed is not affected of how many points that is removed. It always
calculate the effective area for all points. But I see your point. If
the eliminiation stops when the threashold is reached it will be faster.
But then you don't get the information that tells in what order to
eliminate the rest of the pionts.


> 
> > So, do we want ST_SetEffectiveArea(geom) and ST_SetEffectiveArea(geom,
> > trhld)?
> 
> From my earlier reading of the paper I understood that the
> "effective area" of a vertex may change if any adjacent vertex
> is removed, as the area of the new triangle is computed and used
> if larger than the old triangle. Is this done by your function taking
> a threashold already ?

That is not connected with the threashold. 

What happens is:

1) all areas is calculated. for point 4 the area of triangle with point
3, 4 and 5 is calculated.
2) the trinangle with smallest area is eliminated
3) the adjacent points triangels is recalculated. If the new areas is
smaller than the area corresponing to the eliminated point, that area is
used instead. To make sure the points is removed in the right order.
4) this iterates until all points is eliminated.

Then we have the effective area for each point. That is the area that
point gives when all with smaller areas is eliminated.

So what we basically do is to order all vertex points so we can
eliminate them in the right order.

When we have the information about the area the right points can be
eliminated at a very small cost at rendering time.


> My idea was to have one function to just set the index and another
> to filter based on a condition (for example, M value being above
> a value). The filtering function sounds pretty generic, and maybe
> we already have something for that.

Yes, filtering is just comparing the area against the threashold. In my
function that is done when the vertex points is copied from the original
geometry to the resulting geoemtry.

In the case of twkb with zoom levels all vertex points is put in lists
for the zoom-level they belong to depending of multiple area thresholds.

So by calculating those areas we can simplify to all levels without any
more costs than the initial.

> 
> Another thought is that existing clients might not know how to receive
> the M ordinate, in which case it's useful to be able to specify which
> ordinate should hold the "resolution info".

> 
> What such "resolution info" is composed of (effective area or some
> derivative info such as "zoom level"?) I'm still not sure about.
> 

I add a very dirty patch if someone feels like trying. 
The sql-signature as it stands now is just something like:


CREATE OR REPLACE FUNCTION st_seteffectivearea(geometry, double
precision)
  RETURNS geometry AS
'$libdir/postgis-2.2', 'LWGEOM_SetEffectiveArea'
  LANGUAGE c IMMUTABLE STRICT
  COST 1;



that is not included in the patch.

If the second parameter is set to 0 all points will get through and have
with their effective area calculated.

But I realize when you point is out that the function should shortccut
at once the threashold is reached.


/Nicklas


> --strk;
> 
>   ()   Free GIS & Flash consultant/developer
>   /\   http://strk.keybit.net/services.html
> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: setEffectiveArea.patch
Type: text/x-patch
Size: 9141 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20150109/da19a7e6/attachment.bin>