Opened 11 years ago

Closed 8 years ago

#2093 closed enhancement (fixed)

Add extra policy argument to control ST_Simplify behavior

Reported by: robe Owned by: pramsey
Priority: medium Milestone: PostGIS 2.2.0
Component: postgis Version: master
Keywords: Cc: srstclair, aaime, jatorre

Description

See #1987 for further discussion

Attachments (1)

2093.patch (2.8 KB ) - added by pramsey 9 years ago.
Minimal patch to begin preserving collapsed geometries

Download all attachments as: .zip

Change History (40)

comment:1 by robe, 11 years ago

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.

comment:2 by strk, 11 years ago

The actual discussion for this is in #1698

comment:3 by strk, 11 years ago

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.

comment:4 by strk, 11 years ago

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.

comment:5 by strk, 11 years ago

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

comment:6 by robe, 11 years ago

Owner: changed from pramsey to strk

comment:7 by robe, 11 years ago

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

comment:8 by strk, 11 years ago

Milestone: PostGIS 2.1.0PostGIS 2.2.0

comment:9 by srstclair, 10 years ago

Cc: srstclair added

comment:10 by srstclair, 10 years ago

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.

comment:11 by aaime, 10 years ago

Cc: aaime added

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…)

comment:12 by strk, 10 years ago

No progress here. Have a patch ?

comment:13 by aaime, 10 years ago

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

comment:14 by strk, 10 years ago

By "push" she means setting Milestone forward :)

comment:15 by strk, 9 years ago

Cc: jatorre added

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.

comment:16 by aaime, 9 years ago

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?

comment:17 by strk, 9 years ago

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

comment:18 by strk, 9 years ago

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

comment:19 by strk, 9 years ago

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 ?

comment:20 by srstclair, 9 years ago

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)

comment:21 by strk, 9 years ago

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 ?

comment:22 by strk, 9 years ago

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.

comment:23 by srstclair, 9 years ago

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?

comment:24 by strk, 9 years ago

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.

comment:25 by strk, 9 years ago

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.

comment:26 by strk, 9 years ago

Milestone: PostGIS 2.2.0PostGIS Future

comment:27 by pramsey, 9 years ago

Milestone: PostGIS FuturePostGIS 2.2.0
Owner: changed from strk to pramsey

by pramsey, 9 years ago

Attachment: 2093.patch added

Minimal patch to begin preserving collapsed geometries

comment:28 by pramsey, 9 years ago

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

comment:29 by robe, 9 years ago

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.

comment:30 by pramsey, 9 years ago

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

comment:31 by robe, 9 years ago

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

comment:32 by pramsey, 9 years ago

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?

comment:33 by nicklas, 9 years ago

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

comment:34 by pramsey, 9 years ago

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

comment:35 by pramsey, 9 years ago

Whatever the minpoints parameter preserves in the ptarray_simplify function :)

comment:36 by strk, 9 years ago

No concerns here.

comment:37 by pramsey, 9 years ago

Resolution: fixed
Status: newclosed

comment:38 by strk, 8 years ago

Resolution: fixed
Status: closedreopened

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

comment:39 by pramsey, 8 years ago

Resolution: fixed
Status: reopenedclosed

doc'ed at r14459 in trunk, r14458in 2.2

Note: See TracTickets for help on using tickets.