Topology preserve simplify: unexpected behavior on similar polygons

[uclaros]

When simplifying a polygon, the first/last vertex is not removed even when within the threshold. The following WKT polygons are essentially the same polygon, each time with a different first/last vertex:

Polygon((0 42, 0 100, 42 100, 100 42, 42 42, 0 42))
Polygon((0 100, 42 100, 100 42, 42 42, 0 42, 0 100))
Polygon((42 100, 100 42, 42 42, 0 42, 0 100, 42 100))
Polygon((100 42, 42 42, 0 42, 0 100, 42 100, 100 42))
Polygon((42 42, 0 42, 0 100, 42 100, 100 42, 42 42))

simplifying those polygons with a threshold of 1 should give the same result, ie remove the vertex at (42,42) but in the last case this does not happen and the input polygon is returned untouched.

If we remove the vertex at (0,100) and rerun the test:

Polygon((0 42, 42 100, 100 42, 42 42, 0 42))
Polygon((42 100, 100 42, 42 42, 0 42, 42 100))
Polygon((100 42, 42 42, 0 42, 42 100, 100 42))
Polygon((42 42, 0 42, 42 100, 100 42, 42 42))

then only the second polygon gives the correct result, all the others are returned untouched

Tested in QGIS with geos 3.9.0dev :

QgsGeometry.fromWkt('Polygon((0 42, 42 100, 100 42, 42 42, 0 42))').simplify(1)
QgsGeometry.fromWkt('Polygon((42 100, 100 42, 42 42, 0 42, 42 100))').simplify(1)
QgsGeometry.fromWkt('Polygon((100 42, 42 42, 0 42, 42 100, 100 42))').simplify(1)
QgsGeometry.fromWkt('Polygon((42 42, 0 42, 42 100, 100 42, 42 42))').simplify(1)

QgsGeometry.fromWkt('Polygon((0 42, 0 100, 42 100, 100 42, 42 42, 0 42))').simplify(1)
QgsGeometry.fromWkt('Polygon((0 100, 42 100, 100 42, 42 42, 0 42, 0 100))').simplify(1)
QgsGeometry.fromWkt('Polygon((42 100, 100 42, 42 42, 0 42, 0 100, 42 100))').simplify(1)
QgsGeometry.fromWkt('Polygon((100 42, 42 42, 0 42, 0 100, 42 100, 100 42))').simplify(1)
QgsGeometry.fromWkt('Polygon((42 42, 0 42, 0 100, 42 100, 100 42, 42 42))').simplify(1)

[strk]

I guess one option here would be to pick the leftmost-upmost and the rightmost-bottommost points of a ring, split the ring in two parts, merge the lines which remain split by the origina vertex, then perform the simplification on the two parts and join them back togheter.

What do you think Martin ?

[mdavis]

Replying to strk:

I guess one option here would be to pick the leftmost-upmost and the rightmost-bottommost points of a ring, split the ring in two parts, merge the lines which remain split by the origina vertex, then perform the simplification on the two parts and join them back togheter.

What do you think Martin ?

I don't see how that works. The problem with the current simplification algorithm is that it is essentially working on a line, not a ring - which is why it doesn't remove the endpoint even if it should be. Doesn't splitting the ring just introduce one more endpoint?

Not sure of what a solution could be ATM. The simplification algorithm being used is Douglas-Peucker, and I don't know if that can be generalized to work on true rings.

[mdavis]

Not a net new problem; here's some ​ideas about it. Not sure I totally agree with the suggestions, but they do have some ideas that are a starting point.

How about this: find the vertex for which the triangle formed with the adjacent vertices has maximum height, and rotate the ring to use it as the starting point? (Height being the perpendicular distance to the line between the adjacent points. In the case of a regular polygon this is arbitrary, so no need to rotate).

[uclaros]

A simplistic solution would be to take the current resulting polygon, use its 0, 1, n-1 and n (same as 0) vertices to decide if 0 and n vertices should also be removed. If so, remove them and append vertex 1 to the end to close the ring.

[mdavis]

Replying to uclaros:

take the current resulting polygon, use its 0, 1, n-1 and n (same as 0) vertices to decide if 0 and n vertices should also be removed.

Good idea.

[komzpa]

Generally speaking Douglas-Peucker should be replaced with Visvalingam-Whyatt when doing anything about area. It is easily adaptable for rings. The epsilon will be an area then, it is usually ok to square the DP epsilon and run VW instead on areas.

[dbaston]

Resolved by a8514a36f7a6ca3e1eccc2a9b53d3d711342d2bf/git

[uclaros]

This is not properly resolved, the following two cases still fail to remove the 42,42 vertex:

QgsGeometry.fromWkt('Polygon ((0 42, 42 100, 100 42, 42 42, 0 42))').simplify(1)
QgsGeometry.fromWkt('Polygon ((100 42, 42 42, 0 42, 42 100, 100 42))').simplify(1)

using qgis with geos 3.12.0