blob 979c8760 (7122B) - Raw
1 \documentclass[a4paper]{article} 2 3 \iffalse 4 \usepackage[L7x,T1]{fontenc} 5 \usepackage[lithuanian]{babel} 6 \else 7 \usepackage[T1]{fontenc} 8 \usepackage[english]{babel} 9 \fi 10 11 \usepackage[utf8]{inputenc} 12 \usepackage{a4wide} 13 \usepackage{csquotes} 14 \usepackage[maxbibnames=99,style=authoryear]{biblatex} 15 \usepackage[pdfusetitle]{hyperref} 16 \usepackage{enumitem} 17 \usepackage[toc,page,title]{appendix} 18 \addbibresource{bib.bib} 19 \usepackage{caption} 20 \usepackage{subcaption} 21 \usepackage{gensymb} 22 \usepackage{varwidth} 23 \usepackage{tabularx} 24 \usepackage{float} 25 \usepackage{tikz} 26 \usepackage{minted} 27 \usetikzlibrary{er,positioning} 28 \definecolor{mypurple}{RGB}{117,112,179} 29 \input{version} 30 31 \newcommand{\DP}{Douglas \& Peucker} 32 \newcommand{\VW}{Visvalingam--Whyatt} 33 \newcommand{\WM}{Wang--M{\"u}ller} 34 35 \newcommand{\MYTITLE}{Cartographic Generalization of Lines using free software (example of rivers)} 36 \newcommand{\MYAUTHOR}{Motiejus Jakštys} 37 38 \title{\MYTITLE} 39 \author{\MYAUTHOR} 40 \date{\VCDescribe} 41 42 \begin{document} 43 44 \begin{titlepage} 45 \begin{center} 46 \includegraphics[width=0.4\textwidth]{vu} 47 48 \huge 49 \textbf{\MYTITLE} \\[4ex] 50 51 \LARGE 52 \textbf{\MYAUTHOR} \\[8ex] 53 54 \vfill 55 56 A thesis presented for the degree of\\ 57 Master in Cartography \\[3ex] 58 59 \large 60 \VCDescribe 61 \end{center} 62 \end{titlepage} 63 64 65 \begin{abstract} 66 \label{sec:abstract} 67 Current open-source line generalization solutions have their roots in 68 mathematics and geometry, and are not fit for natural objects like rivers 69 and coastlines. This paper discusses our implementation of {\WM} algorithm 70 under and open-source license, explains things that we would had 71 appreciated in the original paper and compares our results to different 72 generalization algorithms. 73 \end{abstract} 74 75 \newpage 76 77 \tableofcontents 78 \listoffigures 79 80 \newpage 81 82 \section{Introduction} 83 \label{sec:introduction} 84 85 When creating small-scale maps, often the detail of the data source is greater 86 than desired for the map. This becomes especially acute for natural features 87 that have many bends, like coastlines, rivers and forest boundaries. 88 89 To create a small-scale map from a large-scale data source, these features need 90 to be generalized: detail should be reduced. However, while doing so, it is 91 important to preserve the "defining" shape of the original feature, otherwise 92 the result will look unrealistic. 93 94 For example, if a river is nearly straight, it should be nearly straight after 95 generalization, otherwise a too straightened river will look like a canal. 96 Conversely, if the river is highly wiggly, the number of bends should be 97 reduced, but not removed. 98 99 Generalization problem for other objects can often be solved by other 100 non-geometric means: 101 102 \begin{itemize} 103 \item Towns and cities can be filtered and generalized by number of 104 inhabitants. 105 \item Roads can be eliminated by the road length, number of lanes, or 106 classification of the road (local, regional, international). 107 \end{itemize} 108 109 Natural line generalization problem can be viewed as having two competing 110 goals: 111 112 \begin{itemize} 113 \item Reduce detail by removing or simplifying "less important" features. 114 \item Retain enough detail, so the original is still recognize-able. 115 \end{itemize} 116 117 Given the discussed complexities, a fine line between under-generalization 118 (leaving object as-is) and over-generalization (making a straight line) must be 119 found. Therein lies the complexity of generalization algorithms: all have 120 different trade-offs. 121 122 \section{Literature review} 123 \label{sec:literature-review} 124 125 A number of cartographic line generalization algorithms have been researched. 126 The "classical" ones are {\DP} and {\VW}. 127 128 \subsection{{\DP} and {\VW}} 129 130 \cite{douglas1973algorithms} and \cite{visvalingam1993line} are "classical" 131 line generalization computer graphics algorithms. They are relatively simple to 132 implement, require few runtime resources. Both of them accept only a single 133 parameter, based on desired scale of the map, which makes them very simple to 134 adjust for different scales. 135 136 Both algorithms are part of PostGIS, a free-software GIS suite: 137 \begin{itemize} 138 \item \cite{douglas1973algorithms} via 139 \href{https://postgis.net/docs/ST_Simplify.html}{PostGIS Simplify}. 140 141 \item \cite{visvalingam1993line} via 142 \href{https://postgis.net/docs/ST_SimplifyVW.html}{PostGIS SimplifyVW}. 143 \end{itemize} 144 145 Since both algorithms produce jagged output lines, it is worthwhile to process 146 those through a widely available \cite{chaikin1974algorithm} smoothing 147 algorithm via \href{https://postgis.net/docs/ST_ChaikinSmoothing.html}{PostGIS 148 ChaikinSmoothing}. 149 150 Even though {\DP} and {\VW} are simple to understand and computationally 151 efficient, they have serious deficiencies for cartographic natural line 152 generalization. 153 154 <TODO: expand on deficiencies> 155 156 \subsection{Modern approaches} 157 158 Due to their simplicity and ubiquity, {\DP} and {\VW} have been established as 159 go-to algorithms for line generalization. During recent years, more modern 160 replacement algorithms have emerged. These fall into roughly two categories: 161 162 \begin{itemize} 163 \item Cartographic knowledge was encoded to an algorithm (bottom-up 164 approach). One among these are \cite{wang1998line}. 165 \item Mathematical shape transformation which yields a more cartographic 166 result. E.g. \cite{jiang2003line}, \cite{dyken2009simultaneous}, 167 \cite{mustafa2006dynamic}, \cite{nollenburg2008morphing}. 168 \end{itemize} 169 170 Authors of most of the aforementioned articles have implemented the 171 generalization algorithm, at least to generate the visuals in the articles. 172 However, I wasn't able to find code for any of those to evaluate with my 173 desired data set, or use as a basis for my own maps. \cite{wang1998line} is 174 available in a commercial product. 175 176 The lack of robust openly available generalization algorithm implementations 177 poses a problem for map creation with free software: there is not a similar 178 high-quality simplification algorithm to create down-scaled maps, so any 179 cartographic work, which uses line generalization as part of its processing, 180 will be of sub-par quality. We believe that availability of high-quality 181 open-source tools is an important foundation for future cartographic 182 experimentation and development, thus it it benefits the cartographic society 183 as a whole. 184 185 \section{Methodology} 186 \label{sec:methodology} 187 188 \section{Conclusions} 189 \label{sec:conclusions} 190 191 \section{Related Work and future suggestions} 192 \label{sec:related_work} 193 194 \printbibliography 195 196 \begin{appendices} 197 198 \section{Code listings} 199 200 We strongly believe ability to reproduce the results is critical for any 201 scientific work. To make it possible for this algorithm, all source 202 files and accompanying scripts have been attached to the PDF. To preview 203 the code listings and re-generate this document, run this simple script: 204 205 \inputminted[fontsize=\small]{bash}{extract-and-generate} 206 207 A reasonably up-to-date Linux or OS X system with a working Docker installation 208 is required to re-generate this document. 209 210 \end{appendices} 211 \end{document}