A Zonal Displacement Approach via Grid Point Weighting in Building Generalization

Abstract

When generalizing a group of objects, displacement is an essential operation to resolve the conflicts arising between them due to enlargement of their symbol sizes and reduction of available map space. Although there are many displacement methods, most of them are rather complicated. Therefore, more practical methods are still needed. In this article, a new building displacement approach is proposed. For this purpose, buildings are grouped and zones are created for them in the blocks via Voronoi tessellation and buffering. Linear patterns are then detected through buffer analyses and the respective zones are narrowed to be able to preserve these patterns. After all the buildings are displaced inside their zones, grid points are generated and then weighted through kernel density estimation and buffer analyses to find suitable locations. Accordingly, the buildings are displaced toward the computed locations iteratively. The proposed approach directly enforces minimum distance and positional accuracy constraints while several indirect mechanisms are used for preserving spatial patterns and relationships. For the quality evaluation of the displacement, the angle, length and shape comparison measures are introduced, computed based on the (Delaunay) triangles or the azimuth comparison measure of the connection lines, generated for the buildings. The quality evaluation criteria are yielded according to the visual assessment of the displacement quality and the quantitative analysis of the measures. The findings demonstrate that the proposed approach is quite effective and practical for zonal building displacement.

1. Introduction

When producing maps on a smaller scale and/or a different theme, cartographic generalization is involved to obtain accurate and legible representation of geographic information. The generalization is first applied to individual objects and then to a group of objects. Groups of objects form various spatial contexts. In cartographic generalization, the contextual information should be maintained as far as the target scale allows to convey geographic information to users in a sufficiently accurate manner. Besides, the symbology of the objects has to be adjusted to target scale in terms of discernibility. Consequently, graphic limits become violated in many cases. In order to resolve the graphic conflicts, displacement operation is applied among others. The displacement has not only to ensure minimum acceptable distance among objects but also preserve spatial characteristics and relationships as far as possible. Therefore, it is one of the most complicated operations of contextual cartographic generalization [1,2,3] and is usually needed in the last stage of the generalization. Building generalization is applied up to 1:100K scale. After this scale, instead of individual buildings, built-up areas are shown in general. Since hydrographic and transportation networks surround buildings, they form natural and artificial boundaries for building objects, respectively. Therefore, buildings are often generalized after those kinds of objects. Enlargement of the objects (buildings, roads, etc.) and therefore the occurrence of overlap or the decrease of spacing between them creates conflicts. In addition, previous generalization operations may contribute to the conflict occurrence. In this case, building displacement is applied for the conflict resolution.

The following spatial constraints are regarded during the building displacement [1,4,5]:

• Minimum distance: minimum spacing between two buildings as well as between a building and a surrounding object such as road, railway and river has to be satisfied to ensure their discernibility at target scale. Minimum distance threshold (MDT) is 0.2 mm (10 m for 1:50k) according to the graphic limits used in cartography.
• Positional accuracy: Displacement changes the positions of map objects. It should be restricted to preserve positional accuracy of objects within the scale limits. Positional accuracy threshold (PAT) is applied as 0.5 mm (25 m for 1:50k) for buildings.
• Spatial patterns and relationships: in maps, spatial patterns and relationships of objects should be preserved as much as possible to be able to communicate significant geographic information effectively. In the context of buildings, it is necessary to consider topological, proximal and directional relationships between the buildings as well as between buildings and surrounding objects. For example, according to the Gestalt principles such as continuity and common orientation, specific arrangements of buildings are important in view of visual perception or from a topological aspect, buildings must be located at the same side of the road after generalization.

The first two constraints are principally considered to be stronger than the last because the extraction and the evaluation of spatial patterns and relationships are complex tasks. Therefore, the first two are enforced to access a solution while the last constraint is not enforced directly but proper mechanisms are necessary to maintain them.

There are various methods proposed for building displacement, but they are usually not practical enough to implement in a GIS environment. In addition, the spatial context cannot be precisely described by mechanical or mathematical analysis methods because of the irregular arrangement of the map objects [6]. Very few studies [1,4] mention or consider the effect of individual generalization of both buildings and roads on building displacement. Therefore, the general objective of this study is to develop a practical and sufficiently effective building displacement approach applied in the zones created in the blocks. In this scope, the specific objectives are (1) to detect the zones that include buildings forming linear patterns and to develop a method to preserve those patterns as far as possible, (2) to find convenient locations within the zones dynamically to displace buildings in an iterative way and (3) to propose relevant measures and criteria to evaluate the quality of displacement.

In this context, buildings with graphic conflicts are obtained in groups and the zones are created for the building groups in the blocks in a way that the map space is shared equitably as well as the displacement feasibility of each zone is identified. An experimental study is carried out with a Python extension developed in QGIS to prove the validity of the proposed approach dealing with the displacement of the buildings in topographic map generalization from 1:25k to 1:50k. Meanwhile, the objects individually generalized according to 1:50k in advance were used in the displacement process. In this context, simplification, edge squaring and enlargement were applied for the large (>625 sq m) buildings and collapse and symbolization were applied for small buildings [7].

2. Related Works

Displacement approaches can be categorized into two groups: incremental and holistic approaches. To resolve the conflicts, displacement is applied in sequential steps in the former while the displacement vector is usually computed once in the latter. There are several incremental approaches. In this scope, Ruas [8] presents a sequential displacement approach that allows performing detection and resolution of the conflicts and the evaluation of the displacement results. Lonergan and Jones [9] present an iterative building displacement method through maximizing nearest neighbor distances by regarding legibility constraints. In addition, they compare this method over a simulated annealing-based displacement method and demonstrate some advantages of the former against the latter. Ai and Oosterom [10] use a field-based building displacement. They create displacement fields through the skeleton of Delaunay triangulation and compute the force propagation direction and magnitude in those fields to resolve the conflicts. Lu et al. [11] use the electric field force model for conflict detection and displacement of buildings. In this respect, points are generated along the boundaries of the objects that represent particles with electric power. The conflicts between the objects and the displacement magnitude are determined through electric repulsion between the particles. Basaraner [1] proposes an incremental generalization method for building displacement. He first obtains the proximity clusters to identify the objects in conflict and then creates generalization zones for the clusters through Voronoi tessellation and buffering. After that, displacement candidate and vector are iteratively found by means of Voronoi tessellation, spatial analysis and/or multi-criteria decision making. Sun et al. [12] present an improved immune genetic algorithm (IGA) that satisfies the building alignment constraint and the tangent relation constraint. They compare IGA with genetic algorithm (GA) by applying them in the partitions created by a road network. The superiority of IGA over GA has been shown for resolving graphic conflicts and preserving spatial relationships. Wei et al. [13] present a collaborative displacement method in urban building generalization. They first apply a vector field-based displacement and then evaluate the conflicts between buildings, and between roads and buildings to determine if an additional displacement is needed. Other generalization operations (aggregation, elimination, and constrained reshaping) are then performed to find an acceptable solution from cartographic aspect.

On the other hand, holistic approaches are quite popular among researchers. In this scope, Mackaness [14] proposes a cyclic and iterative displacement algorithm. He identifies spatial conflicts by means of clustering and resolves spatial conflicts via radial displacement while preserving significant spatial relationships. Bader et al. [4] propose an optimization approach for building displacement. They employ a truss structure to hold and preserve significant spatial relationships of buildings. Liu et al. [5] propose a building displacement approach based on a constrained Delaunay triangulation (CDT) skeleton and improved elastic beam algorithm. After partitioning the dataset according to roads, they perform a cyclic and iterative process for detecting conflicts and resolving them via displacement while the skeleton of the gap spaces is obtained with CDT to detect conflicts and construct the proximity graph. The graph is later adjusted using local grouping information and deformed with the improved elastic beam algorithm by means of the forces derived from the detected conflicts. The displacement method attempts to satisfy the cartographic constraints in this way. Ai et al. [15] generate a vector field model to deal with the multiple conflicts in building displacement. A scalar field is created through a Delaunay triangulation skeleton to partition the buildings being processed. A vector field is then formed for conflict detection. The direction and magnitude of the displacement force are computed based on an iso-line model of vector field. Sun et al. [16] apply the snake algorithm for the displacement of buildings. They first partition the map space according to transportation and river networks. Then, the truss structure representing spatial proximity relationships between buildings, and between roads and buildings is generated by means of the weighted proximity graph derived from CDT. Besides, forces between respective objects are calculated with a buffer method and is used in the snake algorithm. In this way, they obtain the results that satisfy cartographic and spatial relationship constraints. Huang et al. [6] use an improved particle swarm optimization (PSO) algorithm for building displacement. In this context, an initial movement vector is calculated with cartographic displacement rules, and the buildings’ original positions are used as the initial particles’ positions. In addition, they compare PSO with an immune genetic algorithm (IGA) and show superiority of the former over the latter. Maruyama et al. [17] tackle with the building displacement as a constrained optimization problem by means of linear programming. They identify spatial relationships among map objects as constraints and optimize the cost function that penalizes excessive displacement of buildings according to the map scale.

3. Methodology and Experimental Setting

3.1. Spatial Partitioning and Building Grouping

It is essential to preserve topological relationships in building displacement. For this purpose, blocks are created by means of surrounding roads (and other linear objects) so that the buildings located at the different sides of the roads cannot interact. In other words, the buildings located in the same block are processed together in displacement. In this study, the road network from 1:50k topographic map was used when creating the blocks.

In view of displacement, it is important to reveal the building groups with MDT. In this context, buffering is applied to buildings in the same blocks regarding the minimum distance criterion imposed by cartographic constraints. In this way, the buildings that are in conflict and would be displaced together are obtained as groups (Figure 1) [18]. This approach is also supported by the findings of Deng et al. [19]. They demonstrate that in terms of the grouping, the buffer analysis approach performs significantly better than remaining eight approaches including SOM, graph clustering and MST among others when the proximity is considered.

3.2. Map Space Allocation for the Building Groups in the Blocks

There are various patterns of buildings. This means a number of different spatial contexts that need to be dealt with cartographic generalization. Therefore, it is not so easy to make proper displacement decisions in the blocks even though the blocks limit the number of buildings to be processed together. In this respect, it is reasonable to form smaller generalization units to make the generalization problem more localized. To this end, generalization zones are created in the blocks through Voronoi tessellation (VT) and buffering, as proposed in [1] (Figure 1a). VT ensures that the map space in blocks is shared equitably between building groups. On the other hand, buffering delimits the movement of buildings in terms of positional accuracy. The generalization zones partly help preserve the spatial relationships between buildings by allowing controlled reduction and/or re-arrangement of associated buildings. More specifically, VT is created via the points densified along the edges of buildings and the resulting Voronoi polygons are then combined according to their intersections with the buildings in the same group. The reason of the densification is to prevent very irregular Voronoi region boundaries between the building groups [18]. In addition, the dissolved PAT-size buffers of those buildings are generated. Following this, the intersection of both geometries is obtained and then clipped according to the MDT allowed between buildings and roads to create the generalization zones (Figure 1b).

There are various and usually complex approaches for building pattern detection and characterization [20,21,22,23,24]. Particularly, linear (i.e., collinear and curvilinear) patterns need a special approach because they are more salient and more prone to distortion than other kinds of pattern [20]. To this end, a practical method is proposed and implemented here to detect the zones with buildings forming linear patterns and to preserve those patterns as far as possible by narrowing the zones. This method takes into account the PAT and the minimum edge of the smallest buildings (MESB), i.e. 0.5 mm (25 m for 1:50k) [18]. The following steps are applied to detect the zones with a linear pattern (Figure 2 and Figure 3):

• The PAT-size-dissolved buffer of the buildings is generated. The size of the buffer was chosen equal to the PAT to obtain smoother geometry containing the respective building group.
• The inward (negative) buffer of the resulting polygon is generated. For the perfectly aligned buildings forming linear patterns, the inward buffering process returns an empty geometry as can be seen in Figure 2. Since most of the patterns do not consist of perfectly aligned buildings, tolerance value (t) is used to be able to detect them and hence the inward buffer size (IBS) was chosen equal to (PAT + ½MESB + t) (e.g., 40 m for 1:50k). According to our preliminary trials, t was chosen as 2.5 m.
• If the area of final polygon is less than 25 sq m (i.e., 0.01 sq mm at 1:50k) or there is no polygon left, it is then assumed that a linear pattern exists in the zone (Figure 3). If the final polygon is a multi-polygon, the area of greater part is taken into account.

The narrowed zones are obtained with the following steps for the linear patterns:

• The inward buffer of the PAT-size-dissolved buffer is generated. The size of the buffer was chosen to be 5 m less than the PAT (i.e., 20 m) to create a suitable movement space for the buildings (Figure 4a).
• The areas between the buildings at the both ends of the group and the boundary of the generalization zone (Figure 4a) are included in the final polygon (Figure 4b).

3.3. Determination of Displacement-Feasible Zones

Displacement usually follows individual and other contextual generalization operations. After the generalization zones are created, they are analyzed in terms of zonal building density ($Dn{s}_{GZ}$) to decide their feasibility for displacement (Equation (1)). If the density is not high, displacement is performed.

On the other hand, if the conflicts cannot be resolved at the first attempt, the number of buildings is reduced with typification/elimination (see specific steps of the inner displacement in Section 3.6.3) and then the displacement is repeated. During this process, an additional constraint about the number of buildings is imposed. Accordingly, the number of the buildings is not permitted to fall below the acceptable threshold (i.e., half of the initial number of buildings) (after [25]).

In short, the displacement can usually be applied without reducing the number of buildings if the density is low or is applied after typification/elimination if the density is medium. Due to the variety of the spatial contexts, it is difficult to identify the exact limits of the density that is valid for all of the zones. Therefore, the limit of high density was determined as 85% after some trials since the highly dense zones are subject to amalgamation/aggregation. In other words, the displacement was applied in the zones with a density less than 85%.

$$Dn{s}_{GZ}=\frac{1}{A_{GZ}}{{\displaystyle \sum }}_{i=1}^{n_B}{A}_i$$

(1)

where $A_{GZ}$ is the area of the generalization zone, $A_i$ is the area of a building, $n_B$ is the number of buildings in a generalization zone.

3.4. Generation of a Grid Point Set for the Zones

A grid point set is generated to investigate the suitability of different locations in the zone for the displacement of buildings. It is generated at the intervals of 5 m (i.e., 0.1 mm at 1:50k) by means of a minimum area bounding rectangle (MABR) of 7.5 m buffered zone geometry by adjusting the spaces along the edges of the MABR (Figure 5); 7.5 m buffer was created to increase the possibility of locating buildings near the zone boundary so that a minimum distance constraint could be resolved more easily.

As a result of preliminary trials, it was observed that a wider grid interval caused an insufficient amount of base points set to represent a building when its minimum dimensions were considered while a narrower interval did not contribute significantly to the solution and negatively affected the processing speed.

3.5. Grid Point Weighting

Density values of all grid points are computed with kernel density estimation (KDE) based on the base points. Points falling into the buildings (i.e., base points) among the grid points are used to represent the buildings. Reciprocals of the KDE values are then assigned to the points as weights. Thus, the further away the grid points are from the base points representing buildings, the higher their weights become. From the displacement aspect, the higher the weight of a point, the more feasible that location is assumed.

KDE is a frequently employed technique used to transform a discrete distribution of (base) points to a continuous density surface. It preserves the density characteristics of the points in a way that areas that have lots of points receive higher density values than areas that have fewer points [26]. It is calculated with Equation (2) [27].

$$g\left(x,y\right)=\frac{1}{h^2}{\displaystyle \sum }_{i=1}^{n_{BP}}K\left(\frac{d_i}{h}\right)$$

(2)

where $n_{BP}$ is the number of base points in a generalization zone, $g\left(x,y\right)$ is the estimated density at a location $\left(x,y\right)$, $d_i$ is the Euclidean distance from location $\left(x,y\right)$ to a base point, h is the bandwidth, and K is the kernel function.

It is required to determine a bandwidth and a kernel function before applying KDE. The smoothness of the density surface depends on these parameters. It is usually difficult to select an appropriate bandwidth. In many cases, it is experimentally decided. Similarly, the kernel function selection is also experimental. The most preferred function is the Gaussian kernel. When two parameters are compared, the selection of bandwidth is more critical than the selection of the kernel function [26,27].

In this study, the Gaussian kernel function was used with a PAT-size (i.e. 25 m for 1:50k) bandwidth. These parameters were determined experimentally.

3.6. Displacement

The displacement approach is performed in three main phases (Figure 6). First, all buildings are collectively displaced in a way in which their weighted average position is moved toward the zone’s centroid (toward-center displacement). Then, the buildings that intersect with the zone boundary, if any, are re-displaced so that they are located within the zone (inward displacement). Finally, buildings are iteratively moved to suitable locations in the zone (inner displacement). In addition, the post-processing is applied to slightly improve the positional accuracy.

During the displacement, positional change is restricted by the positional accuracy constraint and thus its violation is not permitted. The process is terminated when the minimum distance constraint is satisfied between all buildings or the session limit of the inner displacement is reached or the final number of buildings falls below the limit of acceptable threshold.

On the other hand, spatial patterns and relationships do not have a direct effect over the displacement operation. However, those are tried to be preserved indirectly by using the following mechanisms:

• The zones restrict the area that the buildings can move.
• The zones with linear patterns are highly narrowed to preserve the patterns as far as possible.
• Positional accuracy constraint (i.e., PAT = 25 m) limits the positional changes of the buildings.
• Toward-center displacement carries the buildings toward the centroid of the generalization zone collectively to mainly reduce or resolve the conflicts with roads.
• During inner displacement, in every session (see Setion 3.6.3), all buildings are displaced by small amounts proportional to their distances to their computed target locations.

3.6.1. Toward-Center Displacement

In this phase, the buildings are displaced collectively in a way that their area-weighted average centroid (Equations (3) and (4)) relocated at or near the centroid of the zone but the amount of displacement cannot exceed the PAT. Thus, the possibility of deterioration of the spatial relations among the buildings is reduced. Furthermore, the buildings are brought to more suitable locations in terms of their movement to empty spaces, as well as their conflicts with roads being reduced (Figure 7a) or resolved (Figure 7b). On the other hand, some buildings may move slightly outside of their zones after this process.

$$x_{wac}={{\displaystyle \sum }}_{i=1}^{n_B}\left(x_i\times A_i\right)/{{\displaystyle \sum }}_{i=1}^{n_B}{A}_i$$

(3)

$$y_{wac}={{\displaystyle \sum }}_{i=1}^{n_B}\left(y_i\times A_i\right)/{{\displaystyle \sum }}_{i=1}^{n_B}{A}_i$$

(4)

where $n_B$ is the number of buildings in a generalization zone, $x_{wac}$ and $y_{wac}$ are the area-weighted average centroid coordinates of the buildings in a zone, $x_i$ and $y_i$ are centroid coordinates of a building, $A_i$ is the area of a building.

3.6.2. Inward Displacement

Inward displacement individually moves each building located fully or partially outside the zone into the zone and is applied if the buildings are not completely within the zone after the toward-center displacement (as seen in Figure 7a). New location of the buildings is determined by means of the following steps:

• Directional target location (DTL) ($x_{DTL}$,$y_{DTL}$) is obtained from grid points within the polygon generated with the intersection of PAT-size buffer of the building and the zone (Equations (5) and (6)). These points are called inner grid points.

  $$x_{DTL}={{\displaystyle \sum }}_{i=1}^{n_P}\left(x_i\times w_{0,i}\right)/{{\displaystyle \sum }}_{i=1}^{n_P}{w}_{0,i}$$

  (5)

  $$y_{DTL}={{\displaystyle \sum }}_{i=1}^{n_P}\left(y_i\times w_{0,i}\right)/{{\displaystyle \sum }}_{i=1}^{n_P}{w}_{0,i}$$

  (6)

  where $n_P$ is the number of inner grid points, $x_{DTL}$ and $y_{DTL}$ are the coordinates of DTL, $x_i$ and $y_i$ are coordinates of an inner grid point, $w_{0,i}$ is weight of an inner grid point, computed with the KDE.

The buildings are displaced iteratively in small steps (0.5 m) toward DTL until they are entirely within the zone. The process is applied to all buildings located outside the zone (Figure 8). A building is eliminated if it is impossible to completely move it into the zone because of the size or shape of the zone.

3.6.3. Inner Displacement

Inner displacement is performed after all buildings have been moved into the zone if there is minimum distance conflict between them. The logic behind this process is to displace all buildings in iterative sessions by finding more feasible locations each time as long as the conflicts between the buildings remain unresolved and other termination criteria mentioned in Section 3.6 are not reached.

The session here denotes the displacement of all buildings in the zone once. In the beginning of each session, the weights of the points are updated with the KDE and then modified by the criteria explained below. The displacement order is not important because all buildings in a zone are displaced in each session. In addition, buildings are allowed to move beyond the zone in to a small extent (i.e., 2.5 m) unless the extent of displacement does not exceed PAT, since some buildings cannot use the maximum allowed displacement right due to the zone restriction.

Building-Specific Modification of Grid Point Weights

Initial weights of the grid points obtained with KDE are modified for each building to increase the effect of its relevant points when calculating the DTL. The relevant points of a building are identified by means of buffering. For this purpose, two kinds of buffers are created for every building:

• Unique polygon of a main buffer (UPoly_mb): the difference polygon between the PAT-size buffers of a respective building and other buildings delimited by the zone (Figure 9a). This kind of buffer is created once before the displacement when the buildings are at their initial locations. The size of the buffer chosen is equal to the PAT because the buildings do not have to move outside of these buffers. The difference in polygon corresponds to the unique area where the other buildings cannot be moved. In other words, it is the most feasible area to displace a building; therefore, the weights of the points that fall within this area are increased.
• Unique polygon of an auxiliary buffer (UPoly_ab): the difference in polygon between the half-PAT-size (i.e., 12.5 m) buffers of a building and other buildings (Figure 9b). The size of the buffers was determined after some trials. This kind of buffers are generated in each iteration immediately before displacing buildings. They are not clipped by the zone to be able to involve points around it as well. The reason for creating those buffers is to increase the weight of points that are not located in the intersection of the half-PAT-size buffers of close buildings. In this way, it is possible to move these buildings away from each other and to resolve the conflict between them in general.

The modified weight of a grid point $w_m$ is determined by whether it is contained by one or two of the unique polygons (Figure 9c) using Equation (7), where $w_0$ is the initial weight of a grid point computed with the KDE:

$$w_m=\left\{\begin{array}{cc}{w}_0^2& p\in UPol{y}_{mb}\backslash UPol{y}_{ab}orp\in UPol{y}_{ab}\backslash UPol{y}_{mb}\\ 2w_0^2& p\in UPol{y}_{mb}\cap UPol{y}_{ab}\\ w_0& otherwise\end{array}\right.$$

(7)

Specific Steps of the Inner Displacement

The following steps are applied for the inner displacement (Figure 10):

• The distance between the current $DTL$ ($DT{L}_c$) (Equations (8) and (9)) and the centroid of each building is calculated. $DT{L}_c$ is computed in each session again for each building.

  $$x_{DT{L}_c}={{\displaystyle \sum }}_{i=1}^n\left(x_i\times w_{c,i}\right)/{{\displaystyle \sum }}_{i=1}^n{w}_{c,i}$$

  (8)

  $$y_{DT{L}_c}={{\displaystyle \sum }}_{i=1}^n\left(y_i\times w_{c,i}\right)/{{\displaystyle \sum }}_{i=1}^n{w}_{c,i}$$

  (9)

  where $x_{DT{L}_c}$ and $y_{DT{L}_c}$ are the current coordinates of $DTL$, $x_i$ and $y_i$ are coordinates of a grid point, $w_{c,i}$ is current weight of a grid point.
• The amount of displacement for a building is set as one-tenth of the calculated distance in the previous step and accordingly each building is displaced toward $DT{L}_c$ in each session. This amount is kept small in order to avoid immediate deterioration of spatial relationships between buildings.
• The displacement process can continue until the maximum permitted number of sessions is reached. After some trials, it was determined to be 40.
• One of the buildings is eliminated or typified if there is still a conflict when the sessions are over. This building is one of the two buildings that have the most conflict (i.e., the nearest ones) prior to inner displacement, either the smaller one if their areas are different, or one of them if they have an equal area and same shape (compactness). The typification/elimination process is performed with the area-weighted recentering and the inner displacement process is repeated with the remaining buildings by starting from their initial positions.
• After the typification/elimination, if the number of buildings is less than half of the initial number of buildings, the displacement process is cancelled in this zone and a solution must be found with another generalization operation.

3.6.4. Post-Processing

After the inner displacement, as post-processing, the buildings are collectively shifted back towards the initial centroid of the building group in small steps to decrease the amount of the positional difference (Figure 11). The collective shift process is terminated as soon as any building touches it with the zone boundary.

3.7. Evaluation of the Displacement Quality

Three constraints mentioned before are taken into account in terms of the displacement quality. It should be noted that all constraints are applied in the zones. Therefore, the zones restrict the movement of buildings and mainly help to preserve proximal relationships between the building groups.

The first two constraints, i.e., the minimum distance and positional accuracy constraints are enforced and required to be satisfied during the displacement. The third constraint is not directly enforced and tried to be satisfied indirectly as explained in Section 3.6.

The quality is scored in a range of 1–5 and is ranked in a range from “very bad” to “very good”. If the minimum distance constraint is not fully satisfied in a zone, its quality is scored to be 1 and is ranked to be “very bad”. Another operation such as elimination (only for single buildings), amalgamation, or aggregation should be considered for the zones where the conflicts remain unresolved.

As the first two constraints are ensured to be satisfied, the displacement quality is evaluated based on the spatial relationships of the buildings before and after displacement. The remaining scores, i.e., from 2 to 5 are produced accordingly. In this scope, some measures are proposed in this study, depending on the number of buildings.

For the zones with a minimum of three buildings, Delaunay triangulation is generated using the centroids of the initial buildings in the zones. After the displacement, new triangles are also generated for the same triples of buildings (Figure 12).

Three measures are proposed to evaluate the quality of the building displacement, which compare the initial and final states of the corresponding triangles (e.g., $T_1$ and $T_1^{\prime }$) from angle, length, and shape aspects. For the angles, the angle comparison measure ($m_{\alpha }$) is introduced and computed based on the standard deviations (Equation (10)). For the lengths, the length comparison measure ($m_l$) is introduced and computed based on the ratio of the standard deviations to the averages (Equation (11)). For the shapes, the compactness comparison measure ($m_c$) is introduced and computed based on the areas and the perimeters (Equation (12)). Compactness (a.k.a. circularity) was preferred as it is one of the most-used indices in the practical shape analysis [28,29].

$$m_{\alpha }=\frac{1}{n}{{\displaystyle \sum }}_{i=1}^n\left|\left({\sigma }_{\alpha ,i}-{\sigma }_{\alpha ,i}^{\prime }\right)\right|$$

(10)

$$m_l=\frac{1}{n}{{\displaystyle \sum }}_{i=1}^n\left|\left(\frac{{\sigma }_{l,i}}{{\mu }_{l,i}}-\frac{{\sigma }_{l,i}^{\prime }}{{\mu }_{l,i}^{\prime }}\right)\right|$$

(11)

$$m_c=\frac{4\pi }{n}{{\displaystyle \sum }}_{i=1}^n\left|\frac{A_i}{P_i{}^2}-\frac{A^{\prime }}{P_i^{\prime }{}^2}\right|$$

(12)

where $n$ is the number of triangles in a zone, ${\sigma }_{\alpha }$ and ${\sigma }_{\alpha }^{\prime }$ are the standard deviations of the interior angles of initial and final triangles (IFTs), respectively, ${\sigma }_l$ and ${\sigma }_l^{\prime }$ are the standard deviations of the edge lengths of IFTs, ${\mu }_l$ and ${\mu }_l^{\prime }$ are the average lengths of the edges of IFTs, $A$ and $A^{\prime }$ are the areas of IFTs, $P$ and $P^{\prime }$ are the perimeters of IFTs.

The quality scores of angle $(q{s}_{\alpha })$, length $(q{s}_l)$ and compactness $\left(q{s}_c\right)$ comparison measures are assigned by the following criteria, respectively (Equations (13)–(15)). For obtaining the criteria, a visual assessment of the displacement quality was made and a score was assigned to the zones. Accordingly, the box plots of the scores were generated for the measures. The interdecile ranges of the scores (the values between 10th and 90th percentiles) were regarded to determine the threshold values for the scores to prevent the negative effect of outliers as much as possible. In this way, the criteria of the measures were yielded.

The threshold values of the measures were determined depending on the number of the buildings ($n_b$) in a zone. According to the scores assigned with the visual assessment, it was needed to use different threshold values for the zones with three buildings. For example, the score was 4 for the buildings shown in Figure 13 according to the visual assessment, while the score was 3 according to the general thresholds. Therefore, the threshold values were adjusted appropriately for the zones with three buildings based on their boxplots.

$$q{s}_{\alpha }=\left\{\begin{array}{cc}5,\hfill & \begin{array}{c}{m}_{\alpha }\le 6.5°if{n}_b>3,\\ m_{\alpha }\le 6.45°if{n}_b=3\end{array}\\ 4,\hfill & \begin{array}{c}6.5°<m_{\alpha }\le 14.3°if{n}_b>3\\ 6.45°<m_{\alpha }\le 26°if{n}_b=3\end{array}\\ 3,\hfill & \begin{array}{c}14.3°<m_{\alpha }\le 31.5°if{n}_b>3\\ 26°<m_{\alpha }\le 47.2°if{n}_b=3\end{array}\\ 2,\hfill & \begin{array}{c}31.5°<m_{\alpha }if{n}_b>3\\ 47.2°<m_{\alpha }if{n}_b=3\end{array}\end{array}\right.$$

(13)

$$q{s}_l=\left\{\begin{array}{cc}5,\hfill & \begin{array}{c}{m}_l\le 0.045if{n}_b>3\\ m_l\le 0.085if{n}_b=3\end{array}\\ 4,\hfill & \begin{array}{c}0.045<m_l\le 0.1if{n}_b>3\\ 0.085<m_l\le 0.11if{n}_b=3\end{array}\\ 3,\hfill & \begin{array}{c}0.1<m_l\le 0.16if{n}_b>3\\ 0.11<m_l\le 0.165if{n}_b=3\end{array}\\ 2,\hfill & \begin{array}{c}0.16<m_{l}if{n}_b>3\\ 0.165<m_{l}if{n}_b=3\end{array}\end{array}\right.$$

(14)

$$q{s}_c=\left\{\begin{array}{cc}5,\hfill & \begin{array}{c}{m}_c\le 0.045if{n}_b>3\\ m_c\le 0.052if{n}_b=3\end{array}\\ 4,\hfill & \begin{array}{c}0.045<m_c\le 0.1if{n}_b>3\\ 0.052<m_c\le 0.23if{n}_b=3\end{array}\\ 3,\hfill & \begin{array}{c}0.1<m_c\le 0.27if{n}_b>3\\ 0.23<m_c\le 0.36if{n}_b=3\end{array}\\ 2,\hfill & \begin{array}{c}0.27<m_{c}if{n}_b>3\\ 0.36<m_{c}if{n}_b=3\end{array}\end{array}\right.$$

(15)

Finally, the quality score ($QS$) is calculated by averaging the scores of those measures derived based on the above criteria (Equation (16)). For the measures, equal weights were used since their individual performances according to the visual assessment were similar. Accordingly, the quality rank ($QR$) is assigned to the zones as explained above.

$$QS=⌊\frac{(q{s}_{\alpha }+q{s}_l+q{s}_c)}{3}⌉$$

(16)

If the number of buildings is two, the azimuth comparison measure ($m_{\theta }$) is used that finds the azimuth difference between the connection lines generated between the centroids of the buildings and calculated with Equation (17) (Figure 14) and the scores are assigned by Equation (18).

$$m_{\theta }=\left|\theta -{\theta }^{\prime }\right|$$

(17)

$$QS=\left\{\begin{array}{cc}5,& m_{\theta }\le 10°\\ 4,& 10°<m_{\theta }\le 13°\\ 3,& 13°<m_{\theta }\le 30°\\ 2,& otherwise\end{array}\right.$$

(18)

For single buildings, the quality is evaluated depending on whether a building can be moved into the zone. To be specific, it becomes either 1 (very bad) if there is still a conflict, or 5 (very good) otherwise.

4. Results and Discussion

In the study area, 757 generalization zones were generated and 60.23% (456 out of 757) of the zones were found to be feasible for the displacement. The total number of the buildings was 4586. Among them, 1569 buildings were in the displacement-feasible zones. After the displacement, the number of buildings was reduced to 1194 as a result of typification/elimination (see Appendix A). The Supplementary Material, Video S1 shows how the displacement method works.

According to the quality evaluation of the zonal displacement, the proposed approach yielded quite satisfactory results (see Appendix B) and 78.73% of the zones were ranked “Very Good” in terms of displacement quality. This was followed by “Good”, “Moderate”, “Bad” and “Very Bad” rankings at the rates of 12.50%, 5.04%, 0.44% and 3.29%, respectively (Figure 15).

Average zonal building displacement amounts (${\mu }_d$) ranged between 0.63 m and 24.64 m while the median value was 12.52 m and the 10th and 90th percentiles ranged from 4.38 m to 19.31 m, corresponding to 80% of the values. The zonal displacement amounts of building group centroids ($\Delta d_C$) ranged between 0.00 m and 24.64 m, while the median value was 11.22 m and 10th and 90th percentiles were 1.31 m and 17.86 m, respectively (Figure 16). These findings showed that the positional accuracy constraint was satisfied completely in the zones where the conflicts were resolved (i.e., except for the ones with a “Very Bad” ranking). The displacement amounts are usually greater in the zones next to the roads because the enlargement of the symbol sizes of the roads in addition to the buildings increases the amount of conflicts.

The angle comparison measure yielded values in the range of 0.00–38.33, while the median value was 4.36 and the 10th and 90th percentiles were 0.65 and 12.77, respectively. The length comparison measure got values in the range of 0.00–0.29 while the median value was 0.03 and the 10th and 90th percentiles were 0.00 and 0.10, respectively. Compactness comparison measure got values in the range of 0.00 to 0.35, while the median value was 0.03 and the 10th and 90th percentiles were 0.01 and 0.10, respectively (Figure 17). For all of the measures, the median values are in the range of “Very Good” ranking while the 90th percentiles are in the range of “Good” ranking. These findings showed that the proposed approach, in many cases, was able to preserve the spatial relationships among buildings in the zones.

The quality evaluation criteria pertaining to the spatial relationships among buildings were derived by means of quantitative analysis of the comparison measures based on the scores obtained with the visual assessment of the displacement results. Accordingly, the threshold values were obtained for the quality ranks. Meanwhile, it was recognized that the different threshold values were needed in the case of single triangle (i.e., three buildings) according to the scores assigned with the visual assessment.

For the zones with two buildings, the azimuth comparison measure was used alone because another potential measure, namely the length comparison, did not produce meaningful results that could aid in evaluating the quality.

Concerning the linear patterns, the angle comparison measure yielded values in the range of 0.00–23.25, while the median value was 2.16 and the 10th and 90th percentiles were 0.19 and 6.88, respectively. The length comparison measure got values in the range of 0.00–0.14, while the median value was 0.02 and the 10th and 90th percentiles were 0.00 and 0.05, respectively. Compactness comparison measures got values in the range of 0.00–0.21, while the median value was 0.02 and the 10th and 90th percentiles were 0.00 and 0.07, respectively (Figure 18). Eighty four percent of the linear patterns were ranked “Very Good”, while 15% and 1% of them were respectively ranked “Good” and “Moderate” according to the quality evaluation criteria. These findings show that the proposed approach can quite effectively preserve the linear patterns of buildings in the zones. On the other hand, some zones contain mixed patterns. In that case, our method was not able to detect specific patterns. Clearly speaking, linear and unstructured patterns may be together in a zone due to their closeness and the linear patterns cannot be distinguished in this case. For all of the measures, the median values and 75th percentiles are in the range of “Very Good” ranking. These findings show that the proposed approach is largely able to preserve the linear patterns of the buildings after displacement.

Our approach produces zonal displacement solution and does not consider the conflicts arisen between the zones after displacement. Therefore, in case of occurrence of the conflicts among the buildings belonging to the neighboring zones, the respective buildings may be typified/eliminated. In addition, the semantic differences of the buildings were not taken into account in this study. No or very little displacement should/must be applied to the significant buildings. For example, the religious buildings on which trigonometric points are found should/must not be displaced if possible. Furthermore, the semantic differences should/must be regarded during typification/elimination.

The proposed approach is quite practical and can be developed in a GIS environment by programming without too much effort. It can produce quite successful results for zonal building displacement in many cases. In this context, zonal grid points weighted through KDE and multiple buffer analysis helped to produce satisfactory displacement results in general by allowing us to select optimal locations for buildings in each session. In other words, this strategy provided incremental improvements of the locations of the buildings. In addition, it was possible to detect linear patterns in the zones quite effectively with a new and very practical method. Furthermore, narrowing the respective zones enabled us to preserve this kind of building pattern. Finally, the displacement evaluation criteria produced largely compatible results with the visual assessment, based on three newly proposed measures focusing on the spatial relationships of the buildings. Meanwhile, the satisfaction of the other constrains (i.e., the minimum distance and positional accuracy) was ensured during the displacement.

5. Conclusions

This article introduced a zonal displacement approach specific to building generalization in medium scale topographic maps. In this context, minimum distance, positional accuracy, and spatial patterns and relationships were taken into account to derive a sufficiently accurate and legible representation at a target scale. The individually generalized buildings and surrounding roads were used as inputs and the spatial conflicts occurring between those objects guided the displacement approach. Specifically, the groups of buildings were obtained with the minimum distance criterion to identify the conflicted buildings in the blocks surrounded by roads. The block area was shared among those groups of buildings by generating generalization zones through Voronoi tessellation and buffering. Thus, the displacement problem was reduced to develop a solution in the generalization zones. Besides, the zones with linear patterns were identified through multiple buffering operations and then narrowed to be able to preserve these patterns. Following that, the buildings were first displaced toward the center of the zone collectively and then inward to the zone individually if they were not fully inside. In order to find optimal locations to displace buildings incrementally, the regular points (i.e., a grid point set) were created for the zones and those points were weighted according to the base points falling into the buildings by means of KDE and buffer analysis. In this way, the displacement direction was identified for each building and all the buildings were displaced by small amounts iteratively in multiple sessions. In each session, the weights of the points are updated to find the suitable locations for the buildings according to current state. The displacement process was terminated when the conflicts were resolved or the limit of the permitted number of sessions or the limit of the acceptable number of buildings was reached. Afterwards, the post-processing is applied to improve the positional accuracy slightly. The quality of the displacement was evaluated based on the constraints. Minimum distance and positional accuracy constraints were analyzed during the displacement and were enforced to be met. Spatial patterns and relationships were evaluated after the displacement through (Delaunay) triangulation if a zone had a minimum three buildings or connection lines if a zone had two buildings by comparing initial and final states of those geometries with the angle, length and shape comparison measures in the former case and an azimuth measure in the latter case. According to the threshold values of the measures, determined by quantitative analysis of the visual assessment results, the zones were scored and ranked with respect to the displacement quality.

In future works, interaction with neighboring zones can be dealt with. Linear patterns can be detected in the zones with mixed patterns if available and the related parts of the zones may only be narrowed to preserve the linear patterns. In addition, more specific kinds of patterns may be detected and displaced accordingly. The quality evaluation method may be improved by comparing corresponding lines and angles of the triangles directly. When the displacement is failed, it may be repeated by setting new parameters for the grid resolution and the KDE bandwidth or the parameter settings may be specific to the generalization zones.