Introduction

The automation of map generalization is a task with many subproblems such as simplification, aggregation, selection and typification. These problems need to be solved for various object classes such as buildings or roads. Some of these tasks have been solved satisfactorily in the past, but generally further research is needed.

Previous research on generalization showed that certain spatial structures can be adapted and exploited for diverse problems. Many algorithms that have been developed depend on basic structures in terms of graphs like Voronoi diagrams, Delaunay triangulations – which can be constrained and conformal – medial axes as well as minimum spanning trees. The applications presented in this paper demonstrate the potential of the straight skeleton, which justifies its addition to this list. The straight skeleton exhibits a set of characteristics that can be beneficially exploited for the flexible generation of a medial axis in a general sense, also taking topological constraints into account.

However, generalization tasks can normally not be solved satisfactorily by applying one of the basic operators alone. The derivation of a linear representation for a road from its two dimensional representation is a typical example. Here additional processing steps are necessary in which domain specific knowledge is introduced. The presented workflow for this problem is based on this successive application of basic operators and expert rules.

Generally, the computational aspect of the skeleton algorithm is not the major focus of this paper. This had earlier been elaborated and will be reproduced in this work. This paper focuses on the geometric characteristics, possibilities for manipulations and special features that can be utilized to supply successive steps in the generalization workflow.

The paper is organized as follows: In Sect. 2 different skeleton operators are presented and compared. Outlines of the algorithms are presented to explain the geometric characteristics of the skeletons. Due to its application in this paper, importance is attached to the discussion of previous work on the straight skeleton (Sect. 2.3). After this, two applications to generalization problems are shown. Firstly, the collapse of area features in a topographic database is presented (Sect. 3). Secondly, a new method for the derivation of road centerlines from a cadastral dataset is explained in detail (Sect. 4). Finally, Sect. 5 gives a conclusion.

Skeleton operators

This section summarizes the most common skeleton operators that are used for cartographic applications. Raster based methods are explicitly excluded, since the existing input as well as the demanded output for this work is vector based. Nevertheless, raster based skeleton operators are often used for cartographic applications (see e.g. [12]). In Fig. 1 different vector based skeleton operators are compared.

Fig. 1
figure 1

Comparison of skeleton operators (centerlines bold)

Full size image

Medial axis

Figure 1a shows the medial axis, which is defined as the locus of points that have more than one closest neighbor on the polygon boundary. The bold centerline in the figure is defined by those points of the medial axis, whose closest neighbors do not belong to adjacent edges of the polygon. This skeleton is widely used in geographic information sciences for the analysis of shapes. It consists of straight lines and second order lines that result from reflex angles of the polygon. An algorithm that is of linear time was found by Chin et al. [4]. For practical reasons often approximations of medial axes are used which only consist of straight segments. Since the medial axis is equal to the line Voronoi diagram of the polygon edges, it can be approximated by the Voronoi diagram of a discrete set of boundary points. To generate a good approximation the control points of the polygon need to be densified first. This technique is used by Roberts et al. [11] to derive street centerlines.

Since the Voronoi diagram for a set of points is the dual graph of the Delaunay triangulation, the approximated medial axis can be derived by connecting the circumcenters of adjacent triangles of the triangulation. Here a constrained Delaunay triangulation can be used to ensure that the triangulation covers the same area as the polygon. The medial axis has a very smooth appearance.

Triangulation based skeleton

Another skeleton which is based on a constrained Delaunay triangulation of the polygon was presented by Chithambaram et al. [5]. Alternatively a conformal Delaunay triangulation can be applied [3]. The basic procedure for the skeleton construction from the triangulation does not differ for both cases and is defined as follows: For each triangle which shares one edge with the polygon a skeleton edge is constructed by connecting the centers of the two other triangle edges. Triangles which do not share any edge with the polygon (0-triangles) need to be handled specially. A common approach is to introduce three skeleton edges which connect the triangle’s centroid with each center of its edges. The result of this procedure is shown in Fig. 1b using a conformal Delaunay triangulation. Penninga et al. [10] discuss its advantages compared to the constrained Delaunay triangulation. Since 0-triangles with very obtuse angles can be avoided, unwanted shifts of the skeleton can be reduced.

Another problem that is presented by Penninga et al. is the possible generation of unwanted spikes in 0-triangles. Figure 1b shows that the small disturbance in the polygon boundary has a significant effect on the major axis of the skeleton and a spike is produced. For a better appearance of the skeleton additional rules for the handling of 0-triangles can be defined. However, very difficult cases can appear like multiple adjacent 0-triangles. The occurrence of these spikes can be seen as the biggest disadvantage of the triangulation based skeleton.

The constrained Delaunay triangulation and the conformal Delaunay triangulation are not unique and so the triangulation based skeleton is not well defined. This is a disadvantage if results need to be reproduced.

Straight skeleton

An alternative to the triangulation based skeleton is the straight skeleton presented by Aichholzer et al. [2] which is shown in Fig. 1c. It can be imagined as a roof which covers the polygon ground plan and consists of planes which arise with constant slope from each polygon edge. Each skeleton edge is a bisector of two polygon edges.

The construction of the straight skeleton is based on a stepwise shrinking process of the polygon which can be performed by simultaneous parallel offsets of the polygon edges. In each step the next collision of edges is handled which happens during this process and skeleton edges to the collision point are inserted. The events can be classified into two types which are shown in Fig. 2. An Edge Event means that an edge of the offset polygon is omitted due to a collision of the two adjacent edges. Consequently, the number of polygon edges is reduced by one. In Fig. 2a two simultaneous edge events are shown, which simply can be processed successively. A Split Event (Fig. 2b) happens when an edge of the offset line collides with a vertex incident to two other edges. In this case the polygon is split in this vertex and two new polygons are generated. With respect to the three-dimensional roof illustration, the offset of the polygon corresponds to a line joining points of equal elevation. Defining the roof inclination to be 45°, the offset from the original polygon can be referred to as “roof height”.

Fig. 2
figure 2

Events to be handled for the construction of the straight skeleton. Graphics from Eppstein and Erickson [6]

Full size image

The straight skeleton does not contain any vertex with degree two. This is because each vertex contained in the original polygon boundary has only one incident skeleton edge and each vertex that was constructed by an edge event or a split event has at least three incident skeleton edges.

An important geometric property is that the skeleton consists for the most part of long straight lines which reflect the major axes of the polygon. The geometrical anomaly on the lower right side still has an effect on the shape of the skeleton in Fig. 1c. Yet the generated spike is much less dominant than in the triangulation based skeleton and comparable to the medial axis. The centerline of the skeleton can be defined by comprising all skeleton edges that are not incident to a vertex of the polygon. This centerline is depicted with a bold line. However, it will be shown in Sect. 4.2 that this simple definition does not always suffice to obtain appropriate results for a specific application. A more advanced method for the centerline reduction will be introduced.

The straight skeleton can be altered by assigning slopes to certain roof planes which differ from the default value. With this variation the centerline can be shifted in certain directions. This has been applied in a different domain, namely for three-dimensional reconstruction of buildings from ground plans and laser scanning data [9]. An application in cartography which benefits from this possibility for manipulations will be presented in Sect. 3.

A sub quadratic algorithm for the straight skeleton is described by Eppstein and Erickson [6]. Also the case of different roof slopes is discussed and it is shown that the algorithm can cope with this. Felkel and Obdržálek [7] present an implementation of the straight skeleton and discuss special cases.

A disadvantage of the straight skeleton is its sensitivity to reflex angles close to 360°. In these cases the skeleton will not be situated close to the center of the polygon. The uppermost bend of the polygon in Fig. 1c is a typical example for this case. A solution for this problem is to introduce additional edges of zero length in these vertices. Consequently, an additional roof plane arises from each of these vertices. The orientation of such a plane is defined as follows: The projection of the plane’s normal vector to the horizontal plane must be collinear with the bisector of the original edges incident to the reflex vertex. Its slope is defined to be the same as the slope of the other roof planes. To define the vertices which are to be treated like this, a threshold for the maximal allowed angle between two polygon edges can be defined. Generally, the smallest angle that can be ensured by adding only one edge to a vertex is 270°. For the examples presented in Sect. 4 this angle was applied as threshold.

Figure 1d shows the straight skeleton after the insertion of an additional edge. This skeleton has the same advantages as the normal straight skeleton. In addition the effect of centerline shifts at reflex vertices is reduced. By defining multiple additional polygon edges and roof planes in the reflex vertices, the straight skeleton can be used to approximate the medial axis [13].

The next sections show how the straight skeleton can be applied to map generalization problems. We implemented the skeleton operator for this purpose, following the work of Eppstein and Erickson [6]. Different slopes of roof planes as well as the addition of edges with zero length are supported. Also polygons with holes can be processed.

Collapse of areas

In topographic databases landuse is often represented by attributes of area features, which collectively form a tessellation of the plane. When reducing the scale of such a database by means of model generalization, some area features need to be eliminated. Normally, the area of the deleted feature is assigned to a neighbor to avoid the generation of gaps. The choice of this neighbor can be taken by analyzing attributes and boundary lengths [14]. Since generalization aims at a simplified map, a merge of areas which ends up in a complex shape should be avoided. Considering convexity and circularity measures of shapes when choosing a neighbor for the merge would be an approach to this problem. However, situations can occur when no choice will end up with a more simple map. Figure 3a shows an example of this. The gray area can be assigned to no neighbor without changing the neighbor’s shape dramatically. In this case, a better solution can be reached by splitting the area into multiple parts and assigning these to different neighbors.

Fig. 3
figure 3

Collapse operator based on straight skeleton

Full size image

The following general requirements need to be fulfilled by an operator that has to solve this collapse task:

  1. 1.

    The whole area of the collapsed feature needs to be distributed to its neighbors, leaving no gaps and producing no overlaps.

  2. 2.

    The shapes of the neighbors should be modified as little as possible.

  3. 3.

    Semantic similarities between landuse classes of the involved features should be considered, such that relatively large portions of the area change to similar classes.

  4. 4.

    Topological relationships and boundaries of high priority need to be preserved.

  5. 5.

    A partial collapse shall be possible, such that a feature keeps its two dimensional representation in parts that exceed a certain width.

A problem which is very similar to the discussed elimination of an area appears if a feature is defined to be represented with different geometry types at different scales, e.g., as a polygon in large scale and a line in small scale. Here the released area needs to be assigned to its neighbors, but also a linear representation must be created. For this problem the following requirement needs to be added.

  1. 6.

    The derived linear shape must reflect the major elongations of the polygon and ignore small anomalies.

For specific classes these requirements need to be concretized and further requirements need to be added. For example, in the case that a linear representation needs to be derived for rivers, other geometric characteristics might be favorable than for road centerlines or landuse polygons. A small recess in the polygon boundary could be an ignorable anomaly for one class, while it is an important characteristic feature in case of the other class. In Sect. 4.2 we will present an algorithm that eliminates skeleton edges corresponding to polygon parts which do not conform to a defined object model. A model for roads will be applied to derive road centerlines. First, however, we will discuss possibilities to satisfy the general requirements stated above.

Skeleton based collapse operator

One possibility to approach the collapse task is to use the triangulation based skeleton [1]. It allows to give different weights to different polygon edges and so the centerline can be shifted such that a greater portion of the area is assigned to semantically similar neighbors. However, the risk to obtain unwanted spikes, i.e., zigzag boundaries is a disadvantage with respect to requirement 2. The medial axis is less sensitive to these disturbances. However, the exact algorithms are hard to adapt to special problems like the partial collapse or the collapse with different weights.

In contrast, it will be shown that the straight skeleton can be applied to all stated problems with simple modifications of the original algorithm. With the straight skeleton extension presented by Tănase and Veltkamp [13], i.e., with multiple additional edges in the reflex vertices, no significant geometric difference exists in comparison to other approximations of the medial axis. However, the smooth skeleton that is produced by the medial axis sometimes does not correspond to the level of granularity of the original object, especially when straight man-made objects like roads or buildings are involved. Here, a less smooth skeleton is needed that can be achieved adding maximally one edge to a reflex vertex as it was shown in Fig. 1d.

The edges of the straight skeleton define a decomposition of the original polygon (Fig. 3b). Each fragment of this decomposition is incident to only one polygon edge, and therefore it can be unambiguously assigned to one of the neighbors. Fragments that result from artificially added planes in reflex vertices can simply be separated by the original bisector into two parts to assign the area to the original polygon edges. Figure 3d shows the resulting map after the application of the collapse operator based on the straight skeleton with equal inclinations of planes.

With the straight skeleton different weights can be set by defining different inclinations for the planes that arise from the polygon edges. The area was assigned to its neighbors leading to only little changes of their shapes. In Fig. 3c, a bigger weight and accordingly a bigger part of the eliminated area was assigned to the features on the left side.

Topological constraints

Often an area collapse needs to be performed while certain topological relationships must not be lost and boundaries of high priority must not be changed (requirement 4). An example is a river which flows into a lake (Fig. 4a). After changing the two-dimensional representation of the river into a linear representation, the river and the lake must still be connected while a modification of the lake boundary is not allowed. Applying a naive collapse operator does not assure this. Figure 4b shows the straight skeleton of the river polygon using default settings. The topological relationship is lost.

Fig. 4
figure 4

Straight skeleton that preserves topological relationships

Full size image

The task can be solved by modifying the inclinations of the planes that define the skeleton. Increasing the planes in those edges, that are shared by the river and the lake, causes the skeleton to move into the direction of the lake. Defining vertical planes means, that the skeleton touches these edges. The result of this collapse operator is shown in Fig. 4c.

Another example in which a boundary of high priority needs to be preserved appears if a city area is composed of multiple areal substructures. Then, a collapse of the bordering subareas must not lead to a modification of the borderline. Thus, the collapsing area has to be distributed to the inner neighbors; to this end the planes of the outer boundaries have to be set vertical—which leads to the desired effect.

Partial collapse

The geometry type of a feature in a topographic database depends on the scale of the dataset as well as on the properties of the feature. In some cases this means that an object needs to be split into multiple parts when being generalized, since different parts of an object need to be represented differently in the target scale. A typical example of this is that a river needs to be represented by an area feature if its width exceeds a certain threshold. Otherwise a line feature is used. Figure 5a shows a lake and an incoming river as one area. The task is to split this area into lines and areas according to a given width threshold (requirement 5). A solution with the straight skeleton can be found which takes advantage of the shrinking process on which the skeleton construction is based. More precisely the events described in Sect. 2.3 will be performed only if they happen within half of the width threshold. Events which happen later are not to be processed. Figure 5b shows the skeleton after its termination at an early stage. A width threshold of 20m was applied. In some parts the original polygon has shrunken to lines. Here the centerline of the constructed skeleton needs to be found, which can be done in the same manner as in the case of a complete collapse. In other parts a shrunken polygon is left. Here the extent of the original polygon boundary needs to be recovered by buffering the shrunken polygon. For this, the offset of the last processed event needs to be applied, since the shrunken polygon is defined by the skeleton points located at this level. After constructing the offset, edges of the derived centerline that intersect the resulting polygon need to be clipped.

Fig. 5
figure 5

Partial Collapse of a river and a lake. a Initial polygon. b Uncompleted straight skeleton with polygon at level of last event. c Applying parallel offset, d circular buffer, e circular arcs for acute angles (bold); width threshold = 20 m. f As c, but with width threshold = 5 m

Full size image

Different possibilities for the buffering of the shrunken polygon were tested, namely a parallel offset, a circular buffer and a combined version. Hereof, the parallel offset proved to be inappropriate due to the following observation. In the upper right corner of the shrunken polygon in Fig. 5b an acute angle appeared, because edges of the original polygon were omitted due to edge events. Applying the parallel offset operator on the two edges which form this angle results in a long thin corner in the new polygon (Fig. 5c). In the case of a very acute angle the constructed intersection point of the offset edges would lie far outside of the original polygon. These geometric differences to the old boundary are not acceptable. Also a cartographer would argue that the width falls below the required minimum in this corner.

This problem can be avoided by applying a circular buffer instead of the parallel offset (Fig. 5d). However, this results in a smoothed polygon boundary which might be disfavored according to the objective of changing the boundaries as little as possible.

Therefore, a third procedure is reasonable, which uses a parallel offset by default while problematic vertices of the shrunken polygon, i.e., vertices with acute angles, are treated differently. Here a required minimum value for the angle between the two incident polygon edges can be defined. Figure 5e shows the result of the partial collapse when inserting circular arcs in vertices with angles smaller than 90°. With this procedure, it is guaranteed that the new polygon lies completely within the original polygon and all parts satisfy the width criterion. Most parts of the original boundary are preserved and not modified. Figure 5f shows the partial collapse of the same polygon with a minimal width of 5m.

The combined buffer satisfies the defined requirements best. However, the pure circular buffer might be preferable for visualization tasks that require smoothed lines. The presented method is very similar to the morphologic opening operator, which works on raster data (see e.g. [8]).

Road centerlines

The derivation of centerlines from a polygonal representation of roads is a typical application for a skeleton operator. Often this is needed for network analysis tasks such as routing for car navigation. Figure 6 shows a dataset with parcels from the cadastral administration. The dataset includes information about the land use of each parcel. Thus, also the area covered by roads can be identified.

Fig. 6
figure 6

Source data from cadastral administration. Road parcels in gray

Full size image

The term “road” is used differently in the contexts of cadastral administration and navigation: On the one hand, the road area sometimes comprises (unwanted) areas like parking lots. On the other hand, areas of tunnels, which are important for the network connectivity are missing. In view of this, the automatic derivation of a road map for navigation purposes is only possible to a limited extent. However, the aim is to automatically derive centerlines from the cadastral dataset in order to reduce the manual processing needed to create a road map. In the cadastral dataset the road network is fractured by administrative borders into many small parcels which do not correspond to topographic objects like road sections or road lanes. Consequently, we will consider the union of all road parcels which will be referred to as “road polygon.” The following requirements are defined for a road map in addition to the general requirements from Sect. 3.

  1. 1.

    A road map contains a road centerline for a part of the road polygon if

    1. a.

      its shape is roadlike (this includes all “road axes” that will be defined in Sect. 4.1) OR

    2. b.

      it connects other parts (particularly, this holds for junction areas).

  2. 2.

    In case the road polygon has a roadlike shape (1a) the centerline must have equal distance to both roadsides.

  3. 3.

    In case of a non-roadlike shape (1b) the centerline must connect the centerlines of the neighboring roadlike parts, such that

    1. a.

      their directions are continued AND

    2. b.

      their intersections are as simple as possible AND

    3. c.

      the boundary of the road polygon is not violated.

Figure 7 shows the straight skeleton of the road polygon. Edges of zero length were added to all vertices of the polygon with angles greater than 270°. This skeleton can be analyzed to identify the two different cases defined in requirement 1. In Sect. 4.2 an algorithm is presented that uses a definition for “road axes” to reduce the skeleton to a centerline such that the requirements 1 and 2 are satisfied. The closely spaced skeleton edges in the magnifying box of Fig. 7 will be deleted by this procedure and will not affect the following processing steps. Requirement 3 can not be satisfied by deletion of edges. The centerline needs to be reshaped in parts which do not have the typical elongated shape of a road. Especially this applies to junction areas. A method for their reconstruction was developed which is presented in Section 4.3.

Fig. 7
figure 7

An area of the test dataset with its skeleton. In some parts the distances between vertices of the road polygon are very small, which is due to curves that are approximated by multiple straight lines. This results in a high density of skeleton edges. To clarify this, the shaded clipping is magnified in the bottom right corner

Full size image

Definition of road axes

The geometric characteristics of roads can be described by shape measures such as width, length and the angle between left and right road delineation. Using the straight skeleton is advantageous, since these characteristics can be expressed directly by measures of the skeleton, so that each edge can be tested for satisfying a road axes model.

For this purpose the current offset or “roof height” is assigned to each new vertex during the construction of the skeleton as height value. Here, this value is equal to half of the polygon width since the inclination of all planes is defined to be 45°. The length of a road segment corresponds to the length of the skeleton edge. The inclination of a skeleton edge, which is the bisector of two polygon edges, is a function of the angle between the same edges of the polygon. This relationship can be expressed with i = sin(α/2) , with i being the inclination of the skeleton edge and α being the angle between the two corresponding polygon edges. The skeleton edge is horizontal if both polygon edges are parallel. The following criteria are defined for edges belonging to road axes:

  1. 1.

    The inclination of an edge must not exceed a certain value, which means that the left and right road delineation must be parallel given a tolerance angle. For the examples shown in this paper, a threshold of 20% was used for the inclination.

  2. 2.

    The vertices incident to an investigated edge must have a minimum height, meaning that a road has a minimum width. Here a minimum height of 1 m, corresponding to a minimum road width of 2 m was used.

  3. 3.

    Edges which fulfill the first two criteria are grouped into sequences, that are terminated at vertices with degree higher than two. If such a sequence does not satisfy a length criterion, the associated edges are defined not to be part of the road axes. As length criterion it is defined here, that the total length of a sequence must be greater than the maximal height of its vertices, i.e., a road is longer than wide.

Since the skeleton originally contains no vertex with degree two, each sequence initially contains only one edge. This will change during the processing and thus this definition of sequences becomes more reasonable when edges are reclassified later.

With the defined model, skeleton edges that correspond to road sections with typical shapes can be identified. The following procedures use this model to identify those skeleton parts that need further treatment.

Reduction of skeleton to centerline

To satisfy the requirements 1 and 2 from Sect. 4 some edges of the skeleton need to be deleted. A simple possibility for this reduction is the deletion of all edges which are incident to the vertices of the source polygon. Figure 8a shows the skeleton of a road section and the centerline derived with this procedure. It still includes two edges which neither correspond to roadlike polygon parts nor have a connecting function.

Fig. 8
figure 8

Reduction of the straight skeleton to a centerline

Full size image

A second possibility is to delete all leaf vertices of the skeleton iteratively. This procedure eliminates these unwanted edges, but also dead ends of the road network are lost and only cycles in the skeleton graph survive. However, the second approach is successful if the model for road axes from Sect. 4.1 is applied to differentiate between wanted and unwanted edges. In this case the iterative deletion can be stopped at the current leaf vertex if a valid road axis is detected.

This procedure is presented in Table 1. First the centerline is initialized with the original skeleton (lines 1 and 2). The set of leaf vertices is selected (line 3) and a Boolean variable is defined to indicate whether an additional iteration needs to be performed (line 4). In each iteration the edges are classified (line 6) and the dead ends that were not classified as road axes are deleted (lines 8 to 15). Finally, the set of leaf vertices is updated. The iteration is terminated, if no leaf vertex remains or all dead ends were classified as valid road axes during the last iteration. This algorithm can be implemented independently of the classification procedure that is applied in line 6. So it can easily be adapted to domains that require other criteria.

Table 1 Algorithm for the reduction of the straight skeleton to a centerline
Full size table

With the defined criteria, edges can be classified differently at different iteration steps, since sequences with more than one edge will appear not before first edges were deleted. Figure 8b shows the initial skeleton and the current stage of the centerline after each call of the classification procedure. Edges classified as road axes according to the definition in Sect. 4.1 are highlighted with bold lines. The result after this reduction to the centerline is shown in Fig. 9 for a bigger part of the dataset. With the iterative deletion all unwanted edges were removed, while dead end roads were kept.

Fig. 9
figure 9

Skeleton after reduction to centerline according to Sect. 4.2. Edges classified according to definition in Sect. 4.1 (road axes black)

Full size image

The derived centerline includes edges that do not fulfill the requirements for road axes. These edges were kept due to their importance for the network connectivity. Edges which do not satisfy the criteria can be found in junction areas, but also in areas with unsteady road boundaries and changing road widths.

The output of a classified result is an important advantage of the developed procedure for the centerline reduction. The result not only offers an appropriate representation for most parts of the road with respect to topological and geometrical features. Also those parts that need to be reshaped to satisfy requirement 3 from Sect. 4 are revealed. The successive processing steps that are applied to improve the result can focus on these areas. This strategy is chosen to construct appropriate shapes for junction areas, which will be presented in the following.

Reconstruction of junctions

This section shows how junctions can be reconstructed to satisfy requirement 3 from Sect. 4. The reconstruction is necessary because roads often become wider when entering to junctions which results in unwanted bends in the skeleton. Also small perturbations from symmetric configurations disturb the skeleton in these areas. If more than three roads enter a junction area it is very uncommon, that the corresponding skeleton edges have a single common vertex, which normally would be preferred by a cartographer.

Normally edges of the centerline which are incident to vertices with degree higher than two do not satisfy the criteria for road axes. In a first step sub-graphs of the centerline are expanded from these vertices until valid road axes are reached. Several sub-graphs can become merged during this expansion and consequently can contain more than one branching point. These sub-graphs define junction areas which will be treated individually in the following. The road axes entering a junction area will be tested to satisfy criteria which typically hold for road junctions. If this model is verified, the edges in the interior of the junction area can be replaced. For the junction model it is assumed that extended road axes intersect in intersection points.

A junction must fulfill two criteria to become remodeled:

  1. 1.

    At least three extensions of road axes must intersect in each intersection point.

  2. 2.

    All intersection points within a junction area must be connected by these extensions.

This model covers all star-shaped junctions (Fig. 10a). Also many complex junctions containing more than one intersection point are covered such as the one in Fig. 10b. However, not all possible complex junctions fulfill these two criteria. The validity of these criteria is tested in Sect. 4.4. In Sect. 4.5 examples are presented that are not covered by the model.

Fig. 10
figure 10

Examples of junctions that fulfill the defined requirements

Full size image

To verify the criteria for a certain junction the set of valid intersection points is searched for the road axes entering the junction area. This is done by testing subsets of the set of road axes to fulfill an intersection criterion. For each subset an intersection point is calculated by minimizing the square sum of lateral distances from the road axes. If none of the corrections exceeds a threshold of 3m, the intersection is valid. Otherwise the trend of the road axes is not regarded as being followed which would violate requirement 3 in Sect. 4. The number of possible subsets of the set of road axes is 2n. This is still small, since the number of road axes n that enter a junction area is normally not bigger than 6. Because of this, a complete analysis of all subsets is unproblematic. Sets of axes that are subsets of validated ones are excluded from the solution. For the complex junction in Fig. 10b the solution contains the two intersection points S 1 and S 2 which correspond to the sets of road axes {a,b,d,e} and {a,c,d}.

In the next step, the solution set of intersection points with the corresponding sets of road axes is evaluated to test whether the two criteria for junctions hold. To satisfy the first criterion, each set of axes must contain more than two elements and each axis must be contained in at least one of these sets. If the solution contains more than one intersection point, different sets of axes must intersect to fulfill the second criterion. In this case more than one intersection point lies on a single road axis. The intersection of the two valid sets of road axes, that were found for the complex junction, results in {a,b,d,e} ∩ {a,c,d} = {a,d}. From this it follows that a and d are collinear and both intersection points can be connected with a straight line.

An additional test is necessary to exclude solutions with road axes that intersect the original road polygon after being extended (requirement 3, Sect. 4). Some road axes need to be shortened to become terminated at the found junction points. However, this procedure is only allowed if a part of the original road axis between two junctions persists.

The original skeleton edges of junctions that passed these tests are replaced by edges according to the found solution. The result of the reconstruction of junctions is shown in Fig. 11. In this example, all junctions were properly remodeled. Generally, junctions exist for which the two criteria are not fulfilled. Examples of this will be shown in Sect. 4.5. Independent of this, it can be argued that a representation of junctions by original skeleton edges is much better than a false reconstruction. Therefore, the skeleton representation is kept for junctions that do not satisfy the road junction model.

Fig. 11
figure 11

Result after intersection of adjusted road axes

Full size image

Testing

The procedures developed for the reduction to a centerline and the reconstruction of junctions were tested on a cadastral dataset covering an area of 14km2 with a road network length of 143km and 640 junctions. For this the thresholds from Sect. 4.1 were applied. Fig. 12 illustrates the spatial distribution of road junctions and the differences of their density. The test data set contains the center of the old German town Hildesheim, big parts of its outskirts, as well as some rural areas with a village. The complete town has about 100.000 inhabitants. Its center is depicted with a gray polygon. The example of Figs. 7, 10 and 11 was taken from the outskirts. The clipping used for these figures is represented by the frame north of the city center.

Fig. 12
figure 12

Spatial distribution of processed junctions for Hildesheim, Germany. Classification into correct (white dots) and incorrect junctions (black dots) after application of proposed method. Derived centerlines are displayed as gray lines. The city center is shaded in gray. The clipping used for Figs. 7, 10, 11 is represented by the frame north of the city center

Full size image

The centerlines were inspected visually by four independent test persons according to the requirements from Sect. 4.

It turned out that

  • the road network is complete (except for tunnels that are not included in the cadastral data set),

  • no unwanted edge is existent and

  • the shape of the centerlines is appropriate except for

    • some complex junctions (see Sect. 4.5 for a discussion) and

    • 35 cases in which centerlines are disturbed by parking places or similar features that are included in the road polygon (see Section 4.6).

To assess the developed procedure for the reconstruction of junctions, the evaluators were therefore asked to classify only the junctions into correct and incorrect ones. In 82 cases (13%), the decision was not unanimous. This is very typical for generalization problems, since different cartographers can interpret requirements differently and assess the same situation in different ways. All results that are presented in the following are averages of the four assessments. These statistics are summarized in Table 2.

Table 2 Assessment of road junctions (average values of four evaluators)
Full size table

Of the 640 junctions, 575 (89.8%) were classified as correct. This comprises 550 (85.9%) junctions which were successfully reconstructed according to Section 4.3 and 25 (3.9%) road junctions, for which no intersection points of road axes were found, but the original skeleton configuration was approved. On the other hand, 65 (10.2%) junctions were classified as incorrect. Hereof 54 (8.5%) junctions had not been reconstructed. The remaining 11 (1.7%) junctions had been reconstructed by the algorithm but the result was unsatisfactory. Examples are shown and discussed in the next section.

Discussion of results for junctions

The junctions classified as incorrect and correct by one evaluator can be distinguished by white and black dots in Fig. 12. It can be seen that failures cumulate in certain areas like the town center. This is due to complex configurations, which often exist at central squares that are entered by multiple roads. Figure 13a shows the square in front of the central station, which constitutes a very complicated example. Road axes that probably comply with the evaluation by a cartographer were found. However, these do not fulfill the intersection criteria and so the original centerline of the skeleton was kept. Similar problems can be found at big junctions of arterial roads and at interchanges with ramps and multiple lanes.

Fig. 13
figure 13

Examples of junctions that were not reconstructed by the algorithm

Full size image

In the historical part of the center additional complications appear, since roads often do not satisfy the three criteria from Sect. 4.1. This is because road delineations are often unsteady due to protrusions or misalignments of buildings. Thus, the modeling of junctions is insufficiently supported with reliable information about road axes. Fig. 13b shows an example of this. Since parallel road borderlines are missing, the right junction point is supported only by two road axes, which does not satisfy the requirements from Sect. 4.3.

These restrictions could be eased by permitting additional actions so that more types of junctions can be handled. In the example a procedure can be considered that is capable of constructing the junction points only with the information of the four extracted road axes. Intuitively one would create the left junction point first by intersecting the two left axes and the one entering from the right. Then the fourth axis can be extended until it touches the latter one. A similar example is shown in Fig. 13c. Here the junction could be modeled very easily by intersecting the axes of the two big roads and extending the small one. Similar solutions were proposed by some evaluators to improve the results. However, it is very risky to allow intersections that are supported only by two axes as no additional evidence for the correctness of these solutions is given. Without a very careful treatment of these cases, the number of false reconstructions certainly will increase.

The example in Fig. 13c also reveals a shortcoming of the model for road axes. The inclination of the skeleton centerline persistently decreases when leaving the junction area to the left because of round road borderlines. Since the inclination falls below the threshold before the long straight line is reached, the unwanted bends will be diminished but not eliminated. Figure 14a shows a situation with two junctions that were processed separately by the algorithm, since the connecting centerline was classified as valid road axis. Due to the curvature of this line, the left intersection point was displaced and a false solution was generated. Here the definition for road axes could be enhanced with an additional threshold for the curvature.

Fig. 14
figure 14

Examples of junctions that were incorrectly reconstructed. Manually generated solutions are depicted with dashed lines

Full size image

In other cases, the fixed intersection tolerance resulted in too big shifts of the road centerlines or in a rejection of an existing intersection point. Figure 14b shows an example of the latter case. Here the road is wide enough to allow bigger shifts, which would lead to a single junction point. This however was rejected by the algorithm and a solution with two intersection points was found. Defining a variable intersection criterion that depends on the road width would be an approach to reach a better solution.

Disturbing features at the roadside

In addition to junctions, a postprocessing needs to be done also for some parts of the centerline that do not represent adequate solutions. Though the straight skeleton is relatively stable if the road borderline is disturbed, big recesses and anomalies obviously have effects. Figure 15 presents the most frequent problems. Roads sometimes have recesses on the side (Fig. 15a), which can be due to attached parking lots or real estate borders, that occasionally follow ground plans of buildings. Also roads can become wider in sharp curves or contain bigger areas for turn-over (Fig. 15b). Both results in disturbances of the centerline. Till date these problems need to be processed manually, but also here automatic procedures are imaginable. The definition of road axes is helpful for both examples in Fig. 15. Problems are revealed by the classification result, which can be used to define areas for the reconfiguration of the skeleton. These defects could be reduced with line simplification techniques, which can be applied either to the road polygon before constructing the skeleton or to the derived centerline. The problem could be eased with additional knowledge about parking lots and other objects that are part of the cadastral road polygon but do not belong to the carriageway.

Fig. 15
figure 15

Examples of derived centerlines that need further treatment

Full size image

Conclusion

The straight skeleton is a powerful tool for the derivation of linear representations for polygons. It offers high flexibility and with the presented modifications it can be applied as an operator for area collapse and partial area collapse while topological relationships are preserved. The geometric characteristics of the straight skeleton are superior compared to other skeletons, if long continuous straight lines are demanded, which is not offered by the medial axis. The medial axis however could be preferred to obtain a smooth centerline.

The presented area collapse operator can be applied to the generalization of a polygon map. It can be used to eliminate features without generating gaps while preserving boundaries of high priority. In many cases it will create a more natural solution than a merge with a single neighbor feature. The area feature can be replaced by the centerline of the skeleton if a linear representation is demanded.

The method for the derivation of road centerlines shows how the purely geometric skeleton operator can be enriched by adding expert knowledge—here knowledge about roads. Based on a definition of road axes the centerline can be derived, and road junctions can be reconstructed in a fully automatic way.

The tests of this procedure showed that most junctions (89.8%) can be remodeled appropriately. Due to rather strict intersection requirements the number of false modeled junctions was minimized (1.7%). For junctions that are not covered by the model, the original skeleton solution was kept.

The results for outskirts and rural areas are accurate and promising for practical applications of the method. However, the spatial distribution of junctions classified as incorrect shows that the algorithm often fails in certain areas like the center of a typical European town, which is due to the irregularity and complexity of junctions existing there. Nevertheless the effort to be expended on a manual postprocessing will be greatly reduced when the automatic procedure is first applied. Within an interactive system, the attention of the operator could be directed especially to junctions which were not remodeled by the algorithm. Future research is needed to eliminate effects of disturbing features on the roadside like parking lots. Though this problem has not been solved yet, the presented classification of edges will help operators to detect and reconstruct problematic cases.