# Tomas Straupis's Diary

## Wang–Müller line generalisation

Posted by Tomas Straupis on 15 June 2021 in English.

When preparing geodata for smaller scales, you need generalisation algorithms. Douglas-Peucker and Visvalingam-Whyatt algorithms are usually used for lines (polygons). Unfortunately those are mathematical/geometrical algorithms which do not take into account cartographic requirements.

Wang–Müller algorithm tries to do exactly that - generalise lines (of natural objects) according to cartographic requirements, such as saving or even exaggerating characteristic features.

Original Wang–Müller article has a quite concise description of the algorithm and as there is no open source implementation of this algorithm (to my knowledge) it is impossible to use this algorithm in wider scale and there are a number of unanswered questions on how some particular aspects should work.

A student of Vilnius University, Motiejus Jakštys, has done a perfect job - he has not only implemented the main part of Wang–Müller algorithm using open technologies, but also described the algorithm in his paper, which you can find here:

https://github.com/motiejus/wm/blob/main/mj-msc-full.pdf

Besides describing the algorithm itself (in more detail that original paper), this paper also includes recommendations on values of parameters to use on different scales, a lot of pictures as well as propositions for future work on finishing and refining the open implementation.

In coming days the work of Motiejus will be forked into Lithuanian Openmap repository where work on this algorithm will be continued and we hope to have a final implementation some time this year.

## Discussion

Comment from mboeringa on 15 June 2021 at 14:40

Hi Tomas,

Interesting to hear about a new generalization method I hadn’t heard of before.

However, as to the specific case of generalizing line elements representing waterways, and especially those tagged as waterway=stream/river in OSM, I have found a combination of ST_SimplifyVW and ST_ChaikinSmoothing, quite effective to produce small scale results.

I would not recommend this combination for road networks?

Why not, and why does it work for waterways IMO?

There is a problem with using ST_ChaikinSmoothing on road networks, as the lines are generalized and smoothed on feature-by-feature basis, unaware of connectivity. Since many highway=x elements in OSM are not split where e.g. alleys connect to a main road, smoothing may and will cause the connectivity of the line network to be lost, as the main road does not have an end node on the junction between the highways. I have shown and explained this issue in these two posts on the openstreetmap-carto issue tracker:

So why does it work better for waterways?: natural waterways tagged as waterway=stream/river seem to be more consistently split where waterways connect, especially in well developed countries. This is likely the consequence of people wanting the use the waterway network for detailed hydrological analysis, that requires properly defined topology and tags on individual segment. As a consequence, much less of the network connectivity issues popup if you use ST_ChaikinSmoothing on natural waterways tagged streams and rivers.

In addition, even where waterways connect without the main waterway being split at the junction, and smoothing thus potentially causing a visual artefact of non-connected lines, the issue as shown in the images on the openstreetmap-carto issue tracker, is usually much less problematic due to the main waterway usually running at a relatively straight course where the line elements meet, and the side stream usually flowing into the main stream at angles less 90 degrees.

In my experience, the visual results of generalization + smoothing on the natural waterways like streams and rivers, is thus pretty good.

Of course, for stuff like human made ditches and canals, especially the small ones present in dense artificial network in e.g. “polders”, this is less so, but these are usually only displayed when zoomed in at large scale and do not really need generalization at all.

Comment from mboeringa on 15 June 2021 at 15:50

I know see in the PDF of the project you referenced, which I hadn’t read before posting my comment, that the exact combination of generalization and smoothing using ST_SimplifyVW and ST_ChaikinSmoothing, was also evaluated in the research you mention.

Looks like an interesting PDF, I will make some time to properly read it later on…

Comment from Tomas Straupis on 15 June 2021 at 19:25

SimplifyVW (or DP) will remove too much important details (and no chance of exaggeration). It is not what human cartographer would do. For example human cartographer would never make meandering river into a straight line as that shows totally different attributes of the river to the geographer. Wang-Muller algorithm is offering a way to overcome that.

You can buy an excellent work of Swiss society of cartographers to get an idea of what pure wizards of cartography are doing (well if you do not have that already:-) * demo document: https://kartografie.ch/wp-content/uploads/demo_no16_en.pdf * old (free) version of the generalisation book: https://kartografie.ch/wp-content/uploads/nr02_generalization.pdf (but I suggest buying the new one as it is more aligned with the development of the technology, I can guarantee - for everybody interested in cartography it is worth each penny you pay) (In my personal opinion this is the best resource I’ve ever came up on generalisation and I went through dozen of 1930-today period books from Europe, USA and Moscow, but please comment if you have an even better resource)

Comment from mboeringa on 15 June 2021 at 20:22

Hi Tomas,

Interesting that link to the Swiss society of cartographers website, which I hadn’t seen before.

How though, do you actually buy that specific document:

No. 16 -Topografische Karten – Kartengrafik und Generalisierung

I do not see any link to a webshop for ordering?

Comment from SK53 on 18 June 2021 at 11:02

@mboeringa Check on the Publications page, listed as CHF 10