Building Displacement Based on the Topological Structure

Abstract

Map data at smaller scales than their source can result in spatial conflict, whereby map symbols become too close, or overlaid. Server map generalisation operators may be applied to solve this problem, including displacement. In this paper, we show how an optimisation algorithm, the snake algorithm, was used to displace multiple objects in order to resolve spatial conflicts and maintain important spatial relationships between objects during displacement. Two principles based on the snake algorithm are proposed in this paper. First, the truss structure mirroring spatial proximity relationships between buildings and between building and road is formed based on the weighted proximity graph derived from constrained Delaunay triangulations (CDT) in each map partition. In the weighted proximity graph, each connecting line is determined as a snake and as an element unit to assemble the global stiffness matrix in snake algorithm. Second, a buffer method that calculates force between a building and a road (or other linear features) or between pair of buildings is adopted in the snake algorithm. This avoids the imbalance phenomenon caused by different force calculation methods during the displacement. The feasibility of the approach is demonstrated in obtaining real geographic data. Finally, the results are cartographically usable and in particular, the spatial relationships between objects are preserved.

Keywords:

• map generalisation
• building displacement
• topographic structure
• conflict resolution

ACKNOWLEDGEMENTS

The research was supported by the National Natural Science Foundation of China (grant no. 41071289, 41171350, 41001295, 41201474 and 41101351). This research was also supported by the Center Universities Fundamental Research Project (grant no. 2012205020212).

Additional information

Notes on contributors

Yageng Sun

BIOGRAPHICAL NOTES

Yageng Sun is a PhD candidate in the School of Resource and Environmental Sciences at the Wuhan University. His current research interests include displacement algorithm study in automatic map generalisation and intelligent processing of geographic information.