Zürich, Wed 30 Sep 2024

Improving Linestring Merging in Planetiler

Planetiler, a vector tile generator, provides linestring merging functionality as part of layer post-processing. Merging linestrings prior to simplification is a good idea because simplification methods such as Douglas-Peuker will keep the end points fixed so that successful simplification and therefore tile size reduction depends on contiguous long linestrings.

However, sometimes linestring merging with the default method in Planetiler fails and that results in segmented lines which in particular at low zoom levels will appear fragmented due to line dropping base on min length. The reason it fails are small loops in the input data. Here we will have a look at how such small loops can be removed which will improve linestring merging overall.

For demonstration, we chose a highway=primary in Monaco from OSM. The lines are rendered up to zoom level 6 and we look at an overzoomed version at z13. Dots indicate where lines end.

We see here that planetiler discretizes the lat/lon geometries to a grid. Each vector tile is 256 pixels wide and each pixel subdivides into 16 dots giving a resolution of 0.0625 pixels.

We take the above lines and build a graph where edges represent the lines and nodes represent where lines meet. Each node keeps track of the edges it has attached.

As a next step, we merge edges at nodes that have exactly two edges attached. This creates longer linestrings and reduces the number of nodes:

So far this is roughly what Planetiler's default line merging does, which uses the Java Topology Suite LineMerger. The issue is now that we have short loops which are artifacts of the discretization and not real road loops that we want to keep. Let us therefore go one step further than JTS and remove loops from the graph that are shorter than a certain min loop length:

To create the above graph, we removed loops that were shorter than 4 * 0.0625. This was done by iterating over the nodes of the graph, and for each edge of a node we did a breadth-first search to find all the paths that connect from the node to the end of the edge under the condition that the path was shorter than the min loop length. If more than one path was found, we removed all but the shortest path from the graph.

As a final step, we can remove lines that are shorter than a certain min length:

In the above, we removed lines that were shorter than 4 * 0.0625. Planetiler's default line merging removes short lines as well, but since it does not do any loop merging, it means that it just deletes the loops completely which breaks connectivity.

Overall this method of removing short loops from the road network seems to make contiguous linestrings longer and lead to a representation that is closer to the physical road network. As a result of the longer linestrings, subsequent simplification will work better.

Code can be found on GitHub: https://github.com/wipfli/linestring-merging-planetiler

Update 2024-11-25: With great support from Mike Barry the loop line merging discussed here was merged into Planetiler Core. See onthegomap/planetiler#1083.