Introduction

In dynamic maps, spatio-temporal changes and spatial processes are communicated using animated transitions between different map states (Dransch 2001; Battersby and Goldsberry 2010; Harrower 2001). The transitions are often referred to as morphs, and they are used to support the user in detecting important visual changes that occur during the scene transition.

While the animation can support the detection of changes in the maps, they also add complexity to the visualization, which in extreme cases may cause a cognitive overload for the user, thus limiting the information the user processes (Morrison 2000). Thus, animated maps should be generalized to the most important information to simplify the visualization (Harrower 2003).

Schematic mapping is a cartographic concept that deals with reducing the visual complexity of maps. In schematized maps, a simple and quick-to-understand visualization over a geometrically accurate representation of the features is favored. In this work, we present a method for combining dynamic and schematic maps by generating a morph between two schematized input polylines. Our approach is designed specifically for polylines in which the orientation of each segment is limited to a prescribed set of orientations. One example of such a schematization is octilinear polylines, where all segments are horizontal, vertical, or diagonal. For instance, this type of schematization is widely applied to maps of metro networks (Wu et al. 2020).

Fig. 1
figure 1

Our result for a morph between two schematic isolines (Animated versions for all figures in this article can be found online at https://www.geoinfo.uni-bonn.de/morphing). All polylines are schematic, self-intersection-free, and contained in the morph region (gray)

Full size image
Fig. 2
figure 2

Our result for a morph between two layouts of a schematic transit map. Input layouts are adapted from the Focus+Context Metro Map approach (Wang and Chi 2011)

Full size image

The schematization should be preserved during the morph to reduce the complexity of the animation. Phrased differently, the orientation of the segments of the intermediate polylines that appear in each frame of the animation should be restricted to the same set of orientations as the input polylines. In the case of octilinear input polylines, all intermediate polylines are also octilinear. The morph is schematized by restricting polyline segments to move parallelly without changing orientation. Moreover, we ensure that every segment moves at its own, constant velocity during the morph, further reducing the visual complexity. An example is shown in Fig. 1.

This article proposes an efficient algorithm for morphing schematic input polylines. Specifically, our algorithm produces meaningful morphs for real-world applications by requiring that the morph stays between the input polylines. We show that our algorithm can easily be extended to morph between polygons and between inputs of varying schematization types, i.e., different sets of orientations. The usefulness of the morphs is evaluated for two types of thematic maps, both of which are related to urban mobility.

The first one is isochrone maps, where travel times are displayed by isochrones that enclose the region reachable from a given starting position within a given travel time. We use our morphing algorithm on isochrones to visualize different cycling routing profiles. To this end, we broaden the definition of isochrones to lines containing all points that can be reached with equal effort from a given origin. Figure 1 displays an example morph generated for two routing profiles that reach differently far in varying directions.

The second example is transit network maps, which are well-known for their schematic nature. Specifically, we look at the Focus+Context method developed by Wang and Chi (2011). In their work, the authors generate different transit network layouts based on the selected route. We use our morphing algorithm to animate the transition between these layouts. Figure 2 displays an example morph generated for two transit network layouts for the city of Stockholm.

To summarize our contribution, we present an efficient algorithm that, for two schematic polylines, yields a morph such that it has four favorable properties: (1) it maintains the schematization of the input features, (2) it is self-intersection-free, (3) it is self-contained, and (4) it has constant velocity. To the best of our knowledge, this is the first morphing algorithm that is designed for schematic inputs under challenging constraints such as timing, simplicity, and topology. Alongside this article, the implementation is published as open-source code. It can be accessed at https://gitlab.igg.uni-bonn.de/rukemn/traveltimemaps. Moreover, animated versions for all figures in this article can be found online at https://www.geoinfo.uni-bonn.de/morphing.

Related Work

The concept of morphing was first introduced in the computer graphics community to warp one image into another. In this context, two main methodologies emerged: pixel blending and shape warping. In pixel blending, the pixel values of the first image are gradually shifted toward the second image (Rahman et al. 2007; Kekre et al. 2011). As intermediate states generated by this method show gray values or colors not in the original image, this method is unsuitable for thematic maps with discrete color scales. Nonetheless, Lin and Gong (2018) present an approach similar to pixel blending based on cellular automata suitable for thematic maps.

Shape Warping

In thematic maps, two-dimensional shape warping, where one shape is transformed smoothly into another, is relevant. For the morphing of polygons, Surazksky and Gotsman (Surazhsky and Gotsman 2001a; Gotsman and Surazhsky 2001; Surazhsky and Gotsman 2001b) use compatible triangulations to guarantee that intermediate polygons are self-intersection-free. However, this method tends to produce long vertex traces. As an alternative, a morphing approach based on Hausdorff middles has been presented (van Kreveld et al. 2022). The Hausdorff middle of two shapes is a set that minimizes the maximum Hausdorff distance between them. The authors generate a morph by recursively computing the Hausdorff middle of the two input shapes. A drawback of this approach is that the Hausdorff middle of two polygons is not necessarily a polygon itself. Li et al. (2018) compute a morphing in the frequency space by first applying a Fourier transform on the input data and then computing an intermediate function in the Fourier space.

Another approach to shape warping is by modeling it as a two-step process. First, correspondences between the points of the shapes are established. Secondly, the movement between corresponding points is specified. By using appropriate correspondences, the change during the morph can be optimized. Early works that adopt this method use linear point paths (Sederberg and Greenwood 1992). A problem with this approach is that it can lead to self-intersections in the intermediate shapes. For the morph of two non-intersecting, simple polylines F and G with n vertices, the method of Efrat et al. (2001) guarantees that all intermediate polylines are self-intersection-free by using shortest paths that avoid the input polylines for the point movement. In several publications, improvements of this approach are proposed, resulting in a running time of \(\mathcal {O}(n^2)\) for an optimal solution (Bespamyatnikh 2002) and a running time of \(\mathcal {O}(n)\) for a solution with an approximation factor of two (Bespamyatnikh 2003; Bereg 2005).

Polyline Correspondence

Much attention is given to the correspondence between the two polylines F and G. Most commonly, the correspondence is modeled by two continuous, monotone parameterizations \(\Phi :[0,1] \rightarrow F\) and \(\Gamma :[0,1] \rightarrow G\). For each \(u \in [0,1]\), the point \(\Phi (u)\) on the source polyline corresponds to point \(\Gamma (u)\) on the target polyline. An important feature for finding the correspondence is the similarity of polylines. Similar sections on the two polylines should also correspond in the morph. One of the earliest similarity measures between curves is the Fréchet distance (Alt and Godau 1995). Efrat et al. (2002) introduce two Fréchet-like similarity measures designed explicitly for polyline morphing, the geodesic width, i.e., the length of the maximum point movement, and the link width, i.e., the maximum number of links of the geodesic point movements. Buchin et al. (2019) introduce a method to compute locally correct Fréchet matchings, where matchings for every two subpolylines are valid Fréchet matchings again. Liu et al. (2004) extract perceptual feature points of the input shapes and perform the correspondence based on properties of the local neighborhood of each feature point.

Morphing and Cognition

The utility of animation in human perception has been extensively explored within cognitive science. Archambault and Purchase (2016) examined how animations enhance graph drawings, revealing that animation significantly improves task performance, particularly in scenarios with low stability. This finding supports earlier research by Tversky et al. (2002). Additionally, Sedig et al. (2005) compared different design interfaces for transitional processes and found that animations are the most effective to aid users in constructing cognitive maps.

Another research area focuses on how intermediate shapes during a morph are perceived (Panis et al. 2008). Several studies have identified discrimination thresholds, which are points within the morph space where differences in shape become noticeable (Destler et al. 2019; Hartendorp et al. 2010). Godfrey and Mackaness (2017) applied this concept to geographical information, investigating the maximum extent of map distortions that still permit effective use of the maps.

Morphing for Map Comparison

The comparison of maps is an important topic in cartography (Visser and de Nijs 2006; Lobo et al. 2015) that is frequently used to analyze urban mobility (Polisciuc et al. 2013; Dewulf et al. 2015). Gortana et al. (2014) present a web application for visually exploring urban mobility patterns based on isochrones. In the outlook, the authors highlight the need for smooth transitions to improve the exploration. An important concept in this context is the cognitive or mental map, which reflects the users’ perception of an environment (Kitchin 1994). Preserving the mental map has been shown to improve the user’s orientation (Archambault and Purchase 2013). Previous studies show that animations can help to build and preserve the mental map (Bederson and Boltman 1999; Diehl et al. 2001).

Morphing in Map Generalization

In map generalization, morphing is used to create a smooth transition between different zoom levels (van Kreveld 2001; Cecconi et al. 2002; Pantazis et al. 2009; Kada et al. 2015; Li et al. 2017a; Gao et al. 2020). Nöllenburg et al. (2008) present a method to detect characteristic points of polylines, which are then used as input for the correspondence problem. They present a dynamic programming approach for computing the correspondence and a heuristic method to avoid self-intersections in the intermediate states. Their approach is similar to Dynamic Time Warping, which has also been applied to the continuous generalization of linear features (Li and Mao 2023). Similarly, Deng and Peng (2015) match polylines based on the similarity of the bend structures to generate morphs between features of different scales. Sester and Brenner (2005) consider the generalization of building footprints and highlight the need to preserve the object regularities. Based on a given footprint, the authors generate simplified variants of the footprint while simultaneously generating a morph between the shapes. Their rule-based approach guarantees a rectilinear simplification of building footprints. Similarly, Li et al. (2017b) present an angle-preserving morphing approach for building footprints by establishing the correspondence in the turning-angle function feature space. Similar to the previous approach, their method can only simplify the input feature. van Oosterom and Meijers (2014) introduce the space-scale cube (SSC), a data structure for the continuous generalization of geographic features. More recently, Peng et al. (2023) use a SSC to generate a smooth zoom animation based on merging area objects.

Schematization

In cartography, schematization highlights specific aspects of a map while deemphasizing others (Klippel et al. 2005; Roberts 2023). Schematization aims to reduce the complexity of the map (Meulemans 2014; Ti et al. 2023) and is often used in combination with geographic base maps (Böttger et al. 2008). This article adopts the concept of C-oriented schematization. The edges of a C-oriented shape are restricted to a set C of edge orientations. Two popular variants of C-oriented schematization are rectilinear shapes, where all edges are horizontal or vertical, and octilinear shapes, where diagonal edges are allowed next to the rectilinear directions. Delling et al. (2010) apply C-oriented schematization to create sketches of routes. The goal is to create a schematized variant of the input path that retains key properties, such as being intersection-free and preserving the orthogonal order, i.e., the relative location of consecutive locations. Similarly, Speckmann and Verbeek (2018) present algorithms for finding C-oriented schematizations for input paths that preserve the relationship of the path to given obstacles. Early works for the schematization of polygonal shapes included O-hulls, a schematized convex hull of the polygon (Fink and Wood 2004). Cicerone and Cermignani (2012) present a heuristic for rectilinear and octilinear schematization of polygons. Instead of considering single polygons, some methods deal with the schematization of polygonal subdivisions that preserve the topology of neighboring polygons (Meulemans et al. 2010; Buchin et al. 2016). Bonerath et al. (2019) present a data structure that supports time-window queries on large sets of points with time stamps. The result of a query is a schematic polygonal representation of the set of all points within the queried time window. Thus, C-oriented schematization has been applied in all three vector data domains: point, line, and area.

Transit Maps A well-known application domain of schematization is that of transit map layouts (Jenny 2006; Wu et al. 2020), which, in their schematized form, are often referred to as metro maps. Much research was done in this context on the automatic schematization of networks (Li and Dong 2010; Nöllenburg and Wolff 2011; van Dijk and Lutz 2018; Bast et al. 2020; Brosi and Bast 2024). Li (2015) formulates four general principles for the schematization of networks: preservation of the topological relationship, preservation of the main structure of a line network, relativity in position, and relativity in length. Based on these principles, Lan et al. (2019) present a mixed-integer approach for the construction of octilinear metro maps. Taking it a step further, Nöllenburg and Terziadis (2024) present a method for the automatic generation of C-oriented metro maps, which dynamically selects the set C from the input data.

Wayfinding Wayfinding is another domain where schematization has frequently been applied (Casakin 2004; Meilinger et al. 2007; Speckmann and Verbeek 2018; Galvão et al. 2021). Galvão et al. (2023) present an approach for schematizing a given route and the surrounding transportation network simultaneously. Wang and Chi (2011) present a focus+context approach that allows highlighting a specific route in a metro network by deforming the network such that the selected route is enlarged. One application domain for our morphing scheme could be the transition from the original metro map to the metro map with a highlighted route.

Although previous publications have given considerable attention to polyline morphing and schematization, none of the existing morphing algorithms maintain the schematic properties during animation.

Fig. 3
figure 3

The morph region R is defined by the two input polylines F and G along with the geodesic paths S and T connecting their endpoints. In the standard case (a), the morph region is a simple polygon, but depending on the configuration, it is a weakly connected polygon (b) possibly even featuring dangling outgrowths (c)

Full size image

Base Case: Morphing Simple Polylines

This section introduces the notation used throughout the article and establishes the algorithmic problem we are solving. Then, an algorithm for solving the problem for the base case for morphing two non-intersecting polylines is presented. In the “General Case” section, we introduce simple extensions to the algorithm to make it applicable to closed rings, i.e., polyline outlines, that may also intersect.

Notation

A polyline L is represented as a sequence of points \(\langle l_0, l_1, \dots , l_k \rangle \), which are the vertices of L. A straight-line segment connecting two consecutive vertices in L is called a segment of L. We require that L is C-oriented, meaning that the orientation of every segment of L stems from a predefined set C of orientations. If L has no self-intersections, we call it simple. We denote the subpolyline of L that starts at \(l_i\) and ends at \(l_j\) with \(i \le j \le k\) as \(L_i^j\). Further, the length of L, i.e., the sum of its segments’ lengths, is denoted as \(\ell (L)\). We call the shortest path from a point s to a point t avoiding a given set of obstacles \(\mathcal {O}\) the geodesic path \(\mathcal {G}_\mathcal {O}(s,t)\).

Input

As input, we take two simple schematic polylines \(F=\langle f_1, \dots , f_n \rangle \) and \(G = \langle g_1, \dots , g_m \rangle \). We call F the source and G the target. In a basic setting, we assume (i) that F and G do not cross each other and (ii) that \(S = \mathcal {G}_{\{F, G\}}(f_1, g_1)\) and \(T = \mathcal {G}_{\{F, G\}}(f_n, g_m)\), i.e., the geodesic paths connecting the input polylines’ endpoints while not crossing them, do not intersect. As a result, the polylines F, T, G, and S can be concatenated to form the outline of a simply connected region (Tang 2007). We call this region the morph region and denote it as R. Figure 3 illustrates the definition of the morph region and provides examples of its construction for different configurations that may arise that fulfill assumptions (i) and (ii). In the “General Case” section, we explain simple preprocessing steps, allowing us to deal with inputs where assumptions (i) and (ii) do not hold.

Problem

We aim to find a function M(t) that returns for every timestamp \(t \in [0,1]\) a simple schematic polyline such that \(M(0)=F\) and \(M(1)=G\). We impose the natural requirement that M is continuous. Further, for every \(t \in [0,1]\), the polyline M(t) must fulfill the following properties:

  1. (1)

    Schematic: the segments of M(t) are restricted to the set C of directions that the segments of F and G are restricted to.

  2. (2)

    Self-intersection-free: M(t) is self-intersection free.

  3. (3)

    Self-contained: M(t) is within the morph region R.

  4. (4)

    Constant velocity: the velocity of a moving segment in M(t) is constant.

We call M a morph between its source F and target G. The requirements for M reduce the visual complexity of the morph.

Similar to previous work in polyline morphing, we split the morphing into two problems. At first, we find a correspondence between every point on F to a point on G. We call this the correspondence problem. The second problem is to specify the timing of the movement of points on F to their corresponding points on G. We call this the timing problem. The following gives an overview of our solution to these two problems.

Correspondence

We consider the correspondence as a discrete problem by finding the correspondences of vertices between the two polylines. It is sufficient to model the correspondences for all vertices (corners) of F and G. We reason this because we are dealing with schematized input polylines. Schematization aims to reduce the complexity of the non-schematized feature while preserving its characteristic properties. Therefore, we can assume that the input polylines’ vertices capture the features’ characteristics.

We call the path a point \(f \in F\) takes during the animation to get to point \(g \in G\) the trace of f and g. The simplest way of defining the traces is by using straight-line movements with uniform motion, i.e., the points have constant speed along their trace. Although this approach is established, it can lead to unwanted self-intersections in M. This problem can be avoided by using geodesic paths inside the morph region R as traces (Efrat et al. 2001). Therefore, we use such geodesic paths as traces, making them uniquely defined by the vertex correspondences.

Vertex-Based Correspondence

We model the vertex-based correspondence of the two polylines with a sequence \(\Pi = (\pi _1, \dots , \pi _{p+1}) \subseteq F \times G\) of vertex correspondences. A vertex correspondence is a pair \(\pi = (f, g)\) with \(f \in F\) and \(g \in G\), denoting that vertex f corresponds to vertex g. We call f the source and g the target of the correspondence \(\pi \). Let the trace \(\textrm{tr}(\pi )\) of a vertex correspondence \(\pi = (f,g)\) be the geodesic path from f to g inside the morph region R. We call \(\Pi \) a schematic polyline correspondence if it fullfills:

  • (R1) Monotone: For the correspondences \(\pi '=(f_i, g_j)\) and \(\pi ''=(f_k, g_l)\) in the sequence \(\Pi \) with \(i < k\) it holds that \(j \le l\).

  • (R2) Complete: All vertices of F and G are part of at least one vertex correspondence in \(\Pi \).

  • (R3) Orientation-Preserving: If two consecutive vertex correspondences span a segment on both input polylines, i.e., \(\pi _k = (f_i, g_j), \pi _{k+1} = (f_{i+1}, g_{j+1}) \in \Pi \), then these segments \(f_i^{i+1}\) of F and \(g_j^{j+1}\) of G have the same direction.

Figure 4 gives an example of a schematic polyline corresp-ondence.

Fig. 4
figure 4

A correspondence between polylines F and G fulfilling Requirements (R1) – (R3) and thus being a schematic polyline correspondence. Every vertex of F and G is part of at least one vertex correspondence (black arrows)

Full size image

Operations

Let an operation o be a pair \((\pi _i, \pi _{i+1})\) of two consecutive vertex correspondences in \(\Pi \). Requirements (R1) and (R2) imply that given the vertex correspondence \(\pi _i = (f_j, g_k) \in \Pi \), there are at most three valid candidates for the succeeding vertex correspondence \(\pi _{i+1} \in \Pi \); see Fig. 5:

\(\pi _{i+1} = (f_{r+1}, g_{c+1})\):

resulting in a segment-to-segment correspondence of \(f_r^{r+1}\) to \(g_c^{c+1}\). We call the pair \((\pi _i, \pi _{i+1})\) a Match operation.

\(\pi _{i+1} = (f_{r}, g_{c+1})\):

resulting in a vertex-to-segment correspondence of \(f_r\) to \(g_c^{c+1}\). A new segment appears during the morph. We call the pair \((\pi _i, \pi _{i+1})\) an Insert operation.

\(\pi _{i+1} = (f_{r+1}, g_{c})\):

resulting in a segment-to-vertex correspondence of \(f_r^{r+1}\) to \(g_c\). The segment disappears during the morph. We call the pair \((\pi _i, \pi _{i+1})\) a Delete operation.

Fig. 5
figure 5

The operations resulting from the correspondence displayed in Fig. 4. Segments of equal orientation can form a Match (blue). Otherwise, segments either form an Insert (green) or a Delete (red). The red lines indicate vertex traces. The dash-dotted traces are displaced to allow distinguishing all operations

Full size image

We denote the first vertex correspondence in an operation o with \(\pi _\textrm{L}(o)\) and the second one with \(\pi _\textrm{R}(o)\). Analogously, \(\textrm{tr}_\textrm{L}(o)\) and \(\textrm{tr}_\textrm{R}(o)\) are the traces of these vertex correspondences. An operation describes the correspondence between a vertex or segment on F to a vertex or segment on G. We denote the vertex or segment on F as \(\textrm{source}(o)\) and the vertex or segment of G as \(\textrm{target}(o)\).

Requirement (R3) enforces that Match operations are only valid between segments of equal orientation, i.e., both polyline segments that are part of the Match have the same direction. We denote this direction with \(\textrm{dir}(o)\). During the morph, the \(\textrm{source}(o)\) for every segment \(o \in \Omega \) will be transitioned parallelly toward \(\textrm{target}(o)\). Thus, every intermediate polyline has the same direction \(\textrm{dir}(o)\) as the input polylines within the operation.

Fig. 6
figure 6

Illustration of correspondence properties by taking the example of an a Delete and b Match operation. The blue lines are the vertex traces between \(s_1\) and \(s_2\), which avoid crossing any other parts of the input polylines not involved in the correspondence (red). These traces induce the gray subregion of the morph region. Within this subregion, the segment (black) is translated parallelly. That way, it is ensured that the morph is schematic, self-intersection-free, and contained within the morph region (i.e., self-contained)

Full size image

Properties of Schematic Polyline Correspondences

Due to the monotonicity of the correspondence, the individual vertex traces, defined as geodesic paths between corresponding vertices, do not cross each other. Furthermore, a geodesic path is inherently self-intersection-free. Consequently, the vertex traces partition the morph region R into distinct subregions, with each subregion corresponding to an operation, for example, Fig. 5. This ensures three crucial properties. Firstly, each operation involves the movement of a single segment, which can proceed in parallel to its original position, thereby preserving the schematic representation of the polylines throughout the transition, illustrated in Fig. 6. Secondly, a single segment cannot have self-intersection; thus, each operation transition is self-intersection-free. Thirdly, as the subregions defined by the vertex traces are a tessellation of the morph region, they are mutually disjoint. Since each segment remains confined within its operations’ subregion, no two segments of different operations can interact during the morph. Put together, these three properties guarantee that the correspondence generated by our method results in a morph that remains schematic, self-intersection-free, and contained within the morph region (which we call self-contained).

Optimization

The correspondence needs to be optimized to generate a comprehensive morph animation. Less movement leads to less complex morph animations; thus, we minimize the distance the vertices move during the morph. Hence, we want to solve the following optimization problem:

Problem 3.1

(Optimal Correspondence) Given two simple schematized polylines \(F = (f_1, \dots , f_n)\) and \(G = (g_1, \dots , g_m)\) that do not intersect, find the correspondence \(\Omega = (o_1, \dots , o_p)\) that fulfills Requirements (R1)-(R3) and that minimizes a weighted sum of the vertex traces’ lengths.

Algorithm

In the following, we discuss an efficient algorithm to solve Optimal Correspondence. We are looking for the vertex-based correspondence between the two polylines F and G that minimizes the weighted sum of the vertex traces’ lengths. Nöllenburg et al. (2008) introduced a dynamic programming approach for solving the optimal correspondence for a generic additive cost function c. However, their approach does not guarantee that the generated correspondence results in a schematic morph. That is, Requirement (R3) is not fulfilled. In their algorithm, a dynamic programming table T is used, where every table entry T[r, c] stores the total cost of morphing subpolyline \(f_1^r\) onto \(g_1^c\). The table is filled recursively, starting from the initial solution \(T[0,0] = 0\). Each table entry’s value is the sum of the previous entry and the cost of the applied operation. To solve Problem 3.1, we need to adapt this update step by (a) introducing an appropriate cost function for the operations and (b) guaranteeing that Requirement (R3): Orientation-Preserving is fulfilled.

Operation Costs

The cost of an operation o is defined by the cost function \(c :o \rightarrow \mathbb {R}\). We want to minimize the distance each vertex travels during the morph. Therefore, we consider the sum of the vertex traces’ length per operation as the cost \(c^*\):

$$\begin{aligned} c^*(o)= & \ell \bigl (\textrm{tr}_\textrm{L}(o)\bigr ) + \ell \bigl (\textrm{tr}_\textrm{R}(o)\bigr ). \end{aligned}$$
(1)

Intuitively, an operation spanning a large section of the input polylines should have a higher importance regarding the final correspondence than an operation covering only a tiny part of the polylines. Therefore, we weight the cost with a weighting term w(o) proportional to the length of the covered polyline segments:

$$\begin{aligned} w(o)= & \ell \bigl (\textrm{source}(o)\bigr ) + \ell \bigl (\textrm{target}(o)\bigr ). \end{aligned}$$
(2)

Each segment of the input polylines F and G is part of precisely one operation in \(\Omega \). As a result, it is easy to show that \(\sum _{o \in \Omega } w(o) = \ell (F) + \ell (G)\), which we use as a normalization term \(\eta \). Thus, the final cost \(c_\textrm{opt}\) for an operation is given by:

$$\begin{aligned} c_\textrm{opt}(o)= & \dfrac{w(o)}{\eta } \cdot c^*(o). \end{aligned}$$
(3)

On the one hand, the weighting ensurves that operations in-volving longer sections of the input polylines are more important in the correspondence. The weighting ensures that the cost is independent of the level of discretization of the input.

Fig. 7
figure 7

The morph resulting from the correspondence shown in Fig. 5 is displayed. Depicted are five timesteps of the animation. At \(t=0.50\), the central segment has reached its destination while the others continue moving. Due to the constant velocity constraint, the segments left and right of the stopped segment have the same velocity

Full size image

We can compute T[r][c] for \(r, c > 0\) by using the optimal solution for the subpolylines defined by the three possible operations:

$$\begin{aligned} T[r][c] = \min {\left\{ \begin{array}{ll} T[r-1, c] + c_\textrm{opt}(o_\textrm{D}), & \text {\texttt {Delete}} \\ T[r-1, c-1] + c_\textrm{opt}'(o_\textrm{M}), & \text {\texttt {Match}} \\ T[r, c-1] + c_\textrm{opt}(o_\textrm{I}), & \text {\texttt {Insert}} \end{array}\right. } \end{aligned}$$
(4)

Guaranteeing Schmatization

To guarantee Requirement (R3), the cost function \(c_\textrm{opt}\) introduced in the last section is slightly modified for Match operations. In the case that a Match \(o_\textrm{M}\) is invalid because its source and target have different orientations, infinity is returned:

$$\begin{aligned} c_\textrm{opt}'(o_\textrm{M}) = {\left\{ \begin{array}{ll} c_\textrm{opt}(o_\textrm{M}), & \text {if } \textrm{dir}\bigl (\textrm{source}(o_\textrm{M})\bigr ) = \textrm{dir}\bigl (\textrm{target}(o_\textrm{M})\bigr )\\ \infty , & \text {else.} \end{array}\right. } \end{aligned}$$
(5)

Complexity

The dynamic programming table has size \(n \times m\) where n and m are the numbers of points in F and G, respectively. This results in a running time of \(\mathcal {O}(nm\cdot C)\) with C denoting the time needed to evaluate the cost function \(c_\textrm{opt}\). Precomputing the geodesic paths between the input polylines allows us to have constant evaluation times for \(c_\textrm{opt}\) (i.e., \(C \in \mathcal {O}(1)\)) resulting in a complexity of \(\mathcal {O}(nm)\).

Timing

Until now, we have considered the requirements of having a (1) schematic, (2) self-intersection-free, and (3) self-contained morph. In the timing problem, we consider the requirement for a constant velocity of the moving segments in the morph.

In contrast to the geometric shape of the point movement, the velocity of a point along its trace has yet to be defined. To model this temporal component, we extend the traces for a vertex correspondence from point \(f \in F\) to point \(g \in G\) by a time parameter t. To make the transition as smooth as possible and thus reduce the visual complexity, we require that each segment has a constant velocity in the direction of its normal while it is moving. However, to fulfill the requirement of parallel movement, segments can start and end their movement later than the full morph. Figure 7 shows the timing for the correspondence displayed in Fig. 5. Each operation \(o_i\) (i.e., pair of consecutive vertex correspondences) defines a transition of one segment \(s_i\) from the source to the target polyline. We denote the subpolyline of M between its vertices i and j at time t with \(m_{ij}(t)\).

Requirements

We impose two requirements that influence the timing. First, to preserve the schematization, each polyline segment s can only be moved parallelly during the morph. Secondly, to reduce the visual complexity of the morph, each segment should morph with a constant velocity. More specifically, a segment can start its movement later and end its movement earlier than the full morph. Still, the segment’s velocity in its orthogonal direction is constant during this movement. This means that each segment s has a movement interval \(I_s = [t_\textrm{start}, t_\textrm{end}] \subseteq [0,1]\).

We solve the timing in a two-step process. Firstly, we partition the morph region R into a set of transition cells. In each transition cell, every segment starts and ends its movement simultaneously. Secondly, we determine the starting and ending times of the individual transition cells by setting up and solving a system of linear equations that guarantees temporal consistency between the cells.

Creating Transition Cells

A transition cell c is a subregion of R with the property that all vertex traces passing through the cell are straight lines. This allows us to apply uniform motion to the vertexes inside a single cell. By the intercept theorem, this uniform motion on straight-line traces results in a parallel movement of the transitioning polyline segments. The transition cells of the morph form a tessellation of the morph region R.

Fig. 8
figure 8

Creation of transition cells. Vertex traces (red) that are colinear are displaced for visualization purposes. At bends in the vertex traces, rays (green) are shot parallelly to the operation’s segments. These rays divide the morph region into transition cells (green)

Full size image

By definition, a region will be separated into two transition cells at bends in a vertex trace. Therefore, we iteratively explore all operations in the given correspondence. For every bend in \(\textrm{tr}_\textrm{L}(o_i)\), i.e., the operation’s first trace, the bend is propagated forward through the remaining operations by casting a ray in the operation’s direction \(\textrm{dir}(o_i)\). For every bend in \(\textrm{tr}_\textrm{R}(o_i)\), i.e., the operation’s second trace, the bend is propagated backward through the previous operations by casting a ray in the opposite direction of \(\textrm{dir}(o_i)\). The lines created that way are collected in a set \(\mathcal {L}\) used to split the morph region R into the transition cells. Figure 8 gives an example of a decomposition into transition cells. Lines in \(\mathcal {L}\) are shown in green. They decompose the morph region in four transition cells: \(c_0\), \(c_1\), \(c_2\), and \(c_3\).

Transition Timing

Each transition call c spans a sequence of operations \(O = (o_i, \dots , o_j)\) with \(i \le j\) and has a starting time \(t_\textrm{s}(c)\) and a ending time \(t_\textrm{e}(c)\), with \(0 \le t_\textrm{s}(c) < t_\textrm{e}(c) \le 1\). Thus, a transition cell c describes the morph from \(m_{ij}(t_\textrm{s}(c))\) to \(m_{ij}(t_\textrm{t}(c))\). We call \(m_{ij}(t_\textrm{s}(c))\) the input of the transition call and \(m_{ij}(t_\textrm{t}(c))\) its output. Between \(t_\textrm{s}(c)\) and \(t_\textrm{e}(c)\), all input segments of c move at a constant velocity toward the output segments of c.

Constraints

Some segments move through several transition cells. We call such segments cell-linking. Cell-linking segments impose two constraints on the transition cells’ starting and ending times. Firstly, the segment should not stop at the cell border. Therefore, the ending time of the first cell must be the same as the starting time of the second cell. Take the leftmost segment in Fig. 8 as an example. It starts its movement in \(c_1\) and continues through \(c_3\). Here, \(c_3\) must start its movement when \(c_1\) ends moving. Analogously, \(c_0\) and \(c_1\) as well as \(c_2\) and \(c_3\) are linked. Secondly, segments must have constant velocity throughout the morph, interlinking the transition times of all cells they pass through.

Transtition Cell Graph

We observe that we can arrange the set of transition cells \(C = (c_1, \dots , c_k)\) in a directed graph \(\mathcal {T} = (C, E)\), with the transition cells being the graph’s vertices. Two neighboring transition cells, i.e., transition cells separated by a line \(l \in \mathcal {L}\), are connected by a directed edge \(e \in E\). The direction of the edge e is defined by the vertex correspondences. The morph region R is simple, meaning it has no holes and is connected. Therefore, the transition graph \(\mathcal {T}\) does not contain loops and consists of a single connected component, resulting in a graph with \(|C| = k\) vertices and \(|E| = k-1\) edges.

Computing Cell Starting and Ending Times

We solve the timing using a system of linear equations with the starting and ending times of the cells as unknowns. Thus, each vertex of the transition graph \(\mathcal {T}\) yields two unknowns, resulting in 2k unknowns. Additionally, each edge \(e = (c_i, c_j)\) in \(\mathcal {T}\) imposes two constraints. Firstly, the starting and ending times of \(c_i\) and \(c_j\) must be consistent:

$$\begin{aligned} t_e(c_i) = t_s(c_j) \end{aligned}$$
(6)
Fig. 9
figure 9

Polygons preprocessing. The polygon outlines are cut open at two cut locations (squared vertices). A schematized cut line connecting the cut locations splits the morph region R (gray, slightly buffered to the inside for visualization purposes)

Full size image
Fig. 10
figure 10

For intersecting input polylines, the morph is split into subinstances at the polyline intersections

Full size image
Fig. 11
figure 11

a The intersections of the blue and the red polygon occur in different orders around the polygon outlines (numbers indicate the sequence). b The morph is computed toward the outline \(\partial C\) of the largest component C of the arrangement

Full size image

Secondly, the pair of transition cells are separated by at least one segment \(s_b\) that is part of the output of \(c_i\) and the input of \(c_j\). The orthogonal velocity of \(s_b\) must be the same in both cells. We denote the orthogonal distance the segment \(s_b\) travels inside cell \(c_i\) with \(d_{ib}\). The orthogonal velocity of \(s_b\) in \(c_i\) is given by

$$\begin{aligned} v_b = \frac{d_{ib}}{t_e(c_i)-t_s(c_i)}. \end{aligned}$$
(7)

Thus, the second constraint induced by e is

$$\begin{aligned} \frac{d_{ib}}{t_e(c_i)-t_s(c_i)} = \frac{d_{jb}}{t_e(c_j)-t_s(c_j)} \end{aligned}$$
(8)

To yield a linear constraint in the unknowns, we take the reciprocal of the equation. Further, to improve the numerical properties of our system of linear equations, we normalize the constraint with \(\eta = \min (d_{ib},d_{jb})\):

$$\begin{aligned} \eta \cdot \frac{t_e(c_i)-t_s(c_i)}{d_{ib}} = \eta \cdot \frac{t_e(c_j)-t_s(c_j)}{d_{jb}} \end{aligned}$$
(9)

Introducing a Datum

The system of equations consists of 2k unknowns. Each edge \(e \in E\) yields two linearly independent constraints, resulting in \(2(k-1)\) constraints. As a consequence, we have a rank deficiency of 2. This is because the computed times can be scaled and offset arbitrarily with the current definition. To deal with this, we introduce a datum by fixing the starting and ending times of an arbitrary cell c to \(t_s(c) = 0\) and \(t_e(c) = 1\). After solving the system of linear equations, we rescale all computed times to the interval of [0, 1].

General Case

Until now, we have only considered the base case, in which we assume that (i) our input polylines do not intersect and (ii) the two geodesic paths connecting their endpoints do not intersect. These assumptions on our input do not always hold. Additionally, F and G might form the outlines of polygons. We can apply simple preprocessing steps to fulfill these two requirements in almost all practically relevant situations.

When handling polygon outlines, we divide them at designated cut locations to obtain two polylines. To generate the morph region, we connect these cut locations with a schematized line, referred to as cut line (e.g., using the algorithm by Speckmann and Verbeek 2018), see Fig. 9. If the polygon outlines intersect, one of their intersection points serves as a natural cut location for both outlines, making the computation of the cut line superfluous. Otherwise, a simple approach to selecting the cut locations is by using the pair of vertices between the two polygons closest to each other.

For (i), we split the polylines at their intersection points. If the intersection points occur in the same order along the two polylines, we create one morph subinstance per pair of subpolylines, see Fig. 10. Each subinstance is solved independently. In our experiments with two polylines F and G corresponding to the boundaries of simple polygons, however, we encountered a few examples where the order of the intersection points differed for F and G. We handle this case by computing the intersection of the polygons enclosed by F and G. From the resulting multi-polygon, we select the largest component C. Then, we compute a morph between polyline F and the boundary \(\partial C\) of C and a morph between \(\partial C\) and polyline G. An example of this situation is given in Fig. 11.

The most challenging case is that F and G do not correspond to the boundaries of polygons, and the order of their intersection points differ for F and G. This scenario is displayed in Fig. 12. This case never occurred in our experiments, and we leave it as a challenge for future research. However, we think computing an intermediate polyline and performing the morph in two steps (as in our approach for polygonal rings) is promising.

Finally, Fig. 13 shows an example where (ii) is violated. We can reverse the target polyline for these cases to set up the morph region (Fig. 13b).

Fig. 12
figure 12

Illustration of the only case not (yet) covered by our approach. The input polylines do not form the outline of a polygon, and their intersection points occur in different orders along the two polylines. This case never occurred in our experiments

Full size image

Evaluation

In this section, we evaluate our morphing algorithm. The evaluation can be separated into three main parts. First, we perform a quantitative evaluation of our approach by comparing it to morphs generated with a baseline approach that does not guarantee schematization (Schematic) during the morph or topological correctness (i.e., Self-Intersection-Free and Self-Contained). These baseline methods closely resemble the morph algorithm introduced by Nöllenburg et al. (2008), a state-of-the-art technique for generating morphs in cartography. While there are minor differences, the core principles remain largely the same, enabling a meaningful comparative evaluation against state-of-the-art methods. Specifically, we want to analyze how strongly these constraints influence the optimization function \(c_\textrm{opt}\) of the morph. In the second step, we perform a qualitative analysis by closely examining generated morphs. These first two steps are performed on closed input polylines. In the third step, we apply our algorithm to non-closed polylines, each representing a different level of schematization for the same input feature, to evaluate its effectiveness in the context of continuous generalization.

Fig. 13
figure 13

If the geodesic paths between the source and target (black) cross (a), the target polyline is reversed to create the morph region R (b)

Full size image

Evaluation Instances

For the quantitative evaluation, we use isochrones generated for the cycling network of Bonn, Germany. Specifically, we use isochrones generated for different cyclist routing profiles. For this, we use the routing model introduced by Forsch et al. (2023) to calculate the accessibility for cyclists. In their model, a balance factor \(\alpha \) is introduced that expresses the cyclists’ routing preferences. When applied to the usage of cycleways, an \(\alpha > 0.5\) indicates preference of these designated cycleways while an \(\alpha <0.5\) indicates an avoidance of these paths. For \(\alpha =0.5\) the cyclist is indifferent on the type of path and only minimized the geometric length. Using this routing model, the generated isochrones will display the locations that are reachable within a given maximum amount of effort concerning the routing profile. We generate octilinear isochrones using the visualization component described by Forsch et al. (2021).

We generate isochrones for three different starting locations in Bonn. We apply \(k=6\) different maximum efforts for each starting location for two prevalent routing profiles identified by Forsch et al. (2023): cyclists sticking to shortest paths (CON, \(\alpha =0.45\)) and cyclists wanting to stick to signposted cycleway (PRO, \(\alpha =0.65\)). If the isochrones have holes, we remove them, taking only the outer ring as input to our algorithm. We use these isochrones to generate two sets of morph instances per starting location:

  1. 1.

    Max Effort: For all k maximum efforts, we compute the morph to all larger values of maximum efforts, resulting in \(\frac{(k-1)k}{2}\) instances per routing profile. An isochrone of smaller maximum effort is contained inside an isochrone of larger maximum effort, making the Self-Contained property crucial for interpretation.

  2. 2.

    Routing Profile: For all k maximum efforts, we compute the morph between the two routing profiles. Isochrones in this group often intersect, as one routing profile might reach further than the other in one area but shorter in another.

These two groups result in 21 morph instances per starting location and 63 morph instances. As described in the “Base Case: Morphing Simple Polylines” section, the input polylines are split at intersection points, and a morph is generated individually for each subinstance.

Implementation

To evaluate our approach, we implemented it as a single-threaded Java application. The implementation makes use of two open-source libraries, namely GeoTools (Turton 2008) for handling geographic data and JGraphT (Michail et al. 2020) for the graph structures and algorithms. The implementation, as well as the evaluation instances, are published as open source.Footnote 1 The experiments are executed in a Java 11 Runtime Environment on an AMD Ryzen 7 processor clocked at 2.3 MHz.

Baseline Solution

We want to evaluate the influence of the constraints Schematic, Self-Contained, and Self-Intersection-Free on the optimization criterion of the morph. For this, we define the baseline solution as a solution that does not fulfill these properties. This baseline solution can be generated using the solution to the correspondence problem (“Correspondence” section) with straight-line vertex traces and uniform motion (i.e., constant vertex velocity) along these traces. This approach closely resembles the morphing procedure introduced by Nöllenburg et al. (2008) with slight differences in the applied cost function. Additionally to the baseline solution, we introduce the schematic baseline solution that fulfills the Schematic property. We use straight-line traces as the baseline solution for this, but we use the modified cost function \(c^*_\textrm{opt}\) instead of \(c_\textrm{opt}\). This solution is a trade-off between the baseline solution and our approach when topological correctness is not strictly needed.

Quantitative Evaluation

Splitting the 63 morph instances at the intersection of their input polylines resulted in 226 subinstances. For each subinstance, we generated a morph using the baseline, the schematic baseline, and our approach. Our primary focus is to analyze how much the constraints we induce on the morphing impact the total cost \(c_\textrm{opt}\) of the morph. The results of our quantitative analysis are shown in Table 1. When comparing the schematic baseline to the baseline, the cost only increases by less than \(5\%\). Remember that the difference between \(c^*_\textrm{opt}\) used in the schematic baseline to \(c_\textrm{opt}\) used in the baseline solution is that matches are only allowed between segments of equal orientation in \(c^*_\textrm{opt}\). Thus, this increase is explained by using more Insert and Delete operations instead of Matches. When comparing the schematic baseline to our approach, the increase in the cost is only \(0.5\%\). We conclude that guaranteeing the schematization has the largest influence on the morph cost, while guaranteeing the topological correctness has only a minor effect.

Table 1 Results of the quantitative analysis
Full size table

We need to examine the profit gained to assess whether the increase in the optimization target is reasonable. Table 2 gives an overview of how many subinstances fulfill the properties we require in our approach. By construction, all properties are fulfilled in every instance for our approach. Self-intersections only occur in \(\approx 4\%\) of the subinstances for the baseline approaches, which might lead to the conclusion that they are only a minor issue. In contrast, the self-contained property is only fulfilled in \(\approx 30\%\) of the instances for the two baseline approaches. As a result, the slight increase in our optimization target seems warranted for applications where the topological correctness of the morph is needed.

Table 2 Properties of the resulting morph when using the three approaches
Full size table

Running Times

Figure 14 shows the running time of the morph based on the used approach. The two baseline approaches use straight-line traces with uniform motion. Therefore, once the correspondence is known, the morph is completely defined. For all approaches, our implementation takes under three seconds to solve the correspondence, even for larger instances.

Our approach uses geodesic paths, which we precompute using shortest-path queries in a visibility graph. Our naive approach for computing the visibility graph takes up to 25 s for larger instances, making up the largest part of the algorithm running time. Solving the timing takes approximately as long as solving the correspondence, with running times smaller than 6 s. In conclusion, making the precomputation of geodesics more efficient is mandatory for real-world applications.

Fig. 14
figure 14

Running times of the morphing depending on the input size

Full size image
Fig. 15
figure 15

Morph between two isochrones for different maximum effort values. Shown is the intermediate polyline for \(t = 0.8\) generated using the baseline and our approach. a The baseline approach is not schematic (arrows) and can move outside the morph region (circle). b For the loop closure, a schematic path between the start and end of the intermediate polylines is added in our approach (arrow)

Full size image

Qualitative Evaluation

After analyzing the approach’s impact on our optimization target, we perform a qualitative analysis based on an example. Figure 15 displays an intermediate polyline of the morph between two octilinear isochrones generated for two different values of maximum effort. The morph is generated with the baseline approach (left) and our approach (right). The morph region and the source and target polyline are shown in gray.

For the baseline solution, many segments of the intermediate polylines do not follow the octilinear directions (red arrows highlight some of them). Additionally, the intermediate polyline leaves the morph region (see red highlights). Such incidents limit the morph’s readability, especially for cases like the one displayed, where the source polyline is contained inside the target polyline. They indicate that one can reach further between the two isochrones.

In contrast, the solution generated with our approach is self-contained and schematic. Nonetheless, the intermediate polylines do not form a closed line anymore. The reason for this lies in the timing of the morph. Recall that our approach is initially designed for polylines, not polygonal rings. To use the algorithm for polygonal rings, we cut the rings open at a vertex and apply the morphing to the resulting polyline. The algorithm for computing the transition timing ensures consistency within the morph, but a loop closure for rings is not yet considered. A simple approach to this issue is introducing a loop closing segment (dotted line in Fig. 15b). This closing segment will always be on the cut line, which is schematized by construction. Thus, the resulting loop closing segment also follows the schematization.

Continuous Generalization

As discussed in the “Related Work” section, continuous generalization is a key application of morphing in cartography. To assess the suitability of our approach for this purpose, we focus on the example of rivers. Specifically, we evaluate the effectiveness of our method in supporting continuous generalization within the context of schematization by morphing between schematized versions of rivers with varying levels of abstraction.

Table 3 Properties of the resulting morph when using the three approaches
Full size table
Fig. 16
figure 16

The last two morph instances for the River Rhine. Using only basic operations, the convexities collapse onto one of the cutting points

Full size image
Fig. 17
figure 17

The last two morph instances for the River Rhine. When multi-operations are allowed, the morph appears more natural

Full size image

Input We generated the input instances for 10 European rivers – Danube, Ebro, Elbe, Loire, Po, Rhine, Rhone, Seine, Thames, and Vistula – whose geometry we extracted from OpenStreetMap.Footnote 2 For generating schematized variants of the geometries, we apply a grid-based algorithm, detailed in Appendix 4. For each river, we produced two schematized versions with differing levels of abstraction. We then generated a morphing sequence for each pair, transitioning from the more schematized version to the less schematized one, resulting in ten morphs – one for each river. The resulting morphs are found on https://www.geoinfo.uni-bonn.de/morphing.

Quantitative Evaluation Since the morph inputs are generated for the same geometric feature, they contain many intersections. After applying the preprocessing steps — specifically, dividing the inputs into subpolylines as illustrated in Fig. 10) — we end up with 189 morph subinstances, averaging about 19 subinstances per river. Due to the large number of subinstances, each individual subinstance is relatively small, with the largest containing only 32 vertices on the source polyline. When conducting the quantitative evaluation, similar to the method used for isolines, we observed that these smaller instances exhibit slightly different behavior than the isolines. The results of this evaluation are presented in Table 3.

In this scenario, none of the methods introduced self-intersections during the morph, and nearly two-thirds of all subinstances remained self-contained, even when using the baseline methods. Computation times were also much faster, with the slowest instance completing in less than 0.3 s, including geodesic path computations. When comparing the schematic baseline solution to our approach, the differences are minimal. As such, the additional complexity introduced by computing geodesic paths might not be warranted given the scenario of continuous generalization, especially since the self-contained property appears less critical for rivers than it is for isolines.

Qualitative Evaluation When examining the generated morphs, we observe that many points of the less abstracted source polyline seem to collapse onto a single point on the more abstracted target polyline. Figure 16 illustrates this effect with two subinstances of the River Rhine where the convexities of the source polyline collapse to the left, converging onto a single vertex of the target polyline.

The reason for this is that the current approach only allows basic operations, which are a one-to-one correspondence between elements on the source and target polyline. In the example where the target polyline consists of a single element, no other correspondences are possible. To address this limitation, multi-operations could be introduced, enabling one-to-many and many-to-one correspondences. Figure 17 shows the morphing for the same subinstances multi-operations are enabled. In this scenario, the convexities collapse more naturally, aligning with the nearest subsection of the target polyline.

Conclusion and Future Work

We have presented and evaluated an approach for generating a schematic morph animation for C-oriented input polylines. The resulting animation fulfills several constraints imposed to reduce its visual complexity and thus improve its readability. In particular, the animation is C-oriented, self-intersection-free, self-contained in the morph region, and has a constant velocity. While the algorithm is designed for polylines, we showed that it can also be applied to polygonal shapes and yields promising results. Nonetheless, we identified several areas where improvements to the algorithm can be made. In the following, we review possible directions for future work.

Multi Operations

We defined three basic operations, each matching single segments. In cases where the resolution of the source and target polylines is very different, this might lead to suboptimal morphs. To counteract this, multi-operations that can match a whole sequence of segments on one polyline to a segment of the other polyline can be introduced. Our current implementation already supports these multi-operations, but a more detailed evaluation of this extension is needed.

Finding Shape Correspondences for Morphing Multi-Shapes

In this article, we assumed that we are given two polylines that need to be morphed onto each other. For practical application, it might not always be clear which shapes need to be morphed onto each other. For example, isochrones generated for the public transport network might consist of multiple polygons. For these applications, methods for retrieving the input instances for morphing need to be explored. One approach to address this problem is bipartite matching. This method involves modeling the two sets of polygons as vertices in a bipartite graph, with edges representing the suitability of matches between them. While bipartite matching can effectively handle one-to-one correspondences, where one polygon from the first set is morphed to one polygon in the second set, many real-world scenarios require one-to-many or many-to-many matches. Therefore, extending the approach to accommodate these more complex relationships is essential for practical applications.

Utilizing Different Cost Functions

This article minimized the weighted distance the points move during the morph. While this simple metric already yields promising results, other metrics might improve the morph. For example, these metrics could take shape characteristics or prior knowledge on the input into account.

Improving Running Times

The analysis of the running times showed that the computation of the geodesic paths is the bottleneck in our approach. Although this article has not focused on the efficient computation of geodesic paths, it can significantly improve the approach’s utility. This problem has received much attention in the computational geometry community, and efficient algorithms exist to solve this problem. An example is the algorithm published by Guibas and Hershberger (1989) that allows computing the length of the shortest path inside a simple polygon with n vertices in \(\mathcal {O}(\log n)\) time based on a triangulation and a hierarchical decomposition of the polygon. Utilizing such a specialized algorithm could substantially improve the running times of our algorithm.

Additionally, parallel computing can be employed to significantly speed up the computation of geodesic paths. The running times recorded in the evaluation section are based on a single-core implementation. However, because each geodesic path is independent of the others, implementing the computations in a multi-core environment is straightforward, allowing for speed-ups that match the number of available cores.

Relaxing the Constant Velocity Constraint

We showed that the requirements we impose on the morphing (schematic, self-intersection-free, self-contained, and constant velocity) are mutually compatible and can be fulfilled without conflicting with each other. However, they uniquely define the morph animation, leaving no further degree of freedom for additional optimization targets. To introduce some flexibility into the morphing process, the constant velocity constraint could be relaxed. For example, allowing slight variations in speed could help eliminate the need for closing segments while still aiming to minimize speed fluctuations.

User Evaluation

The quantitative evaluation demonstrates that our algorithm performs comparably to state-of-the-art approaches for morphing in cartography. However, this assessment is limited by the absence of user feedback and usability data in real-world applications. To thoroughly evaluate the practical effectiveness and user acceptance of our method in generating meaningful morphs, it is essential to conduct a comprehensive user study.