Zürich, Thu 20 Feb 2025
Collapsing Carriageways with Magnetron
Road geometries are represented in OpenStreetMap by centerlines. A single line is used per physical road even if the road has multiple lanes. However, if the road consists of multiple physical carriageways separated by guardrails, then each carriageway is mapped by a centerline. A typical example for this is a road classified as highway=motorway.
Rendering roads with multiple parallel centerlines on maps at low zoom levels will still result in a single stroke. This happens if the size of a pixel on the screen is larger than the physical separation between centerlines. If for example two carriageways are separated by 20 m then this will correspond to 1 pixel at zoom level 12, i.e., the scale where suburbs, villages, and residential roads are typically shown. At zoom levels lower than 12, the two centerlines will essentially look like one stroke.
At low zoom levels there is no visual difference between drawing one or two lines, so if two lines are drawn the rendering engine does unnecessary work and the vector tiles include redundant information. One should therefore collapse carriageways into single lines at low zoom levels before tile generation. Google and Apple maps both optimize their maps in this direction. One can inspect this by loading their web map, turning the internet off, and zooming in. This will reveal the true number of lines of a road. Most free and open-source maps however are not collapsing carriageways due to the lack of tooling.
In this post we will give an overview of Magnetron, a new tool to collapse carriageways into single lines. The underlying idea is to make the lines magnetic such that they attract each other, move closer together, and eventually collapse into a single line. But before going into details let us briefly discuss alternative approaches.
Alternatives
A first alternative is to use raster instead of vector tiles. Pixels are simply colored at tile generation time and the tile size does not increase if multiple identical lines are drawn. However, in particular line rendering looks much worse on raster maps than on vector maps if fluid zooming is required.
A second alternative are the Natural Earth roads. This is a collection of road geometries with metadata that contain single lines even for multi-carriageways. One challenge here is the transition from the Natural Earth roads to OpenStreetMap during zoom. Since the geometries are not identical, there will be some discontinuity. Also the dataset is not generated automatically and while updates are still released, they might be multiple years apart. Nonetheless, Natural Earth roads are today probably the most popular option for low zoom roads.
Finally, Skeletron was a project that aimed at collapsing carriageways programmatically. The basic idea was to first turn lines into polygons by buffering them (buffering means to turn a line into a sausage), then to union the buffered polygons, and then to extract polygon centerlines using Voronoi diagrams. While this is an attractive concept, there are probably some difficulties in turning polygons to lines since this problem does not have a unique solution. Skeletron gave the inspiration for the name Magnetron.
Overview
Magnetron has two steps: First, lines are "magnetized" such that they move closer together. While this step reduces the separation between lines, one still has multiple lines. In a second step, overlapping lines are erased such that only a single line remains.
Magnetize
The magnetize step is inspired by the Physics of attractive particles. The points of a line are attracted to the points of other lines and move towards them. For this, we loop over all points. Consider the current point of Figure 1. We first compute the midpoint of the points of the other line. Then we move the current point halfway in the direction of the midpoint to find a new, magnetized point. This can be repeated several times and the line separation drops each time roughly by a factor of two.
Fig. 1: In the magnetize step, the current point moves halfway to the weighted midpoint of the other points to a new location called the magnetized point.
The midpoint calculation takes multiple factors such as distance, angle, and line overlap into account.
Erase
The erase step turns multiple close-by lines into a single line. For this, we start with the longest line first and follow it point by point.
Fig. 2: Following the points of the top line, we erase all points within the erase radius that belong to other lines.
Consider Figure 2 where we see that points that fall within a so-called erase radius are deleted if they belong to other lines. This process is like following lines with the erase tool in Microsoft Paint. We repeat this for all lines in order by length with longest first.
Special care has to be taken if two lines cross. By default, a gap would be created in one of the lines. To prevent this we introduce a minimum erase length which is a multiple of the erase radius. Points are only effectively deleted if the deleted section is longer than the minimum erase length.
In Depth
Now that we understand the basic steps magnetize and erase, let us have a closer look at some detail aspects.
Densification
Road geometries from OpenStreetMap are stored as a sequence of points. The distance between points is variable. While in tight curves points can be as close as a few meters, they can also be tens or even hundreds of meters apart on perfectly straight roads.
Fig. 3: The magnetize step only takes points inside the interaction radius into account. To make sure points are there we densify the lines with additional, densified points.
If the distance between points along a line is much larger than the line separation this can lead to problems. We have seen that the erase step uses a finite radius. Similarly, we take in the magnetize step only points into account that are within a given distance from the current point. This distance is called the "interaction radius", see Figure 3. On straight roads where the original points have separations longer than the interaction radius, it can happen that no points fall within the radius even though the other line crosses the interaction circle.
To counteract this, we first densify the original lines by adding points at a fixed densify interval. The interval is chosen to be small compared to the interaction radius.
The densified points can be removed again by line simplification with a small or even zero tolerance.
With well densified lines at hand we can now discuss in more detail how the weighted midpoint calculation in the magnetize step works. Each point gets a weight given by the product of the distance weight, the angle weight, and the overlap weight.
Distance
The first factor that plays a role in the midpoint calculation is the distance between the current point and the other points, see Figure 4. Similar to a force in Physics, we want to give more importance to closer points. We choose a scaling of 1/distance for the distance weight.
Fig. 4: The distance weight in the midpoint calculation is given by the inverse of distance.
Without the distance weight we have observed that S-like geometries get flattened out. For example mountain passes with many curves become straight lines. While this might be an interesting effect, we wanted to preserve the original geometries as well as possible. Lines should only collapse.
Angle
The angle weight is the second factor of the midpoint calculation. The basic idea here is that parallel lines should attract each other, but lines that just cross should not be changed.
To compute the angle weight we iterate first over all points and attach an angle to each point given by the angle of the next line segment to the horizontal. We then use the absolute value of the cosine of the angle difference between the current point and the other point as the angle weight, see Figure 5. Parallel lines have maximal angle weight, perpendicular lines have zero angle weight.
Fig. 5: The angle weight uses the angle difference between lines.
We have observed that without the angle weight, x crossings can turn into >-< crossings, i.e., they get flattened out. This still happens to some degree with the angle weight but the effect is suppressed.
Overlap
While the distance and the angle weight are factors that only take local properties into account, we also make use of the global arrangement of lines with the overlap weight. The idea here is that lines that are close together over extended distances should attract each other more than lines which are only close in some points.
To find the overlap weight of line A with line B, we first buffer each line, see Figure 6. We then compute the intersection area of A with B and normalize it by the area of A.
Fig. 6: For the overlap weight lines are buffered and the intersection area of A with B is normalized by the area of A.
The overlap weight helps like the angle weight with keeping crossings unchanged and it also preserves branching roads better.
Result
We downloaded some highway=motorway lines from OpenStreetMap and ran the Magnetron method on it, see Figure 7. The data is from an area around Washington DC and includes not only dual but also triple and quadruple carriageways. We see that lines are well collapsed and even complex junctions are simplified.
For this example we run three iterations of the magnetize step followed by the erase step.
Most roads in this example have two carriageways. In principle a size reduction of 50 percent should be possible. In practice we found that the overall PMTiles file went from 188 kB for the original geometries to 104 kB after running Magnetron. This is still a size reduction of 45 percent.
You find an online demo at https://github.com/wipfli/magnetron. In some locations you will find leftover segments which were not erased because the line separation was larger than the erase radius. One could counteract this with more magnetize iterations which would move the lines closer together. Or the erase radius could be increased. This however can lead to larger gaps at Y-junctions.
Fig. 7: Example of carriageway collapsing north of Washington DC. a) the original geometries from OpenStreetMap, b) after one magnetize iteration, c) after three magnetize iterations, d) after 3 magnetize iterations and the erase step.
Outlook
With the Magnetron method one can collapse parallel lines like dual- and multi-carriageways into single geometries. At the moment the tool operates on GeoJSON files. To make it easier to use one could integrate it in a tile generator like Planetiler. Challenging here might be that line collapsing is best done on the full geometries while Planetiler works on a tile by tile basis.
Another attractive direction could be to create a dataset similar to the Natural Earth roads. This would be a set of roads with metadata from OpenStreetMap where all lines are collapsed. If all is done automatically one could produce nightly or weekly builds and data consumers would always get fresh and up-to-date collapsed roads.