wm/mj-msc.tex

\documentclass[a4paper]{article}

\usepackage[T1]{fontenc}
\usepackage[american]{babel}
\usepackage[utf8]{inputenc}
\usepackage{fvextra}
\usepackage[autostyle,english=american]{csquotes}
\MakeOuterQuote{"}
\usepackage[
    maxbibnames=99,
    style=numeric,
    sorting=none,
    alldates=iso,
    seconds=true
]{biblatex}
\addbibresource{bib.bib}
\usepackage[
    pdfusetitle,
    pdfkeywords={Line Generalization,Line Simplification,Wang--Mueller},
    pdfborderstyle={/S/U/W 0} % /S/U/W 1 to enable reasonable decorations
]{hyperref}
\usepackage{enumitem}
\usepackage[toc,page,title]{appendix}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{dcolumn}
\usepackage{gensymb}
\usepackage{units}
\usepackage{varwidth}
\usepackage{tabularx}
\usepackage{float}
\usepackage{numprint}
\usepackage{tikz}
\usetikzlibrary{shapes.geometric,arrows,positioning}
\usepackage{fancyvrb}
\usepackage{layouts}
\usepackage{minted}
%\usepackage{charter}
%\usepackage{setspace}
%\doublespacing

\input{version.inc}
\input{vars.inc}

\newcommand{\onpage}[1]{\ref{#1} on page~\pageref{#1}}
\newcommand{\titlecite}[1]{\citetitle{#1}\cite{#1}}
\newcommand{\titleciteauthor}[1]{\citetitle{#1} by \citeauthor{#1}\cite{#1}}
\newcommand{\DP}{Douglas \& Peucker}
\newcommand{\VW}{Visvalingam--Whyatt}
\newcommand{\WM}{Wang--M{\"u}ller}
\newcommand{\WnM}{Wang and M{\"u}ller}
\newcommand{\WirM}{Wang ir M{\"u}ller}
% {\WM} algoritmo realizacija kartografinei upių generalizacijai
\newcommand{\MYTITLE}{{\WM} algorithm realization for cartographic line generalization}
\newcommand{\MYTITLENOCAPS}{wang--m{\"u}ller algorithm realization for cartographic line generalization}
\newcommand{\MYAUTHOR}{Motiejus Jakštys}
\newcommand{\inputcode}[2]{\inputminted[fontsize=\small]{#1}{#2}}
\newenvironment{longlisting}{\captionsetup{type=listing}}{}

\title{\MYTITLE}
\author{\MYAUTHOR}
\date{\VCDescribe}

\begin{document}

\begin{titlepage}
    \begin{center}
        \includegraphics[width=0.2\textwidth]{vu.pdf} \\[4ex]

        \large
        \textbf{\textsc{
            vilnius university \\
            faculty of chemistry and geosciences \\
            department of cartography and geoinformatics
        }} \\[8ex]

        \textbf{\MYAUTHOR} \\[8ex]

        \normalsize
        A Thesis Presented for the Degree of Master in Cartography \\[8ex]

        \LARGE
        \textbf{\textsc{\MYTITLENOCAPS}}

        \vfill

        \normalsize
        Supervisor Dr. Andrius Balčiūnas \\[16ex]

        \VCDescribe
    \end{center}
\end{titlepage}

\begin{abstract}
\label{sec:abstract}

    Currently available line simplification algorithms are rooted in
    mathematics and geometry, and are unfit for bendy map features like rivers
    and coastlines. {\WnM} observed how cartographers simplify these natural
    features and created an algorithm. We implemented this algorithm and
    documented it in great detail. Our implementation makes {\WM} algorithm
    freely available in PostGIS, and this paper explains it.

    \vfill

    Šiuo metu esami linijų supaprastinimo algoritmai yra kilę iš matematikos ir
    geometrijos, bet nėra tinkami lankstiems geografiniams objektams, tokiems
    kaip upės ir pakrantės, atvaizduoti. {\WirM} ištyrė, kaip kartografai
    atlieka upių generalizaciją, ir sukūrė algoritmą. Mes realizavome šį
    algoritmą ir išsamiai jį dokumentavome. Mūsų {\WM} realizacija ir
    dokumentacija yra nemokamos ir laisvai prieinamos, naudojant PostGIS
    platformą.

\end{abstract}

\clearpage

\tableofcontents

\listoftables
\listoflistings

\newpage

\section{Introduction}
\label{sec:introduction}

\iffalse
NOTICE: this value should be copied to layer2img.py:TEXTWIDTH, so dimensions
of inline images are reasonable.

Textwidth in cm: {\printinunitsof{cm}\prntlen{\textwidth}}
\fi

When creating small-scale maps, often the detail of the data source is greater
than desired for the map. While many features can be removed or simplified, it
is more tricky with natural features that have many bends, like coastlines,
rivers, or forest boundaries.

To create a small-scale map from a large-scale data source, features need to be
simplified, i.e., detail should be reduced. While performing the
simplification, it is important to retain the "defining" shape of the original
feature. Otherwise, if the simplified feature looks too different from the
original, the result will look unrealistic. Simplification problem for some
objects can often be solved by non-geometric means:

\begin{itemize}
    \item Towns and cities can be filtered by the number of inhabitants.
    \item Roads can be eliminated by the road length, number of lanes, or
        classification of the road (local, regional, international).
\end{itemize}

However, things are not as simple for natural features like rivers or
coastlines. If a river is nearly straight, it should remain such after
simplification. An overly straightened river will look like a canal, and the
other way around --- too curvy would not reflect the natural shape. Conversely,
if the river originally is highly wiggly, the number of bends should be
reduced, but not removed altogether. Natural line simplification problem can be
viewed as a task of finding a delicate balance between two competing goals:

\begin{itemize}
    \item Reduce detail by removing or simplifying "less important" features.
    \item Retain enough detail, so the original is still recognizable.
\end{itemize}

Given the discussed complexities with natural features, a fine line between
under-simplification (leaving an object as-is) and over-simplification (making a
straight line) needs to be found. Therein lies the complexity of simplification
algorithms: all have different trade-offs.

The purpose of the thesis is to implement a cartographic line generalization
algorithm on the basis of {\WM} algorithm, using open-source software. Tasks:

\begin{itemize}
    \item Evaluate existing line simplification algorithms.
    \item Identify main river generalization problems, using classical line
        simplification algorithms.
    \item Define the method of the {\WM} technical implementation.
    \item Realize {\WM} algorithm technically, explaining the geometric
        transformations in detail.
    \item Apply the created algorithm for different datasets and compare
        the results with national datasets.
\end{itemize}

Scientific relevance of this work --- the simplification processes (steps)
described by the {\WM} algorithm --- are analyzed in detail, practically
implemented, and the implementation is described. That expands the knowledge of
cartographic theory about the generalization of natural objects' boundaries
after their natural defining properties.

In the original {\WM} article introducing the algorithm, the steps are not
detailed in a way that can be put into practice for specific data; the steps are
specified in this work. Practically, this work makes it possible to use open-source software to perform cartographic line generalization. The developed
specialized cartographic line simplification algorithm can be applied by
cartographers to implement automatic data generalization solutions. Given the
open-source nature of this work, the algorithm implementation can be modified
freely.

\section{Literature Review And Problematic}
\label{sec:literature-review-problematic}

\subsection{Available Algorithms}

This section reviews the classical line simplification algorithms, which,
besides being around for a long time, offer easily accessible implementations,
as well as more modern ones, which only theorize, but do not provide an
implementation.

\subsubsection{{\DP}, {\VW} and Chaikin's}
\label{sec:dp-vwchaikin}

{\DP}\cite{douglas1973algorithms} and {\VW}\cite{visvalingam1993line} are
"classical" line simplification computer graphics algorithms. They are
relatively simple to implement and require few runtime resources. Both of them
accept a single parameter based on desired scale of the map, which makes them
straightforward to adjust for different scales.

Both algorithms are available in PostGIS, a free-software GIS suite:
\begin{itemize}
    \item {\DP} via
        \href{https://postgis.net/docs/ST_Simplify.html}{PostGIS \textsc{st\_simplify}}.

    \item {\VW} via
        \href{https://postgis.net/docs/ST_SimplifyVW.html}{PostGIS
        \textsc{st\_simplifyvw}}.
\end{itemize}

It may be worthwhile to post-process those through Chaikin's line smoothing
algorithm\cite{chaikin1974algorithm} via
\href{https://postgis.net/docs/ST_ChaikinSmoothing.html}{PostGIS
\textsc{st\_chaikinsmoothing}}.

In generalization examples, we will use two rivers: Šalčia and Visinčia.
These rivers were chosen because they have both large and small bends, and
thus are convenient to analyze for both small- and large-scale generalization.
Figure~\onpage{fig:salvis-25} illustrates the original two rivers without any
simplification.

\begin{figure}[ht]
    \centering
    \includegraphics[width=\textwidth]{salvis-25k}
    \caption{Example rivers for visual tests (1:{\numprint{25000}}).}
    \label{fig:salvis-25}
\end{figure}

\begin{figure}[ht]
    \centering
    \begin{subfigure}[b]{.49\textwidth}
        \includegraphics[width=\textwidth]{salvis-2x50k}
        \caption{Example scaled 1:\numprint{50000}.}
        \label{fig:salvis-2x50k}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{.49\textwidth}
        \centering
        \includegraphics[width=.2\textwidth]{salvis-250k-10x}
        \caption{Example scaled 1:\numprint{250000}.}
    \end{subfigure}
    \caption{Down-scaled original river.}
    \label{fig:salvis-50-250}
\end{figure}

Same rivers, unprocessed but in higher scales (1:\numprint{50000} and
1:\numprint{250000}), are depicted in Figure~\ref{fig:salvis-50-250}. Some
river features are so compact that a reasonably thin line depicting the river
is touching itself, creating a thicker line. We can assume that some
simplification for scale 1:\numprint{50000} and especially for
1:\numprint{250000} is worthwhile.

\begin{figure}[ht]
    \centering
    \begin{subfigure}[b]{.49\textwidth}
        \includegraphics[width=\textwidth]{salvis-dp64-2x50k}
        \caption{Using {\DP}.}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{.49\textwidth}
        \includegraphics[width=\textwidth]{salvis-vw64-2x50k}
        \caption{Using {\VW}.}
    \end{subfigure}
    \caption{Simplified using classical algorithms (1:\numprint{50000}).}
    \label{fig:salvis-generalized-1x50k}
\end{figure}

Figure~\ref{fig:salvis-generalized-1x50k} illustrates the same river bend, but
simplified using {\DP} and {\VW} algorithms. The resulting lines are jagged,
and thus the resulting line looks unlike a real river. To smoothen the jaggedness,
traditionally, Chaikin's\cite{chaikin1974algorithm} is applied after
generalization, illustrated in Figure~\ref{fig:salvis-generalized-chaikin-1x50k}.

\begin{figure}[ht!]
    \centering
    \begin{subfigure}[b]{.49\textwidth}
        \includegraphics[width=\textwidth]{salvis-dpchaikin64-2x50k}
        \caption{{\DP} and Chaikin's.}
        \label{fig:salvis-dpchaikin64-2x50k}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{.49\textwidth}
        \includegraphics[width=\textwidth]{salvis-vwchaikin64-2x50k}
        \caption{{\VW} and Chaikin's.}
        \label{fig:salvis-vwchaikin64-2x50k}
    \end{subfigure}
    \caption{Simplified and smoothened river (1:\numprint{50000}).}
    \label{fig:salvis-generalized-chaikin-1x50k}
\end{figure}

\begin{figure}[ht!]
    \centering
    \begin{subfigure}[b]{.49\textwidth}
        \includegraphics[width=\textwidth]{salvis-overlaid-dpchaikin64-2x50k}

        \caption{Original (fig.~\ref{fig:salvis-2x50k}) and simplified
        (fig.~\ref{fig:salvis-dpchaikin64-2x50k}).}

    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{.49\textwidth}
        \includegraphics[width=\textwidth]{salvis-overlaid-vwchaikin64-2x50k}

        \caption{Original (fig.~\ref{fig:salvis-2x50k}) and simplified
            (fig.~\ref{fig:salvis-vwchaikin64-2x50k}.)}

    \end{subfigure}
    \caption{Zoomed-in simplified and smoothened river and original.}
    \label{fig:salvis-overlaid-generalized-chaikin-1x50k}
\end{figure}

\begin{figure}[b]
    \centering
    \includegraphics[width=\textwidth]{amalgamate1}
    \caption{Narrow bends amalgamating into thick unintelligible blobs.}
    \label{fig:pixel-amalgamation}
\end{figure}

The resulting simplified and smoothened example
(Figure~\onpage{fig:salvis-generalized-chaikin-1x50k}) yields a more
aesthetically pleasing result; however, it obscures natural river features.

Given the absence of rocks, the only natural features that influence the river
direction are topographic:

\begin{itemize}
    \item Relatively straight river (completely straight or with small-angled
        bends over a relatively long distance) implies greater slope, more
        water, and/or faster flow.

    \item Bendy river, on the contrary, implies slower flow, slighter slope,
        and/or less water.

\end{itemize}
Both {\VW} and {\DP} have a tendency to remove the small bends altogether,
removing a valuable characterization of the river.

Sometimes low-water rivers in slender slopes have many bends next to each
other. In low resolutions (either in small-DPI screens or paper, or when the
river is sufficiently zoomed out, or both), the small bends will amalgamate to
a unintelligible blob. Figure~\ref{fig:pixel-amalgamation} illustrates a
real-world example where a bendy river, normally 1 or 2 pixels wide, creates a
wide area, of which the shapes of the bend become unintelligible. In this
example, classical algorithms would remove these bends altogether. A
cartographer would retain a few of those distinctive bends, but would increase
the distance between the bends, remove some of the bends, or both.

% TODO: figues shouldn't split the sentence.

For the reasons discussed in this section, the "classical" {\DP} and {\VW} are
not well-suited for natural river generalization, and a more robust line
generalization algorithm is worthwhile to look for.

\clearpage

\subsubsection{Modern Approaches}

Due to their simplicity and ubiquity, {\DP} and {\VW} have been established as
go-to algorithms for line generalization. During recent years, alternatives
have emerged. These modern replacements fall into roughly two categories:

\begin{itemize}

    \item Cartographic knowledge was encoded to an algorithm (bottom-up
        approach). One among these are \titlecite{wang1998line}, also known
        as {\WM}'s algorithm.

    \item Mathematical shape transformation which yields a more cartographic
        result. E.g., \titlecite{jiang2003line},
        \titlecite{dyken2009simultaneous}, \titlecite{mustafa2006dynamic},
        \titlecite{nollenburg2008morphing}, \titlecite{devangleserrorbends}.

\end{itemize}

Authors of most of the aforementioned articles have implemented the
generalization algorithm, at least to generate the illustrations in the
articles. However, code is not available for evaluation with a desired dataset, much less for use as a basis for creating new maps. To the author's knowledge,
{\WM}\cite{wang1998line} is available in a commercial product, but requires a
purchase of the commercial product suite, without a way to license the
standalone algorithm.

{\WM} algorithm was created by encoding professional cartographers' knowledge
into a computer algorithm. It has a few main properties which make it
especially suitable for generalization of natural linear features:

\begin{figure}[h!]
    \centering
    \includegraphics[width=.8\textwidth]{wang125}
    \caption{Figure 12.5 in \cite{wang1998line}: example of cartographic line
    generalization.}
    \label{fig:wang125}
\end{figure}

\begin{itemize}
    \item Small bends are not always removed, but either combined (e.g.,
        3 bends into 2), exaggerated, or removed, depending on the neighboring
        bends.
    \item Long and gentle bends are not straightened, but kept as-is.
\end{itemize}

As a result of these properties, {\WM} algorithm retains the defining
properties of the natural features: high-current rivers keep their appearance
as such, instead of becoming canals; low-stream bendy rivers retain their
frequent small bends.

Figure~\ref{fig:wang125}, sub-figure labeled "proposed method" (from the
original \titlecite{wang1998line}) illustrates the {\WM} algorithm.

\subsection{Problematic with Generalization of Rivers}

This section introduces the reader to simplification and generalization, and
discusses two main problems with current-day automatic cartographic line
generalization:

\begin{itemize}
    \item Currently available line simplification algorithms were created
        to simplify geometries, but do not encode cartographic knowledge.

    \item Existing cartographic line generalization algorithms are not freely
        accessible.
\end{itemize}

\subsubsection{Simplification versus Generalization}

It is important to note the distinction between simplification, line
generalization, and cartographic generalization.

Simplification reduces an object's detail in isolation, not taking the object's
natural properties or surrounding objects into account. For example, if a
river is simplified, it may have an approximate shape of the original river,
but lose some shapes that define it. For example:

\begin{itemize}

  \item Low-water rivers in slender slopes have many small bends next to each
      other. A non-cartographic line simplification may remove all of them,
        thus losing an important river's characteristic feature: after such
        simplification, it will be hard to tell that the original river was
        low-water in a slender slope.

  \item Low-angle river bend river over a long distance differs significantly
      from a completely straight canal. Non-cartographic line simplification
        may replace that bend with a straight line, making the river more
        similar to a canal than a river.

\end{itemize}

In other words, simplification processes the line, ignoring its geographic
features. It works well when the features are human-made (e.g., roads,
administrative boundaries, buildings). There is a number of freely available
non-cartographic line simplification algorithms, which this paper will review.

Contrary to line simplification, cartographic generalization does not focus
into a single feature class (e.g., rivers), but the whole map. For example,
line simplification may change river bends in a way that bridges (and roads to
the bridges) become misplaced. While line simplification is limited to a single
feature class, cartographic generalization is not. Fully automatic cartographic
generalization is not yet a solved problem. % <TODO: Reference needed>.

Cartographic line generalization falls in between the two: it does more than
line simplification, and less than cartographic generalization. Cartographic
line generalization deals with a single feature class, takes into account its
geographic properties, but ignores other features. This paper examines {\WM}'s
\titlecite{wang1998line}, a cartographic line generalization algorithm.

\subsubsection{Availability of Generalization Algorithms}

Lack of robust openly available generalization algorithm implementations poses
a problem for map creation with free software: there is no high-quality
simplification algorithm to create down-scaled maps, so any cartographic work,
which uses line generalization as part of its processing, will be of sub-par
quality. We believe that the availability of high-quality open-source tools is an
important foundation for future cartographic experimentation and development,
thus it benefits the cartographic society as a whole.

{\WM}'s commercial availability signals something about the value of the
algorithm: at least the authors of the commercial software suite deemed it
worthwhile to include it. However, not everyone has access to the commercial
software suite, access to funds to buy the commercial suite, or access to the
operating system required to run the commercial suite. PostGIS, in contrast, is
free itself, and runs on free platforms. Therefore, algorithm
implementations that run on PostGIS or other free platforms are useful to a
wider cartographic society than proprietary ones.

\subsubsection{Unfitness of Line Simplification Algorithms}

Section~\ref{sec:dp-vwchaikin} illustrates the current gaps with line
simplification algorithms for real rivers. To sum up, we highlight the
following cartographic problems from our examples:

\begin{description}

    \item[Long bends] should remain as long bends, instead of becoming fully
        straight lines.

    \item[Many small bends] should not be removed. To retain a river's character,
        the algorithm should retain some small bends, and, when they are too
        small to be visible, they should be combined or exaggerated.

\end{description}

We are limiting the problem to cartographic line generalization. That is, full
cartographic generalization, which takes topology and other feature classes
into account, is out of scope.

Figure~\onpage{fig:wang125} illustrates {\WM} algorithm from their original
paper. Note how the long bends retain curvy, and how some small bends get
exaggerated.

\section{Methodology}
\label{sec:methodology}

The original {\WM}'s algorithm \cite{wang1998line} leaves something to be
desired for a practical implementation: it is not straightforward to implement
the algorithm from the paper alone.

Explanations in this document are meant to expand, rather than substitute, the
original description in {\WM}. Therefore, familiarity with the original paper is
assumed, and, for some sections, having the original close-by is necessary to
meaningfully follow this document.

This paper describes {\WM} in detail that is more useful for anyone who wishes
to follow the algorithm implementation more closely: each section is expanded
with additional commentary, and illustrations added for non-obvious steps. Corner
cases are discussed, too.

\subsection{Main Geometry Elements Used by Algorithm}
\label{sec:vocab}

This section defines and explains the geometry elements that are used
throughout this paper and the implementation. Assume Euclidean geometry
throughout this document, unless noted otherwise.


\begin{description}

    \item[\normalfont\textsc{vertex}] is a point on a plane, can be expressed
        by a pair of $(x,y)$ coordinates.

    \item[\normalfont\textsc{line segment}] or \textsc{segment} joins two
        vertices by a straight line. A segment can be expressed by two
        coordinate pairs: $(x_1, y_1)$ and $(x_2, y_2)$. Line segment and
        segment are used interchangeably.

    \item[\normalfont\textsc{line}] or \textsc{linestring} represents a single
        linear feature. For example, a river or a coastline.

        Geometrically, a line is a series of connected line segments, or,
        equivalently, a series of connected vertices. Each vertex connects to
        two other vertices, with the exception of the vertices at either ends of the line:
        these two connect to a single other vertex.

    \item[\normalfont\textsc{multiline}] or \textsc{multilinestring} is a
        collection of linear features. Throughout this implementation, this is
        used rarely (normally, a river is a single line) but can be valid
        when, for example, a river has an island.

    \item[\normalfont\textsc{bend}] is a subset of a line that humans perceive
        as a curve. The geometric definition is complex and is discussed in
        section~\ref{sec:definition-of-a-bend}.

    \item[\normalfont\textsc{baseline}] is a line between the bend's first and last
        vertices.

    \item[\normalfont\textsc{sum of inner angles}] is a measure of how "curved"
        the bend is. Assume that first and last bend vertices are vectors. Then sum
        of inner angles will be the angular difference of those two vectors.

    \item[\normalfont\textsc{algorithmic complexity}] measured in \textsc{big o
        notation}, is a relative measure that helps explain how
        long\footnote{the upper bound, i.e., the worst case.} the
        algorithm will run depending on its input. It is widely used in computing
        science when discussing the efficiency of a given algorithm.

        For example, given $n$ objects and time complexity of $O(log(n))$, the
        time it takes to execute the algorithm is logarithmic to $n$.
        Conversely, if complexity is $O(n^2)$, then the time it takes to
        execute the algorithm grows quadratically with input. Importantly, if
        the input size doubles, the time it takes to run the algorithm
        quadruples.

        \textsc{big o notation} was first suggested by
        Bachmann\cite{bachmann1894analytische} and Landau\cite{landau1911} in
        late \textsc{xix} century, and clarified and popularized for computing
        science by Donald Knuth\cite{knuth1976big} in the 1970s.

\end{description}

\clearpage

\subsection{Algorithm Implementation Process}
\label{sec:algorithm-implementation-process}

\tikzset{
  startstop/.style={trapezium,text centered,minimum height=2em,
    trapezium left angle=70,trapezium right angle=110,draw=black,fill=red!20},
  proc/.style={rectangle,minimum height=2em,text centered,draw=black,
    fill=orange!20},
  decision/.style={diamond,minimum height=2em,text centered,aspect=3,
    draw=black,fill=green!20},
  arrow/.style={thick,->,>=stealth},
}

\begin{figure}[!ht]
  \centering
  \begin{tikzpicture}[node distance=1.5cm,auto]
    \node (start) [startstop] {Read \textsc{linestring}};
    \node (detect) [proc,below of=start] {Detect bends};
    \node (inflections) [proc,below of=detect] {Fix gentle inflections};
    \node (selfcrossing) [proc,below of=inflections] {Eliminate self-crossing};
    \node (mutated1) [decision,below of=selfcrossing] {Mutated?};
    \node (bendattrs) [proc,below of=mutated1] {Compute bend attributes};
    \node (exaggeration) [proc,below of=bendattrs] {Exaggeration};