Using Outer Hulls for Smoothing Vectorized Polygons

The electrons were hardly dry on the JTS Outer and Inner Polygon Hull post when another interesting use case popped up on GIS StackExchange.  The question was how to remove aliasing artifacts (AKA "jaggies") from polygons created by vectorizing raster data, with the condition that the result should contain the original polygon.  

A polygon for Vancouver Island vectorized from a coarse raster dataset.  Aliasing artifacts are obvious.

This problem is often handled by applying a simplification or smoothing process to the "jaggy" polygon boundary.  This works, as long as the process preserves polygonal topology (e.g. such as the JTS TopologyPreservingSimplifier). But generally this output of this process does not contain the input polygon, since the simplification/smoothing can alter the boundary inwards as well as outwards.  

Simplification using TopologyPreservingSimplifier with distance = 0.1.  Artifacts are removed, but the simplified polygon does not fully contain the original.

In contrast, the JTS Polygon Outer Hull algorithm is designed to do exactly what is required: it reduces the number of vertices, while guaranteeing that the input polygon is contained in the result.  It is essentially a simplification method which also preserves polygonal topology (using an area-based approach similar to the Visvalingham-Whyatt algorithm).

Outer Hull using vertex ratio = 0.25.  Artifacts are removed, and the original polygon is contained in the hull polygon.

Here's a real-world example, taken from the GADM dataset for administrative areas of Germany.  The coastline of the state of Mecklenburg-Vorpommern appears to have been derived from a raster, and thus exhibits aliasing artifacts.  Computing the outer hull with a fairly conservative parameter eliminates most of the artifacts, and ensures polygonal topology is preserved.

A portion of the coastline of Mecklenburg-Vorpommern showing aliasing artifacts.  The Outer Hull computed with vertex ratio = 0.25 eliminates most artifacts, and preserves the coastline topology.

Future Work

A potential issue for using Outer Hull as a smoothing technique is the choice of parameter value controlling the amount of change.  The algorithm provides two options: the ratio of reduction in the number of vertices, or the fraction of change in area allowed.  Both of these are scale-independent, and reflect natural goals for controlling simplification.  But neither relate directly to the goal of removing "stairstep" artifacts along the boundary.  This might be better specified via a distance-based parameter. The parameter value could then be determined based on the known artifact size (i.e. the resolution of the underlying grid).  Since the algorithm for Outer Hull is quite flexible, this should be feasible to implement.