Computing simplified coverage polygons

Summary

A somewhat recurring problem I encounter in things I work on is the need to compute simplified geographic polygons, or more specifically, simplified hulls of geographic polygons. Here’s an overview on the currently used approach, maybe someone has pointers to better algorithms for this. Coverage polygons Geographic polygons are used in a few different places: The Transport API Repository and consumers of it like KPublicTransport use them for describing areas covered by a public transport routing service, to automatically pick a suitable one at a given location. The Emergency and Weather Aggregation Service uses them to describe areas affected by an emergency. Alerts that don’t carry explicit geometry but refer to an external dataset using a geographic code are particularly affected here, as those datasets (e.g. derived from OSM boundaries) are used for many different purpose and thus are often extremely detailed. Meter-resolution geometry isn’t needed for any of those use-cases, hundreds of meters or even a kilometers are more than sufficient. And using a higher resolution does come at a cost, larger geometry needs to be stored and transferred, and rendering or doing intersection tests becomes significantly more expensive to compute. Simplified coverage Applying generic geometry simplification algorithms here isn’t ideal, as we would want a result that is still covering the original geometry, ie. a simplified hull. In the above use-cases covering more area is merely inefficient or maybe mildly annoying, while covering a smaller area can be catastrophic (e.g. someone potentially affected by an emergency not getting alerted). A bounding box is the extreme case fulfilling that requirement and minimizing the resulting geometry, but we are obviously looking for a more reasonable trade-off between additionally covered area and geometry complexity. Also, not all additionally covered area is equal here, covering extra area at land potentially impacts more people than coveri...