Computing Simplified Coverage Polygons

I have a few ideas:

1. The only problem with Douglas-Peucker is that it can remove "convexities", which makes the result no longer a convex hull. A simple modification to D-P to try would be to have it only remove "concavities", i.e., only simplify to a line segment when all intermediate points fall on the "inside". This is simple and guarantees the result will be a convex hull -- though I'm not sure how much simplification it will achieve on mostly-convex polygons.

I can think of ways to simplify convex areas, but these are trickier and may not always work or work satisfactorily. Basically, if we picture the path going left-to-right with the polygon inside below, you somehow decide on a gradient and then "drop" a line with that gradient from above ("the outside") until it hits any of the points being simplified, then push the two endpoints up to meet this line.

But I think there's a better way that's completely different:

2. Make a 2D array of bits representing a coarse grid, and "render" the original geometry into it: if any part of the geometry is inside a grid cell, it is set to 1, otherwise 0. You could get a possibly quite good rectilinear solution just by tracing the outside of each connected component of 1-bits in this grid, greedily compressing runs of steps in the same direction (N/S/E/W) into a single longer line segment. But I think you could do even better:

3. The above edge-tracing approach doesn't minimise direction changes as strongly as it could, leading to "rough" edges and large encodings. We can address this by solving a shortest path problem in a closely related graph, where instead of a single vertex for each grid cell, we have 4 vertices: one for each direction we could be travelling in when we enter that cell. Each vertex has directed edges to its 4 neighbouring vertices, with the cost to its preferred (that is, same-direction) neighbour being, say, 10000, and the cost to each of its other 3 neighbours (each of which require a change of direction) being 10001. For each connected component of 1s, construct the graph by creating these 4 vertices for every grid cell outside the component; then "sever" the graph by picking, say, the cell p to the left of the leftmost 1-cell and the cell q below it, and deleting every edge from any vertex to the left of p (including p itself) to any vertex to the left of q (including q itself). Now look for a shortest path from p to q: Because we "severed" the graph, this can't "short-circuit" anticlockwise from p to q, but must go "the long way" clockwise around the component; and because each step costs 10000 and each direction change costs an additional 1, this will be a path having total length no greater than that produced by the simple algorithm 2, but that additionally minimises direction changes :)

GRASS v.generalize() has a lot of different methods: https://grass.osgeo.org/grass85/manuals/v.generalize.html. I can't personally speak to the differences but probably worth looking into.

The QGIS Simplify tool also has a Visvalingam method: https://docs.qgis.org/3.40/en/docs/user_manual/processing_al...

It may be interesting to combine a workflow with the QGIS Smooth tool: https://docs.qgis.org/3.40/en/docs/user_manual/processing_al...

I think you covered most of the ways this is done, though I didn't see mention of ST_SimplifyPreserveTopology.

There's clearly no universally correct answer to this, so I suppose it depends on your aim. If you want visually pleasing coverages, maybe look at how Mapbox Vector Tile (MVT) libraries do this. I believe they use a combination of Douglas–Peucker, area-based filtering (i.e. exclude polygons below a minimum mapping unit) and precision reduction to 4096 x 4096 within a tile.

P.S. There'a typo in your Poylgon.