Generalisation in the Context of Schematised Maps

Abstract

In the last decade schematised maps have garnered substantial research interest from disciplines such as cartography, computational geometry and spatial cognition. More often than not, the approaches have been following their own specific goals, leaving the question of what they have in common relatively open. Most research has had metro maps and their automated creation as its focus. In this chapter we seek a more systematic treatment of what constitutes schematised maps. This chapter organises and differentiates the understanding of what schematisation is and how it relates to generalisation. Three cases studies variously explore and illustrate developments in the automatic generation of schematised maps.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

10.1 The Nature of Schematised Maps

Conventionally the focus of application of map generalisation techniques has been on topographic mapping (Stoter et al. 2009). Typically a broad collection of generalisation operators are variously applied to control content (model generalisation) and its display (cartographic generalisation) with the ambition of creating a map relevant to a wide audience. The topographic map typically contains a broad range of entities—both natural and anthropogenic and throughout the generalisation process the desire is to conserve the positional accuracy of the features represented on the map (their relative distances, shapes and areas). This enables the map reader to readily move between the objects as represented on the map and the features experienced in the landscape. In such contexts, we might say that ‘x and y are sacrosanct’, in that we wish to preserve as far as is possible, the correct geographical location of objects both in absolute and thus relative terms. But there are other types of maps that are highly thematic in nature, for which the ambition of abstraction is just as important, if not more so. One such type is ‘schematised maps’—maps that we might characterise as bereft of detail, emphasising properties such as causality, connectivity, and flow. In schematised maps, x and y are highly malleable—the movement of features are allowed if it results in simpler forms, that are more readily understood. By malleable, we mean that locational accuracy is ‘sacrificed’ if it results in a simpler, more consumable conceptual understanding of the relationship between the mapped entities. As such, schematic maps are narrow in their function and task, often stripped bare of their geography in the interests of instantaneous comprehension. These are maps that reflect the ultimate in generalisation—since they are abstractions of reality reduced down to their absolute essential elements. Metro maps are a frequently cited example of schematised maps (Roberts 2012), though in reality there are many other examples (Fig. 10.1).

Fig. 10.1

Bünting’s ‘cloverleaf’ world from 1581, showing the relationship between Jerusalem and its surrounding geography. http://upload.wikimedia.org/wikipedia/commons/8/87/1581_Bunting_clover_leaf_map.jpg

It is relatively recently that attention has focused on the role of map generalisation techniques in the automated production of schematised maps (Reimer and Fohringer 2010). In trying to automate their design, the challenge is in (1) linking the task requirements (what are the user’s needs) to a set of generalisation techniques, and (2) modelling the point at which a satisfactory design has been reached (neither too much nor too little abstraction).

As part of the generalisation process we must take care not to exceed the point at which we lose all notion of the geographic (Fig. 10.2). The limit of distortion that the user will tolerate will depend on factors such as familiarity, perceptibility and recognition (Montello 2002). Modelling constraints in highly abstracted forms is something that generalisation researchers have not had much reason to think about because of their focus on topographic maps where traditionally the degree of application of generalisation techniques has been limited by the need to preserve the underlying geography. What appears to be required is ‘pattern aware’ map generalisation (Steiniger 2007); by this we mean an environment in which the essential properties (metric, topological, semantic) of a geographic entity can be explicitly measured against increasing levels of abstraction—such that we can model the changing emphasis being given to certain map qualities. These significant changes arising from the process of abstraction amount to what Muller referred to as ‘conceptual cusps’ (Muller 1991). Typically conceptual cusps are points in the map generalisation process where the dimensionality of objects change. There is something of a paradox in that we intentionally distort and alter the geography in order to transit these conceptual cusps and that we do this precisely to gain these higher synoptic ‘states’ and different conceptualisations of the geography represented by the entities.

Fig. 10.2

Increasing levels of abstraction in the representation of Spain: modified from Ferras (1986)

Trying to determine which is the ‘best generalised solution’ highlights the need to consider context and task, though trying to link the two has proved elusive (Head 1991). Some researchers have tried to link map generalisation to task and context for example in the context of mobile mapping (Nivala and Sarjakoski 2003; Ware et al. 2006), but it remains an area very much in need of research. In the meantime it is the cartographer who must decide how far to push the design of their schematised map.

10.2 A Definition of Schematisation

We define schematisation in cartography as a process that uses cartographic generalisation operators in such a way as to produce maps of a lower graphical complexity compared to maps of the same scale; the process aims to maximise task-adequacy while minimizing non-functional detail. This is in contrast to traditional cartographic generalisation which seeks to maximise functional detail with task-adequacy (in the form of legibility) as a constraint—a significant difference being that schematised maps are much less beholden to their locational constraints (Klippel et al. 2005) whereas traditional maps are constructed from precise measurements, in which the outlines of features are shown as accurately as is possible within the limitations of scale (ICA 1973). Topographic, thematic and schematised map can usefully be differentiated by examining the relationship between map detail and intent. Imagine a two axis graph, the y axis ordered from ‘sparse’ to ‘detailed’, and an x axis of intent, ranging from the very general to the highly specific. For a two axis graph of geographic detail against intent, we can define a topographic map as something intended for a broad audience, containing high levels of detail. Thematic maps by definition have a specific audience in mind, and often contain topographically correct contextualising information. This is in contrast to schematised maps, that are highly specific in their ambition, and minimalist in their content (Fig. 10.3).

Fig. 10.3

Differentiating topographic, thematic and schematised maps

10.3 A Classification of Schematised Maps

We have identified seven types of schematised maps (Table 10.1); these include mental maps and sketch maps, educational, propaganda, mass media info-graphics, and schematic maps. There is some overlap between schematised maps and what Muehlenhaus (2013) calls ‘persuasive maps’. While educational, propaganda and mass media schematised maps surely could be categorised as persuasive, not all persuasive maps are actually schematised in the above definition’s sense.

Table 10.1 Examples of various types of schematised map

A mental map or sketch map reflects a person’s perception of that space, based more on their feelings and experiences than a desire to record locational accuracy (Gould and White 2004; Sester and Elias 2007). Educational schematised maps are synthetic thematic depictions (often at the scale of continents or countries), using a specific symbol set on schematised as well as non-schematised and emptied base maps (e.g. Jalta et al. 2006). The objective is a map of sufficient simplicity that it can be readily memorised (Gürtler 1927; Sitte 1996).

Propoganda maps are suggestive maps that are created specifically to reinforce and emphasise how spatial processes and situations mirror ideological preconceptions about the world and how it works. They too require instant comprehension and typically use simple geometries, high contrast colours and striking symbols (Scharfe 1997; Ogrissek 1983). Also included under this heading are ‘geopolitical maps’ (Ogrissek 1983; Bollmann and Koch 2002).

Of growing importance are mass media maps and infographics. Their nature is decidedly ephemeral with short production cycles and low exposure times. The ambition is highly schematised depictions with low cartographic complexity and a symbology of high iconicity. This is different from Web-mapping which afford means of interaction and are not constrained by limited exposure time. Schematic maps such as topograms or metro maps depict (mostly in linear form) geographical entities with emphasis on the correct topology but locationally distorted in order to achieve greater clarity. The most famous example is the London Tube Map. A review of algorithmic solutions to the automated production of such maps is considered in the first case study (see also Wolff 2007).

Chorematic diagrams are all those maps and map-like diagrams that use one or more graphical embodiments of the choremes as introduced by Roger Brunet (explored in greater detail in the second case study). As a final group, we include ‘geodesign maps’. These types of map have evolved in response to the needs of planners. Typically they use an intricate system of hachures and colours on top of subdued topographical information. They are perceived as being especially useful for communicating strategic political scenarios and high level policy guidelines that do not require precise locational information (Rase and Sinz 1993; Stiens 1996; Dühr 2007). In recent years, a homogenisation of EU planning cartography is in evidence in which geodesign and chorematic concepts are both toned down and retained at the same time (e.g. Schmidt-Seiwert et al. 2006; Dühr 2007).

10.4 Methods of Schematisation Production

The forms of schematisation can be readily matched with existing generalisation operators and concepts (Hake et al. 2002; Regnauld and McMaster 2007), the key difference being the intensity with which they are applied. The first step is one of synthesis—the careful selection of pertinent data (model generalisation). The second stage is a reduction in detail achieved through amalgamation, and object simplification. Typically the target contains a low number of classes, requiring strong amalgamation. Often, smaller patches of non-matching objects are reclassified and amalgamated to provide a low number of contiguous objects. Elimination is an extreme case of selection where all non-functional detail is omitted in order to reduce cognitive workload and concentrate on just a few message(s). Line and area objects typically undergo smoothing—even if the entity is angular in form. For example anthropogenic angular borders may be replaced with gentle Bezier-curves in order to emphasise the continuity of form. Additionally schematised maps are sometimes characterised by strict angular restriction and circular arcs (for example Case study I), a process which we call stylisation. Features and objects can also be collapsed (transformed from a higher differentiation schema to one of lower degree), or iconised (the process of transforming recurring shapes into glyph-like depictions). Beyond this conventional set of operators, other transformations include reduced dimensionality (e.g. polygons to lines), and representing linear and polygonal forms in symmetric shapes. Additionally, entities are often represented as caricatures of themselves—where one part of an object is emphasised over another, resulting in an uneven degree of schematisation in the interests of the message’s easy recognition.

10.4.1 Governing the Generalisation Process in Schematisation

As in any generalisation process, the challenge is in knowing when to stop (i.e. how do we know that the solution is sufficient?). Essentially, in topographic mapping, the difference in geometric scale is the governing force in generalisation. The ambition in schematised maps is different; here, it is the move from higher to lower cartographic complexity that governs schematisation. Such a statement leads us to the requirement for a measure of map complexity. One way to do this has been proposed by Reimer (2010) using cartographic line frequency:

$$ OLLpA = \frac{{\mathop \sum \nolimits_{i = 1}^{n} \mathop \sum \nolimits_{j = 1}^{m} l_{ij} }}{ab} $$

where l _ij is the line length of object o _ij of object type i, and a, b are the long and short side of the bounding box around all considered map objects. The variable i stands for the number of different object types and j for the number of objects of that type i. Structurally this is the cartographic line frequency, related to Bertin’s density concept of sign per minimum visible distance, which is why we suggest the name Bertin [Bt] for this unit of measurement. This measure encapsulates various ideas, but in particular is:

• based on empirical legibility research (e.g. Harrie and Stigmar 2010)

• is congruent with information theory and Bertin’s density concept

• is more expressive than other methods of measuring content (such as Töpfer 1977).

10.5 Schematisation Metaphors in Interactive Environments

The various design ideas implicit in these highly abstracted forms have influenced the design of interactive environments, especially where space is of a premium. For example, Haunert and Sering (2011) have experimented with graph-based focus region techniques inspired by the shortcomings of fisheye lenses to reveal localised detail in the map (Fig. 10.4). The undistorted space further away from the enlarged detail acts as a contextualising frame, whilst the region immediately surrounding the detailed area ‘absorbs’ the distortion created by the enlargement.

Fig. 10.4

Localised distortion to reveal detail through graph-based focus region technique (Haunert and Sering 2011)

A different technique for handling large numbers of linear features is ‘edge bundling’. This technique groups together large numbers of linear objects that share the same pathway (Holten and Van Wijk 2009). The technique gives the appearance of a less cluttered, neater presentation of data (Fig. 10.5). Edge bundling is a technique often employed in the realm of Information Visualisation. By automatically grouping edges of a graph for a certain stretch of their length we reduce the number of line crossings. Various approaches exist, such as force-directed, a technique generally popular in graph drawing (e.g. Holten and Van Wijk 2009). Edge bundling’s nearest equivalent in terms of map generalisation is aggregation. Such an approach lends itself to interactive environments, where individual bundles can be highlighted and inspected. While a plethora of techniques exist that optimise some measures, the links from measure or parameter towards task-efficiency remains unclear.

Fig. 10.5

Bundling as a means of showing predominant ‘flows’ (Holten and van Wijk 2009)

Schematised maps offer a new perspective on map generalisation, both in extending the range of techniques used, and in modelling the conditions governing their degree of application. In the three case studies that now follow we explore the level of automation that has been achieved, the success of those designs, and how such maps afford rich and intuitive means of interaction.

10.6 Case Study I: Schematisation of Transportation Networks

• William Mackaness 

1. School of GeoSciences, The University of Edinburgh, Edinburgh, UK

   William Mackaness

In this case study we review approaches to the automated production of schematised maps that take the form of linear abstractions of networks (Avelar 2002). We define a schematised network map as a diagrammatic representation comprising a set of distinct, but interconnected linear features, which taken together, represent a network. The ambition in design is to make simple the task of route planning and route following across a network and this typically involves making the line work simpler, re-orienting lines to avoid confusion, and making various scale adjustments to minimise cluttered areas. The most iconic form of a schematised metro map is Beck’s rendering of the London Underground though this is not the earliest example of this type of thinking. For example Minard’s depiction of Napoleon’s Russian campaign of 1812 is an excellent example of a schematised map (Tufte 2001). But the longevity of Beck’s map is testament to its utility and aesthetic appeal and it remains an inspiration to the manual and automated production of public transport maps the world over (Roberts 2012).

10.6.1 Design Considerations

The design of schematised network maps seeks to minimise contextual information, simplify linear form, emphasise connectivity between distinguishable parts of the network whilst preserving the topology. The ambition is to iron out unnecessary complexity in conveying connectivity between a set of connected stations. From this we can formalise a set of criteria (Table 10.2) in which lines seek to emanate at regular angles from the station, where stations are unambiguously labelled and evenly spaced, and line work has continuity of form.

10.6.2 Combining Context with Schematised Maps

The first criterion listed in Table 10.2 is a selection process in which only the salient information is retained—effectively depriving the reader of contextualising information. This gives focus to the task of route selection and following, the argument is that there is no need to retain a sense of geographical location when travelling a network. The task is often reduced to one of counting the stops, or looking out for the station name. However when the pedestrian emerges into the real world, they need to correctly geo-reference themselves. At this point there is a need for a detailed and ‘true’ geographic representation of the world as they ‘connect back’ into the real geography in which the station finds itself. This has given rise to the idea of the ‘Spider map’—maps that seek to fuse the highly schematised with maps that are geographically ‘correct’. They are comprised a central ‘hub’ that is geographically correct, together with schematised ‘legs’. A level of automation has been achieved (e.g. Mourinho et al. 2011) though this remains an area in need of further development.

Table 10.2 Design criteria for schematised transportation maps

10.6.3 Computational Perspectives

From the discussion of these design criteria, we can see that any given solution is largely one of compromise. Though we can readily distil these criteria, automation of a process in which we collectively optimise this design has proved challenging (Avelar and Hurni 2006). This problem of ‘orchestration’ is common to all generalisation problems. The sorts of questions we need answers to in an automated context are: (1) how do we identify problematic regions? (2) What is the mix of generalisation techniques required (for any given region of the map)? (3) How do we know when we have arrived at a ‘good’ or even a ‘suboptimal but acceptable solution’? What we can say, is that given the importance of preserving topological properties, it is sensible to represent the network in the form of a planar graph, in which the vertices represent stations and edges represent the routes connecting those stations (Gross and Yellen 1999; Di Battista et al. 1999).

If we imagine the geography of the network ‘painted’ onto a rubber sheet, the process of arriving at a schematised version of the map, is primarily one of differentially stretching and shrinking the rubber sheet until a solution is arrived at. The question, for any given vertex or node, is to decide whether any given ‘stretch’ (or displacement) either improves or makes worse the design, according to the criteria listed in Table 10.2. We can think of this in terms of a cost function in which we seek to minimise the loss of geography, minimise ambiguity, whilst maximising the aesthetics, clarity and thus comprehension of the map.

10.6.3.1 Hill Climbing

A number of methodologies have been proposed that model this ‘compromise in design’—seeking to efficiently arrive at a solution among a large number of candidate designs. Invariably these methodologies involve an initial state for which a ‘cost’ is calculated (in effect the cost measures how far that initial state is from an acceptable solution). Assuming the cost is greater than a threshold of acceptance, the initial state is modified (typically displacements are applied to a randomly selected vertex), and the cost re-evaluated. Broadly speaking, if the cost is reduced via the process of displacement, then the new state is retained, otherwise it is discarded. This is how the ‘hill climbing’ algorithm works in which localised optimal solutions can be found. Having started from an initial state (typically a geographically correct map of the location of stations and their connecting segments), the algorithm makes iteratively small displacements in order to arrive at an improved solution (Stott and Rodgers 2004). Hill climbing is good for finding local optimums (in which the solution cannot be improved given the local neighbouring nodes and vertices), but it is not guaranteed to find a more global solution—precisely because its search space is localised.

10.6.3.2 Simulated Annealing

Another popular approach is ‘simulated annealing’. Again we start with an initial state, in which candidate improvements are proposed and costed. If the cost is increased (i.e. the solution is made worse) then it is rejected. Simulated annealing seeks to address the risk that such an approach will lead to sub optimal solutions (i.e. where a localised solution is arrived at that is not a good solution overall). In order to avoid such ‘locally optimal solutions’ we introduce a probability function p. This enables the acceptance of worse solutions as part of the process of finding better overall solutions. The probability function p governs the likelihood of a solution being accepted or rejected, with the value of p increasing as the programme iterates over time:

$$ p = e^{- {\Updelta} {\text{E}}/t} $$

The value of p is dependent on two variables: ΔE (the difference in cost between the current state and proposed new states), and t—the temperature. By analogy as a metal cools, it becomes harder to forge (hence the term ‘simulated annealing’). So too in this process the value of t is initially set high, and decreases in stages. When t is large, there is a greater probability that higher cost new states are retained, but as t decreases, high cost states tend to be rejected. The acceptance of higher cost solutions in the initial phases enables the solution to escape locally optimal solutions (Agrawala and Stolte 2001; Avelar and Huber 2001; Anand et al. 2007).

10.6.3.3 Force Directed Approach

A force directed approach is one in which optimal solutions are modelled as a set of attraction and repulsion forces (Fruchterman and Reingold 1991; Bertault 2000). An example of an attraction force, is the desire for a station to be as close to its original geographic location as possible. An example of a repulsion force is in repelling an adjacent station node in order to have clear separation between nodes. A distance decay function is used to model the influence of adjacent nodes and vertices, such that closer objects have greater ‘force’ than those objects that are further away. The total force action on a vertex or node is calculated by summing all the attraction and repulsion forces from which an optimal direction of movement can be assigned (Hong et al. 2006). Such an approach has been used in transportation maps (Fink et al. 2013; Finkel and Tamassia 2005), in the automated creation of cartograms, and in optimised label placement (Ebner et al. 2003).

Force directed algorithms have been extended to include the idea of an even distribution of circular arc edges that give the image a cleaner aesthetic, and better continuity in which paths are easier to distinguish, one from another. The result is a mapping that is similar to the style of the artist, Mark Lombardi, in which the edges are represented as circular arcs and the edges are equally spaced around each vertex (Duncan et al. 2012). Figure 10.6 is one such an example from the work of Chernobelskiy et al. (2011).

Fig. 10.6

Solution drawn in the style of Mark Lombardi (Chernobelskiy et al. 2011)

10.6.3.4 Mixed Integer Approaches

A fourth approach is based on ideas of ‘integer programming’. Integer programming is concerned with optimisation among a large number of variables in which we wish to model binaries and logical requirements (Bertsimas and Weismantel 2005). Mixed integer programming is an instance of these approaches where some of the variables are not restricted to integers. By relaxing the integer constraint and enlargening the set of possible solutions, solvers can be used and greater modelling flexibility is achieved. Nöllenburg and Wolff (2011a, b) were able to successfully generate high quality solutions using mixed-integer programming techniques, applied to both the network and the labelling of stations (Fig. 10.7a).

Fig. 10.7

a mixed integer approach (Nöllenburg and Wolff 2011a, b); b geographic counterpart of the London underground (http://www.theguardian.com/news/datablog/2013/jan/31/circle-line-tube-map-visualised)

10.6.4 Refinements and Evaluation

Various authors have sought to improve the quality of these automated solutions. For example Fink et al. (2013) used Bézier curves to emphasise continuity of lines using a force directed approach. The ambition was similar to that of Lombardi maps in which we seek to reduce the number of inflection points in the line. Dwyer et al. (2008) refined the process of fitting station nodes to network lines, using least squares regression. By partitioning the lines into segments, they applied least squares regression to a localised set of nodes to find the best fit line. The best fit line is selected from octolinear candidates. Their approach sought to better reflect the overall geographic pattern and distribution of the network, though it did not test for changes in the topology of the network. The work of Stott et al. (2011) proposed a multicriteria optimisation approach in combination with clustering techniques in order to avoid the ‘local minima’ solutions associated with hill climbing algorithms. This was done by detecting local minima using clustering techniques that identified groups of stations, enabling them to be modelled as a group and thus minimising the loss of relative positioning among the group during displacement.

In combination, these approaches are generating solutions that are coming closer and closer to the hand drawn solutions with which we are so familiar (Roberts et al. 2013). Our judgement of the quality of automated solutions is, of course, influenced by that which is familiar, which begins to beg the question: ‘Is there an automated design that is better than Beck’? In their work, Stott et al. (2011) compared their automated solution against geographically correct, and manually generated solutions. They found that the automated solution was preferred in the majority of cases. Nöllenburg and Wolff (2011a, b) compared their output against the automated outputs of Hong et al. (2006) and Stott et al. (2011), using three case studies. Of the three, their solution was preferred, and was deemed by experts to surpass the official version in respect of some of the design criteria.

10.6.5 Conclusions

Manually produced solutions can have a beauty and an aesthetic all of their own. For automated solutions, the challenge is in modelling the balance between displacement, line simplification and smoothing. Despite the complexity in their design, the quality of automated solutions is such that it is becoming increasingly hard to differentiate hand drawn solutions from automated ones. The advantage of automated solutions over hand drawn solutions is in their speed, and capacity to be applied to other types of ‘network’ data. For example schematisation algorithms have been applied to generalisation of flight paths (Hurter et al. 2010), cable plans (Lauther and Stübinger 2001), and road networks (Cabello et al. 2001; Haunert and Sering 2011; Li and Dong 2010; Casakin et al. 2000). Furthermore, all of these uncluttered forms of representation lend themselves to display on mobiles (with their typically limited screen size) (Wang and Chi 2011). More broadly, developments in automated solutions to schematised transport maps demonstrates the importance and relevance of graph drawing and optimisation algorithms to the field of map generalisation.

10.7 Case Study II: Chorematic Diagrams

• Andreas Reimer 

1. Institute of Geography, University of Heidelberg, Heidelberg, Germany

   Andreas Reimer

Chorematic diagrams can be understood as schematised thematic maps, which follow a certain line of geographic thinking. This school of thought is called “chorematique” and was invented by the French geographer and cartographer Roger Brunet (1980). His work has had a lasting impact on European spatial planning, school education and French geography (Reimer 2010). Their striking clarity (Fig. 10.8), coupled with their underlying materialistic-rationalistic generation philosophy make them attractive candidates for automation (Cheylan et al. 1997; Tainz and Heitmann 2005) and have inspired the work of others (Klippel 2004; Laurini et al. 2009).

Fig. 10.8

Hand drawn chorematic diagram (top left) derived from the more detailed

Their envisaged use is in (1) overview, and interaction with, geographic data (Cheylan et al. 1997; Laurini et al. 2009; Reimer and Meulemans 2011), (2) during the consensus building phase in time-critical situations, such as disaster management (Reimer 2010), and (3) as a way of conveying spatial uncertainty—avoiding the illusion of accuracy that often arises from digital products. Because of the rich symbology and scope of themes covered, chorematic diagrams are an attractive means of generating knowledge about the schematisation process.

10.7.1 Knowledge Engineering

Chorematic diagrams are much more varied in their design as compared with other types of schematised maps. They typically employ network-forming lines and simple point symbols as well as dynamic encodings (e.g. the use of arrows). A variety of generalisation techniques are used. In the model stage, just a few entities are selected—often chorematic maps are monothematic. Entities are often simplified by collapsing the base shape of the region into a simple form, such as a rectangle, a circle or a hexagon (e.g. Table 10.1-geodesign). Data are re-classified, and regions amalgamated.

In general, chorematic diagrams do not show quantitative information and succinctly always rely on model generalisation techniques to deliver the reclassification of data. The most striking visual difference to non-schematised thematic maps is the absence of a proper base-map layer in many instances. The base map information is schematised (via collapse, smoothing, geometric stylisation or caricature), thereby forcing similar schematisation on the thematic layer, effectively fusing both. These symbolisation issues alone warrant a differentiation into different categories or classes of chorematic diagrams:

• Symmetric models: the base shape of the region of interest is collapsed into a basically undirected simple form, such as a rectangle, a circle or a hexagon (e.g. Fig. 10.2). Very sparse thematic information, often monothematic.

• Asymmetric models: the base shape is smoothed, geometrically stylised and possibly caricatured into a low-complexity model (5–7 vertices or control points). Very sparse thematic information, often monothematic.

• Synthetic models (symmetric/asymmetric): Usually the synopsis of several preceding monothematic models, geometrically they tend to mirror the preceding models leading up to the synthetic one. They contain synthesised resultant layers that are often emphasised.

• Chorematic maps: More complex (8–17 vertices or control points) irregular polygons are used as base shapes. The polygons are depicted in a manner that allows unambiguous identification to a person familiar with the original shape. Often used as a synopsis of a non-schematised thematic map.

• Synthetic chorematic map: Used and constructed analogous to synthetic models, synthetic chorematic maps combine geographic phenomena on a base map following the definition of chorematic maps stated above. Their content and their cartographic complexity approaches that of non-schematised thematic maps.

Information that conveys the geographic region is simplified up to the point at which it is still recognisable (e.g. Fig. 10.8). Ensuring its recognition requires us to model and retain its characteristic points (the minimum-$\varepsilon$ Problem), particularly given that it might be represented by only a handful of points (Reimer and Meulemans 2011). Succinctly, geographic recognisability cannot always be reached without ancilliary data that models the pertinent geographic context. Research to date has concentrated on territorial outlines for countries, continents and provinces and their subdivisions. Empirical observation suggests retention of significant estuaries (defined by identifying the most land-inward part of an estuary as a characteristic point (e.g. Fig. 10.9)).

Fig. 10.9

Simplification whilst preserving characteristic points

Vertices that are adjacent to administrative boundaries of at least two entities and a sea area bear special topological and conceptual relevance, albeit they might not be geometrically important within the polygon itself (for example the red dot in Fig. 10.9). This requires us to explicitly model points that serve more than one entity (i.e. having degree greater than two). In other words we cannot treat the coastal boundary in isolation of other features connected to it, including objects close to it such as towns and cities.

10.7.2 Modelling Generalisation According to Complexity

Any attempt at automated schematisation needs to be governed by the pairing of desired output complexity and generalisation operators. Generating the desired output complexity/design rule pairing from an input task can be interpreted as a function of the form:

$$ f\left( t \right) = \mathop \sum \limits_{i = 1}^{n} \left( {W_{i} s_{i} } \right) $$

with $s \in S,\;W_{i} \in \left[ {0,1} \right]$ and $W_{i} + W_{j} = 1,$ where $W_{i }$ denotes the weight attributed to $s_{i}$, the chorematic class from the set of all classes $S$ from an input task $t$. Currently there are available automated methods that model this function, so we treat it as a black box, i.e. we presuppose this decision has been made a priori. The degree to which we must apply these techniques depends largely on the complexity of the underlying data and the number of objects we wish to visualise. The classification and complexity measures that result from investigations into chorematic diagrams have the advantage of allowing us to transform the black-box problem into a matching problem.

Let $T$ be the set of tasks and $S$ be the set of chorematic diagram classes. Then the matching $m\!:T \times S \to {\mathbb{B}}$ is a Boolean function that decides whether a chorematic class in $S$ matches the given task in $T$. The set $M_{S} \left( t \right)\!:T \to {\mathcal{P}}(S)$ gives for any task $t$ in $T$ the subset of $S$ that matches $t$. That is,

$$ M_{S} (t) = \left\{ {s|s \in S{\wedge}\,m\,(t,s)} \right\} $$

Such a matching from task to the minimally allowable chorematic diagram classes expressed as $\sup \{ f\left( s \right)\!:s \in S\}$ seems more tractable than a possibly AI-complete black-box function of the general case. Instead of the complete function $f\left( t \right)$, we only need to know the minimum required information for a given task to select from the known and well-described set of chorematic diagram classes.

Assuming we are given a task-derived chorematic diagram class and a layer hierarchy derived from datasets associated with the task, we can envisage the compilation stages as: the reduction in complexity of each layer, the application of various design rules, and their evaluation (Fig. 10.10).

Fig. 10.10

Modelling the design of chorematic maps

Depending on the outcome of the evaluation, the preceding step needs to be repeated or adjusted. The layers are hierarchically inserted into the first layer (always the territorial outline) via a “mapping” utilising anchor points that preserve desirable topological relations (Saalfeld 2001). This hierarchical model mimics a process often used in manual chorematic diagram creation, in which layers are created and fused to the schematised basemap with different design principles applied to different layers.

The step of complexity reduction is crucial to constraining the design. As with schematisation in general the most common forms of complexity reduction are similar to strong reduction of detail (e.g. amalgamation, elimination and synthesis). The respective upper bound is the summed complexity expressed in OLLpA. Existing chorematic diagrams have OLLpA values in the 0.2–0.4 Bt range, depending on type (which compares with non-schematised thematic or topographic maps which typically have a value of 1 and above or transport network schematic maps with values below 0.1 Bt).

Such a strategy allows a divide and conquer approach to these diverse and varied schematic components. Compositionally we might have a polygonal outline showing a high edge parallelism with a subdivision internally smoothed with cubic Bezier curves and a simplified geometrically stylised network on top. Once a design rule is correctly identified and a measure suitable for evaluation has been found the step can be transformed into an optimisation problem. To date, this has been achieved for:

• smoothed polygonal outlines using simulated annealing and edge parallelism as evaluation measure (Reimer and Meulemans 2011)

• smoothed subdivisions using cubic Bezier curves for benign input (Reimer and Volk 2012)

• smoothed outlines and subdivisions using cubic Bezier curves (van Goethem et al. 2013) (Fig. 10.11b)

  Fig. 10.11

  

  Different ways of representing disputed land claims in Antarctica (van Goethem et al. 2013)

• geometrically stylised outlines and subdivisions using circular arcs (van Goethem et al. 2013) (Fig. 10.11c).

Other techniques can then be applied. For example network schematisation (Case study I) can be directly applied to achieve geometric network stylisation after the target complexity and anchor points have been completed. Not all possible design rules have yet been successfully replicated however and this remains a rich area of research.

10.7.3 Future Challenges

Chorematic diagrams make use of a large number of schematisation forms. As with many map generalisation tasks, the challenge is in integration of design rules, and the identification of stopping conditions in their application. The encyclopedic as well as procedural and modelling knowledge gained via investigating chorematic diagrams is considered beneficial for similar tasks in other schematisation efforts. The biggest open problem remains one of matching the task requirement to the selection of entities, and their subsequent analysis sufficient to determine the mix and degree of application of generalisation methods. This problem is common to automation in thematic cartography, more broadly.

10.8 Case Study III: Schematised Maps for Multi Modal Travel

• William Mackaness 

1. School of GeoSciences, The University of Edinburgh, Edinburgh, UK

   William Mackaness

Many different solutions exist that seek to help us navigate across cities and utilise public transport. Often schematised maps are part of that solution (e.g. Case study I; Hochmair 2009; Merrick and Gudmundsson 2007). Anything deemed not relevant to the task is omitted, and the geometry simplified to reduce the cognitive load of the user since the emphasis is one of connectivity between points (Anand et al. 2006). This is not the complete solution however, since travel using public transport requires the user to operate at different geographical scales. When in a station they require maps that direct them along concourses, through ticket barriers, to a particular platform, and bus. But once on the move, synoptic information that shows time or distance is all that is required to monitor progress. However, once at the destination, more detailed information is again required that enables the pedestrian to exit the bus station, and continue their journey. In summary, the task requires ‘connected’ information but at varying levels of detail. For Fig. 10.7a, for example, what is additionally required are more detailed elements that would enable the pedestrian to continue their journey once they have emerged from the metro. We argue that a more complete solution would be one that delivers both the ‘architectural’ scale (Quigley 2001), connected to the more synoptic (Hile et al. 2009). Artistically this idea is captured in the drawings of Escher (Fig. 10.12). It is not simply the casting of a fisheye lens over a particular entity, but more of a ‘semantic zoom’ in which space is created in order to reveal the detail of different, albeit connected, entities.

Fig. 10.12

Connecting the detailed with the more synoptic (M. C. Escher)

10.8.1 Hierarchical Graphs and Event Horizons

The idea that all things geographical are in some way connected, can be schematically represented as a hierarchical “compound” graph. A hierarchical compound graph consists of an ‘inclusion tree’ that makes explicit a set of partonomic and taxonomic relationships that exist amongst a set of entities. Such a tree reflects a multi scaled perspective, that each entity is constituted by the finer scale entities beneath it in the tree (Fig. 10.13).

Fig. 10.13

The most granular, constituted by the most detailed

Metaphorically we can use this construct as a means of selecting entities for schematic or topographic display at a particular scale, by taking a slice through the tree at a specific level. Quigley (2001) describes these slices as an ‘event horizon’—the formal definition of an event horizon being a manifold through a multi hierarchical graph that represents multiple inter-related hierarchical compound graphs. Any given event horizon can be used as a means of selecting entities for a specific map task—thus creating a ‘visual précis’—maps that represents an abridged subset of the graph. In Fig. 10.13 the event horizons are straight horizontal lines but Quigley argued that the event horizon could be ‘deformed’, so as to specifically exclude some entities, AND include other entities, which were themselves combined with entities from different scales (or levels in the tree). In this way the visual précis could encompass both a local- and a global-context (Fig. 10.14).

Fig. 10.14

The event horizon cuts across the hierarchical structure, essentially enabling the mixing of geographic information across different ‘conceptual cusps’

This event horizon gives us synoptic, global content, AND the detailed, local content. In the example of the user commuting by public transport, the detailed more local content is needed at the start and the destination points, where the pedestrian requires architectural detail in order to navigate back to the outside world.

Such hierarchical structures can be formulated in many ways—by spatial proximity, or partonomically—whichever fits best with our conceptual views of the world (Benslimane et al. 2003). Traditionally GIS and cartographic databases are not constituted in these partonomic forms, though a number of techniques have been developed to automatically derive such functional perspectives (Chaudhry et al. 2009).

10.8.2 Implementation

The efficacy of these ideas were explored through implementation (Mackaness et al. 2011) by bringing together various datasets combined with open source software (uDIG http://udig.refractions.net/). The data came from Ordnance Survey and Open Street Map and covered the city of Edinburgh. A journey planning algorithm was implemented on top of bus route data.

The graph database technology neo4j (http://neo4j.org/) was used to facilitate the creation of a pedestrian/public transport network. Neo4j is a flexible graph network database, supporting storage and manipulation of entities, properties and multiple relationships between entities. It was chosen because it is ideal for making explicit the relationship between different representations of concepts. In the context of journey planning, it enables us to chain together the components that make up the journey—the architectural and street level detail, with the more general and synoptic. It also enables us to model event horizons to extract those entities and their connections specific to the given task.

The link between task and both cartographic selection and symbolisation was formalised as a set of rules using drools (http://www.jboss.org/drools). The rule engine governed (1) selection of entities together with the associated contextualising information; (2) the display of text associated with any change in the task; (3) varying levels of detail within differing buffered regions; (4) colour and symbolisation. Figure 10.15 shows how the connected components enabled the generation of different output. Figure 10.16 shows two example outputs generated using rules governing the selection of navigational cues along the route, and the level of detail associated with places of interchange between different modes of transport.

Fig. 10.15

Combining neo4j, route planner, and drools to select and symbolise differing map content

Fig. 10.16

a Example output, for part of Edinburgh, showing navigational cues associated with the walking task and more schematised information along the bus route; b alternate output from the model providing greater levels of detail at points of interchange, and a few nearby navigational cues along the route of the bus

10.8.3 Conclusions

These ideas and their implementation have focused on structures to support the selection of map content according to sub tasks within a multi modal journey. The complimentary nature of visualising geographic information in topographic and schematic form (e.g. Reimer and Meulemans 2011) has been demonstrated. The ambition of future work is to (1) model and populate multi hierarchical graphs, such that event horizons can be used to select content according to differing tasks; (2) to further develop existing visualisation techniques to support automated topographic and schematic mapping, and (3) build on existing techniques for smoothly transitioning between these complimentary but very different styles of visualisation.

10.9 Conclusions and Challenges

Schematised maps require the ‘strong’ application of map generalisation techniques. Different from the challenges of generalising topographic maps, their goal is one of minimum effort in comprehension, seeking to support very specific tasks or messages. They are maps that are far less constrained by the need to correctly convey locational information. In some cases their ambition is to transcend ‘conceptual cusps’ as they seek to represent information at much smaller scales. Such mapping points to the need for modelling complexity, and pattern aware generalisation techniques, capable of understanding the behaviour of the entity in order to determine how best to represent it. This is a topic for which many research questions remain.