Add extra policy argument to control ST_Simplify behavior

[robe]

See #1987 for further discussion

[robe]

Does this affect ST_SimplifyPreserveTopology as well? I honestly can't remember the last time I ever used ST_Simply. I usually use the PreserveTopology variant.

[strk]

The actual discussion for this is in #1698

[strk]

robe: I don't think it affects ST_SimplifyPreserveTopology. There the policy is clear: preserve the internal topology. So no geometry will collapse. This is only for ST_Simplify which happily allows collapses instead.

[strk]

More background on the topic here: ​http://blog.cartodb.com/post/20163722809/speeding-up-tiles-rendering

The numbers there show that running ST_SimplifyPreserveTopology (simpTP) on the data can make the whole operation (process,fetch,render) slower than rendering the whole vertices (vanilla), thus defeating the purpose of vector reduction.

[strk]

r10821 make trunk version consistent in that it returns _more_ NULL values (NULL rather than single-vertex line, and NULL on EMPTY input).

[robe]

strk again — do this or please push. If I don't see a note, I'm going to push myself next week.

[srstclair]

GeoTools now has the ability to use ST_Simplify when rendering tiles from PostGIS. The polygon nullification behavior wasn't expected and caused a bit of a debugging headache:

​http://jira.codehaus.org/browse/GEOT-4737

This behavior basically prevents ST_Simplify's use in map tiling applications. As strk mentioned above, using ST_SimplifyPreserveTopology isn't an option since it's usually much slower than just returning the original geometries. So, +1 for adding policy control argument(s) to prevent nullification of polygons.

[aaime]

Any progress on this one? More people are reporting this as a problem against GeoServer (and yes, we do have a way to turn off simplification, but it's useful in various complex maps…)

[strk]

No progress here. Have a patch ?

[aaime]

Hehe, sorry no, hell will freeze before I program in C again My interested was picked by this comment from Regina: "strk again — do this or please push. If I don't see a note, I'm going to push myself next week."

[strk]

By "push" she means setting Milestone forward

[strk]

So, back to this. What would useful behaviors be in case of lines and polygon collapses ? Of course the request here is to keep something rather than returning NULL. EMPTY is likely not useful at all as you probably want the georeference.

The smallest valid type to represent the georeference would be a point, but returning a point for a line or areal input might result in unexpected rendering, as the rendering engine may behave differently based on input type (for example placing markers for points). So we're left with the only options being returning a structurally or topologically invalid geometry.

A topological invalid geometry would be a line with no interior (2 cohincident vertices) or a polygon with no interior (4 cohincident vertices). A structurally invalid geometry would be a line with a single vertex and a polygon with a single vertex.

I'm making the difference because some functions may choke when fed structurally invalid geometries, in PostGIS, so I'm wondering if the same may also happen in clients. For sure the structurally invalid case would be the smallest, which may matter in case you have million of collapsed polygons to transfer to the client.

On a side note, would we want to control whether or not to keep the boundary of collapsed holes too ? Imagine a big swiss cheese geometry with all holes collapsed. Do we want to keep them all, or just keep the shell ?

To recap, we need the following policies:

• lines: null, structurally invalid, topological invalid, collapse to point
• polygon shells: null, structurally invalid, topological invalid, collapse to line or point
• polygon holes (for non-collapsed shell): remove, structurally invalid, topologically invalid

I've to go check for the current behavior, as I lost track of which one it is.

Also, the same set of policies would be useful to be also accepted by ST_SnapToGrid, so it's worth having them well defined once for all.

[aaime]

Wondering, why isn't a "bbox" simplification being considered?

If the geometry is so small that the bbox is smaller than the simplification distance, why not replace a line with a valid diagonal line across the bbox, a polygon with a triangle fitting the bbox, and a point or multipoint, with a single point centered in the bbox?

[strk]

Just a note: the structurally invalid (single-vertex) polygon is known to not be rendered by mapnik, see ​https://github.com/mapnik/mapnik/issues/1140 — it might take additional policy parameters to distinguish between a structurally valid polygon shell composed by 4 cohincident vertices and one composed by 4 vertices among which at least 2 are distinct.

About the "bbox", I'd still keep this as a pure DP with constraints on what it can do on collapse. Using the bbox is something you could do with a policy of "return null" and a COALESCE returning whatever derivate from a bbox (maybe we need some functions to derive nice figures from boxes, but that'd be for another ticket).

[strk]

So, current policy is:

• lines: never collapse (this was not included in the previous attempt at giving policies, but it is to always keep at least 2 points, the first and the furthest)
• polygon shells: null
• polygon holes: remove

So the proposed set of policies increases by adding a "do not allow collapses" for lines. I guess the equivalent for polygons (do not allow collapses) might also be useful, for both shells and holes. Ideally it would be composed by the first/last point + the farther from them + the farther from the segment composed by the previous two (for DP).

Also, I was thinking that "topological invalid" is really never useful to be intentional, that is since you have to keep at least 2 points for lines and 4 points for rings, they may as well be not topologically invalid (and a minimum number of points in output is likely to give you a valid return).

So the possible policies become:

• collapsed line: null, single vertex line, 2 vertices line [1], a point
• collapsed shell: null [1], single vertex ring, 4 vertices ring, a line or point
• collapsed hole: removed [1], single vertex ring, 4 vertices ring

[1] current behavior

[strk]

I'd note that for the mapnik case a 3-vertices ring would also be enough to render (and would be ¾ the size of the 4-vertices ring…). So maybe we need to be able to specify exactly the minimum number of vertices for tipology… Let's see if it could be expressed with an integer for each type:

minimum number of points:

• 0: null for collapsed lines or shells, removed for holes
• 1: single vertex line for lines, single vertex ring for rings
• 2: structurally valid for line, structurally invalid for rings
• 3: structurally valid for line, structurally invalid for rings, but good enough for mapnik
• 4: structurally valid for line, structurally valid ring

The conversion from line to point and from ring to line or point we could omit from the function completely. ST_MakeValid can do that, and it would be expensive to ensure topological validity anyway, even if we have multiple points.

So with this approach you'd basically only have to specify an integer for each category. Does it sound flexible enough so far ?

[srstclair]

Some quick tests indicate that the JTS Java library will not accept structurally invalid geometries (single vertex lines, 1-3 vertex polygons, unclosed polygons) but will accept topologically invalid geometries (two coindicent vertex lines, four coincident vertex polygons). So, at least considering GeoTools and all other applications using JTS, preserving structural integrity is important. Perhaps we just need a ST_SimplifyPreserveStructure which reduces lines to a minimum of two coincident verticies and polygons to a minimum of four coincident verticies with all holes removed?

The suggestion of specifying the minimum number of (coincident) points for each type works too; it's definitely the most flexible, if a little cumbersome. To clarify, though, the minimum number of verticies would be specified for each type in the same call? Something like this?

st_simplify(geometry geomA, float tolerance, int linestring_min_verticies, int polygon_shell_min_verticies, int polygon_hole_min_verticies)

[strk]

Yes, that's the idea. Either one parameter per type or an array of integers (but would be harder to remember which array element is for which type). Other ideas ?

[strk]

I've to say that ST_SimplifyPreserveStructure is not bad as an idea, btw. I like it.

It would basically behave the same as ST_Simplify(geom, 2, 4, 0) in the other (more complex) version.

PS: those vertices would not need to be coincident, just within that minumum number.

[srstclair]

Either (or both) of these proposals (st_simplify with min vertices arguments and st_simplifypreservestructure) seem to be good solutions to me. Maybe st_simplifypreservestructure could just call st_simplify(geom, tolerance, 2, 4, 0) internally if that's not too confusing from a user perspective?

[strk]

I'm thinking that ST_SimplifyPreserveStructure would not allow to express: st_simplify(geom, tolerance, 0, 0, 0). I would avoid a new function name if the old one is still needed.

[strk]

I had another thought. Imagine a big shell with many holes. Some holes would be very tiny, and some may be very long, although "flat". Would you ever want to keep the long ones and drop the tiny ones ? Note: the "long" ones have a length which is above the "mindistance" tolerance you passed to the function.

[pramsey]

Minimal patch to begin preserving collapsed geometries

[pramsey]

So,

• is changing the behaviour to preserve collapsed features not on at all?
• if it is on, then how about some simple changes to ensure that any polygon preserved will be 4+ vertices and any line 2+ vertices (see patch above)
• if it isn't on, then about about a simple boolean flag to turn on preserve-or-not behavior

As strk has demonstrated above, the current behavior isn't exactly consistent… a collapsed line will come out as a single point, which is an invalid construction; a collapsed polygon will just go away. We should either have all collapsed things go away, or have them all survive as valid constructions (but not valid geometries, there's only so much we can do).

[robe]

I forgot what this is about, and how much of it is taken care of by the new ​http://postgis.net/docs/manual-dev/ST_SimplifyVW.html

We have too many ways to simplify for me to keep track of.

[pramsey]

No, it's just about ST_Simplify, which is the Douglas-Peuker algorithm

[robe]

Fine by me. I really don't care about this.

[pramsey]

OK then, in the spirit of improvement then, I've added an extra parameter to control collapses. I've also changed the LINESTRING collapse behavior to return NULL on collapse instead of an illegal one-point line. I've also changed both LINESTRING and POLYGON to return NULL when fed an EMPTY input.

In the presence of the "preserve collapsed" parameter, the function will now return at a minimum 4 point polygons and 2 point lines.

Concerns?

[nicklas]

What 4 points is preserved? The most significant? or evenly distributed along npoints?

[pramsey]

Added extra argument at r13574, as well as default policy changes as described above.

[pramsey]

Whatever the minpoints parameter preserves in the ptarray_simplify function

[strk]

No concerns here.

[strk]

Paul: this change lacks an entry in NEWS and an update to the manual. It makes users confused: ​https://github.com/qgis/QGIS/pull/2410#issuecomment-160503564

[pramsey]

doc'ed at r14459 in trunk, r14458in 2.2