Unexpected polygon simplification result from DouglasPeuckerSimplifier

[grimsa]

I encountered something I did not expect while using DouglasPeuckerSimplifier (disclaimer: I only have basic experience with JTS library or GIS in general).

Input polygon: POLYGON ((15.115084617721836 8.70727443584788, 15.115091626386706 8.707267302923066, 15.421534362529906 9.00837173744791, 15.671678753822775 8.753792425821182, 15.525576299977171 8.61022120849388, 16.236962643225866 7.8862233422732535, 16.383077267381125 8.029781213985052, 17.123996103335905 7.275726300925636, 16.516458866503537 7.281064561167845, 16.511120297046187 6.673493046478718, 14.808634660893606 8.40616285818682, 15.115084617721836 8.70727443584788))

Input polygon looks like this:

My intention is to remove the two almost overlapping points in the middle of the line (those zoomed in).

If I run DouglasPeuckerSimplifier.simplify(inputPolygon, distanceTolerance) with distanceTolerance of 0.001, 0.01, 0.1 it removes one of those two points, but not both.

The following results are with distance tolerance increased to 0.4 (blue) or 0.5 (red):

In both cases the mid-point which is almost on the line remains, while other much further points are simplified away.

Is this a limitation of the DouglasPeuckerSimplifier algorithm, or a bug? Or maybe I should be using some different tool for the job?

JTS version used: 1.18.0, with jts.overlay=ng property specified.

[dr-jts]

This is because one of the points that would otherwise be removed by simplification is the endpoint of the shell ring. Currently the DouglasPeuckerSimplifiier does not change endpoints. It would be nice to fix this, but that's a bit of a research project.

In this particular case you could run normalize(), which will rotate the ring enough that that point can be removed. A more general solution would require "rot"-ing the points in the ring by half-the ring size.

[grimsa]

In case anyone needs a workaround, below you can find a code snippet that rotates the exterior ring by half the ring size and simplifies again (note: interior rings are not modified).

Example code:

public class SmartPolygonal {
    private final Geometry polygonalGeometry;

    public SmartPolygonal(Geometry polygonal) {
        Assert.isTrue(polygonal instanceof Polygonal, "Provided geometry must be polygonal");
        this.polygonalGeometry = polygonal;
    }

    /**
     * Simplifies this polygonal geometry using {@link DouglasPeuckerSimplifier} using provided tolerance
     */
    public SmartPolygonal simplified(double distanceToTolerate) {
        Geometry simplified = DouglasPeuckerSimplifier.simplify(polygonalGeometry, distanceToTolerate);
        Geometry withEndpointsSimplified = DouglasPeuckerSimplifier.simplify(scrollExteriorRings(simplified), distanceToTolerate);
        return new SmartPolygonal(withEndpointsSimplified);
    }

    /**
     * Workaround for {@link DouglasPeuckerSimplifier} not removing endpoints even if they could be removed
     *
     * @see <a href="https://github.com/locationtech/jts/issues/679">JTS issue</a>
     */
    private static Geometry scrollExteriorRings(Geometry geometry) {
        Assert.isTrue(geometry instanceof Polygonal, "Provided geometry must be polygonal");
        if (geometry instanceof Polygon) {
            CoordinateSequence exteriorRingCoordinates = ((Polygon) geometry).getExteriorRing().getCoordinateSequence();
            CoordinateSequences.scroll(exteriorRingCoordinates, exteriorRingCoordinates.size() / 2);
        } else if (geometry instanceof MultiPolygon) {
            IntStream.range(0, geometry.getNumGeometries())
                    .mapToObj(geometry::getGeometryN)
                    .map(Polygon.class::cast)
                    .forEach(SmartPolygonal::scrollExteriorRings);
        }
        return geometry;
    }

    // .... other unrelated methods
}

Edit: Initially, I tried rotating by one and it seemed to work. However, later I encountered a polygon that failed to get simplified after being rotated by one. Rotating by half the ring size produced correct results. I updated the code snippet above.

The polygon in question: POLYGON ((1.2586829355310745 9.38029785473937, 1.508644282897763 11.371610040404745, 4.210635341803999 11.032440054800482, 3.085712920302312 2.0707675799929253, 1.28618687509565 2.29665479039672, 1.4097390276967172 3.2809305981043537, 2.3176080234983845 3.1669694829041446, 2.568946978993983 5.16925635779693, 1.661077983194669 5.283217472996844, 1.7836325019463066 6.259545650451515, 1.9104241620977316 7.26962893160707, 2.8182931578987356 7.155667816506943, 3.195426139693792 10.1600903423981, 2.276749179701474 10.275408137494729, 2.026406612502394 8.281058970693575, 1.1347495630934672 8.392985065899177, 1.2586829355310745 9.38029785473937))

[mwtoews]

Noting two related shapely issues to this upstream ticket:

• https://github.com/shapely/shapely/issues/990
• https://github.com/shapely/shapely/issues/1046

And agree with @dr-jts that a fix on LinearRings would be to rotate the ring somehow, as algorithms on LinearRings should not depend on the position of the start/end coordinate.

[dr-jts]

Fixed by #1013