地图自动综合中Beams移位算法的实现与改进

Implementation and Improvement of Beams Displacement Algorithm in Automated Cartographic Generalization

地图自动综合中,基于Beams模型的全局最优化移位算法通过借鉴材料力学中杆件结构的移位和变形,模拟地图上空间目标(群)在移位操作中的传递性和衰减性,从而较好地保持地图目标(群)的形状、空间关系和分布模式。然而,目前对该算法实现细节的介绍仍然较少,也没有可操作的参数(弹性模量、横截面积和惯性力矩)设置方法。针对此种情况,对算法进行了实现与改进。首先,介绍了算法的基本数学模型与有限元求解方法;然后,从算法实现的角度,详细研究了Beams模型刚度矩阵和外力向量的计算和聚合等关键问题;最后,在降低参数复杂性的前提下,提出了一种自适应参数设置方法来改进算法。为了验证算法的可行性和适用性,在Delaunay三角网的支持下,分别对道路网和建筑物群进行移位,结果表明改进后的算法可较好地应用于地图上线状目标(群)和离散面状目标群的移位。

The cartographic displacement algorithm based on the Beams model is a kind of global optimization algorithm that references the mechanics of materials.Using the model,the decay process of propagation in the displacement operation can be simulated,providing cartographically pleasing results with respect to the preservation of shape,spatial relations,and patterns of map object（s）.However,the model lacks a detailed algorithm for implementation and a feasible method for setting the model＇s material parameters（i.e.elastic modulus,cross-sectional area,moment of intertia）.Therefore,we focuses on the implementation and improvement of the algorithm.First,the basic mathematic model and solution method based on finite element method（FEM）are introduced.Second,from a point view of algorithm implementation,a detailed study of the key issues concerning the calculation and aggregation of the stiffness matrix and force vector are presented.Finally,to reduce the complexity of the parameters,we propose an adaptive parameter setting method to improve the algorithm.Supported by a constrained Delaunay triangulation（CDT）,tests against a road network dataset and a building cluster dataset are carried out.The results illustrate that the improved algorithm is feasible and applicable to the displacement problems of linear object（s）and discrete polygon object clusters.