Polygon Simplification with Douglas-Peucker

[wipfli]

I played around with polygon simplification in QGIS, was quite nice. I used the Douglas-Peucker method there. Can Planetiler do this as well?

[msbarry]

Yes, this is what planetiler uses now. You can configure the simplify tolerance (in tile pixels) on each feature that the profile emits.

The main gap in planetiler is you can't do Visvalingam-Wyatt simplification. I think the VW variant that uses effective area would produce better results generalizing low zoom features (oceans, glaciers, etc) from OSM data instead of needing to use natural earth.

[wipfli]

Polygon simplification on the merged geometries seems to work. Douglas Peucker with a tolerance of 100 created this image:

I guess that is a bit too high a tolerance...

[msbarry]

This is the code that does the polygon merging:

planetiler/planetiler-core/src/main/java/com/onthegomap/planetiler/FeatureMerge.java

Lines 240 to 290 in 15d0e4f

	public static List<VectorTile.Feature> mergeNearbyPolygons(List<VectorTile.Feature> features, double minArea,
	double minHoleArea, double minDist, double buffer) throws GeometryException {
	List<VectorTile.Feature> result = new ArrayList<>(features.size());
	Collection<List<VectorTile.Feature>> groupedByAttrs = groupByAttrs(features, result, GeometryType.POLYGON);
	for (List<VectorTile.Feature> groupedFeatures : groupedByAttrs) {
	List<Polygon> outPolygons = new ArrayList<>();
	VectorTile.Feature feature1 = groupedFeatures.get(0);
	List<Geometry> geometries = new ArrayList<>(groupedFeatures.size());
	for (var feature : groupedFeatures) {
	try {
	geometries.add(feature.geometry().decode());
	} catch (GeometryException e) {
	e.log("Error decoding vector tile feature for polygon merge: " + feature);
	}
	}
	Collection<List<Geometry>> groupedByProximity = groupPolygonsByProximity(geometries, minDist);
	for (List<Geometry> polygonGroup : groupedByProximity) {
	Geometry merged;
	if (polygonGroup.size() > 1) {
	if (buffer > 0) {
	// there are 2 ways to merge polygons:
	// 1) bufferUnbuffer: merged.buffer(amount).buffer(-amount)
	// 2) bufferUnionUnbuffer: polygon.buffer(amount) on each polygon then merged.union().buffer(-amount)
	// #1 is faster on average, but can become very slow and use a lot of memory when there is a large overlap
	// between buffered polygons (i.e. most of them are smaller than the buffer amount) so we use #2 to avoid
	// spinning for a very long time on very dense tiles.
	// TODO use some heuristic to choose bufferUnbuffer vs. bufferUnionUnbuffer based on the number small
	// polygons in the group?
	merged = bufferUnionUnbuffer(buffer, polygonGroup);
	} else {
	merged = buffer(buffer, GeoUtils.createGeometryCollection(polygonGroup));
	}
	if (!(merged instanceof Polygonal) || merged.getEnvelopeInternal().getArea() < minArea) {
	continue;
	}
	merged = GeoUtils.snapAndFixPolygon(merged).reverse();
	} else {
	merged = polygonGroup.get(0);
	if (!(merged instanceof Polygonal) || merged.getEnvelopeInternal().getArea() < minArea) {
	continue;
	}
	}
	extractPolygons(merged, outPolygons, minArea, minHoleArea);
	}
	if (!outPolygons.isEmpty()) {
	Geometry combined = GeoUtils.combinePolygons(outPolygons);
	result.add(feature1.copyWithNewGeometry(combined));
	}
	}
	return result;
	}

Notice on line 275 that it goes straight from buffered/unbuffered output to snapAndFix without simplifying first. You could insert a simplify step there before snapAndFix and add an extra argument to this method to control simplification factor.

What you're seeing in the result you shared is that simplifying introduces self-intersections in the polygons so they become invalid and maplibre generates these rendering artifacts. That's why you need to simplify before snapAndFix.

[wipfli]

Interesting, thanks! Is it possible that the buffering/unbuffering generates self-intersecting polygons which make Douglas Peucker behave in a strange way? I added a GeoUtils.fixPolygon step before simplification now, let's see if that changes something...

[zhibek]

@msbarry Just picking up this conversation as I've been experimenting with different line simplification/smoothing strategies.

The main gap in planetiler is you can't do Visvalingam-Wyatt simplification. I think the VW variant that uses effective area would produce better results generalizing low zoom features (oceans, glaciers, etc) from OSM data instead of needing to use natural earth.

Is this simply stating the current situation or are there conceptual reasons that having VW simplification added to planetiler would be problematic or something to be avoided? I realise the performance may be slightly poorer than DP simplification, but the improved output may be worth it.

Depending on your response to the point above, if I get a chance, I'd be interested in trying to implement VW here. Would using JTS source (https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/simplify/VWLineSimplifier.java#L27) be a reasonable starting point (planning on making similar adaptations to use MutableCoordinateSequence as you did in the DouglasPeuckerSimplifier class?

[msbarry]

Is this simply stating the current situation or are there conceptual reasons that having VW simplification added to planetiler would be problematic or something to be avoided? I realise the performance may be slightly poorer than DP simplification, but the improved output may be worth it.

This is just the current situation - it would be great to add VW simplification!

Depending on your response to the point above, if I get a chance, I'd be interested in trying to implement VW here.

Awesome! The 2 pieces to figure out are 1) how to implement it without creating a performance bottleneck and 2) how to expose an API that switches to use VW simplification instead of DP.

For (1) probably makes sense to start out with a benchmark that compares DP with the built-in JTW VW simplification to see how far off it is. If it's way off, could implement it directly in planetiler. The VW algorithm is pretty straightforward (https://www.jasondavies.com/simplify/#pseudocode) - I think the JTS implementation is mostly inefficient because it's missing the min heap so just scans through all the possibilities. We could use PriorityQueue for that or the ArrayLongMinHeap in com.onthegomap.planetiler.collection package.

For (2) I'm not quite sure the best way to switch to this approach, maybe something like features.line("layer").setPixelTolerance(1).setSimplifyAlgorithm(VISVALINGAM_WYATT); but then we'd need a way to convert the pixel tolerance between equivalent values for DP and VW. A more robust approach would switch to a builder for configuring the simplify algorithms like features.line("layer").transform(GeometryPipeline.create().simplifyVW().useEffectiveArea().minArea(...)) where multiple geometry transforms could be chained, and possibly change by zoom level but that would be a larger refactor.