Algorithms for Curved Schematization

Arthur van Goethem

Promotors: prof.dr. B. Speckmann (TU/e) and prof.dr. M.J. van Kreveld (UU)
Technische Universiteit Eindhoven
Date: 31 August 2016, 16:00
Thesis: PDF


Maps are an indispensable part of our lives. They are information dense and can quickly place information in a geographic context. Maps are used by many on a daily basis, helping to make decisions in navigation, spatial planning, and risk and disaster management. To facilitate efficient decision-making, task-appropriate maps are as simple as possible. By omitting unneeded detail emphasis is given to the main message.

Schematization is the process of creating a simplified and compact representation of the original input data. It reduces detail, possibly going beyond the needs of the target scale or medium. Design-based rules further emphasize the visual appearance over geographic accuracy. Schematization can structure and simplify information, reduce the illusion of accuracy, and help create a striking and powerful message. One of the most well-known examples is Beck’s iconic map of the London underground.

There is an extensive body of work on algorithmic methods for schematization using straight lines. Traditional cartography, however, commonly makes use of curves for schematization. Curves have a greater expressive power and, hence, naturally lend themselves to the reduction of detail. In this thesis we look at possibilities for automated schematization using curves. Automated curved schematization has implications for algorithms, cartography, and visualization.

In the first part of this thesis we focus on the schematization of territorial outlines. We present a generic framework for topology-preserving curved schematization that can be instantiated with different quality measures and curve types. Using the edge-based Voronoi diagram we ensure that the schematization maintains the correct topology. Curves can be fitted only between vertices of the input, and as such the approach is vertex-restricted.

The ability to introduce new vertices may significantly increase the expressiveness of a schematization.
Hence, we present a second approach that is non-vertex-restricted. Iterative detail reduction via local operations allows new vertices to be introduced removing the restrictions placed by the input vertices. By prioritizing operations according to different schemes we obtain results of varying degree of `curviness’. The method creates visually pleasing results even for very low output complexities and combines well with different rendering styles. We present a geometric evaluation of the resulting schematizations.

Besides a geometric evaluation, we also evaluate the perceived effects of curved schematization. We discussed the results from an online user survey comparing the effects of curved versus straight-line schematization. Curved schematizations were deemed aesthetically more pleasing, but were considered as more complex. The use of curves also improved the recognizability for schematized shapes of moderately complexity.

Having explored territorial boundaries, in the next part we shift our attention to the schematization of networks. Networks are generally more densely connected than territorial outlines, restricting the options for schematization.

The third approach we introduce removes the constraint that vertices of degree three or higher are reserved. Our algorithm can introduce circular arcs that span across these vertices. Consequently it is able to significantly reduce the complexity even for densely connected networks. We explore the suitability and effectiveness of this algorithm for three different use cases. The results are of high-quality for both territorial outlines and metro maps. The lack of caricature, however, reduces the effectiveness for road networks.

In linear cartograms a metric (e.g., travel-time) is projected onto a network by proportionally distorting the underlying geographic map. Distances in these maps do not correspond to geographic distances anymore, but instead correspond to the metric. The geography of the underlying map, however, may be severely distorted. We introduce an alternative model where the (road) network is distorted, but the rest of the map remains undistorted. Edges are drawn as sinusoid curves using edge length as an encoding. Curves may be placed in three possible positions. We describe an efficient algorithm to compute a suitable, non-intersecting placement of the curved edges. We also show that maximizing the number of curves in the center position is NP-hard, but that heuristics may produce high-quality results.

In the last part of this thesis we explore the limits of schematization. Traditional schematization considers shape schematization as a schematization of the boundary of a shape. We present a radically different type of geometric abstraction — the stenomap. Stenomaps represent two-dimensional input shapes by smoothly curving linear glyphs. We present an efficient algorithm to automatically generate these open, C1-continuous splines from a set of input polygons. The glyphs offer new possibilities in the `cartographic design space’ and we discuss their relative merits and shortcomings. Finally, we describe several use cases including the depiction of uncertain model data; minimal ink thematic mapping; and the depiction of continuous statistical data.