DP算法自动实现方法:以河流化简为例  

Approach to Automating DP Algorithm:Taking River Simplification as a Example

作　　者：闫浩文 张鑫港 禄小敏 李蓬勃 YAN Haowen;ZHANG Xingang;LU Xiaomin;LI Pengbo(Faculty of Geomatics,Lanzhou Jiaotong University,Lanzhou 730070,China;National-Local Joint Engineering Research Center of Technologies and Applications for National Geographic State Monitoring,Lanzhou 730070,China;Gansu Provincial Engineering Laboratory for National Geographic State Monitoring,Lanzhou 730070,China)

机构地区：[1]兰州交通大学测绘与地理信息学院,甘肃兰州730070 [2]地理国情监测技术应用国家地方联合工程研究中心,甘肃兰州730070 [3]甘肃省地理国情监测工程实验室,甘肃兰州730070

出　　处：《武汉大学学报（信息科学版）》2024年第2期264-270,共7页Geomatics and Information Science of Wuhan University

基　　金：国家自然科学基金(41930101)。

摘　　要：曲线化简是自动地图综合的重要内容,但其中广泛应用的DP(Douglas-Peucker)算法却是非自动化的,原因是需要在算法执行之初由人工输入距离阈值ε。为此,首先提出了一个多尺度曲线相似度的计算公式;然后基于该公式,以河流数据为例给出了地图比例尺与曲线目标相似度的函数关系推导方法和曲线目标相似度与ε的函数关系推导方法,进而得出了ε与比例尺的函数关系;最后实现了DP算法的自动化。实验研究表明,利用提出的自动化DP算法可以获得指定地理区域不同比例尺的水系要素的化简结果,化简结果与经验丰富的制图员的手工化简结果的相似度平均值为0.927,相似度总体表现良好,表明了该方法良好的可靠性和较高的智能化。Objectives:Curve simplification is of importance in automated map generalization;nevertheless,the Douglas-Peucker(DP)algorithm popularly used in map generalization is not automatic,because a key parameter called distance tolerance(ε)must be given by experienced cartographers and needs to be input before execution of the algorithm.Methods:To solve the problem,this paper proposed a method to automatically calculateεand by which the automation of the DP algorithm is achieved.The method consists of the following steps:(1)A formula is constructed by the Hausdorff distance for calculating the similarity degree(Ssim)between a curve at a larger scale and its simplified counterpart at a smaller scale.(2)15 linear rivers are selected,and each of them is manually simplified to get their counterparts at seven different scales.The Ssim of each original river and each of its simplified counterpart at a smaller scale can be obtained using the formula constructed by the Hausdorff distance,and 15×7=105 coordinate pairs consisting of(S,Ssim)can be got,and a function between Ssim and S are constructed by the curve fitting using the coordinates.(3)In the meanwhile,the 15 rivers are simplified using a number ofε,and the Ssim of each original river and each of its simplified counterpart at a smaller scale can be calculated using the formula constructed by the Hausdorff distance.In this way,a number of coordinate pairs(ε,Ssim)are got,and a function betweenεand Ssim is constructed by the curve fitting.(4)By the function between Ssim and S and that betweenεand Ssim,a formula betweenεand S can be deducted.Using the formulaεcan be calculated automatically,because in a map generalization task S is usually known.After this step,automation of the DP algorithm is achieved.Re⁃sults:The experiment results show that(1)The proposed DP algorithm can automatically simplify the rivers in a specific geographical area to get the results at different scales;and(2)the resulting river curves generated by the proposed DP algorithm have a high de

关 键 词：曲线化简 地图综合 DOUGLAS-PEUCKER算法 相似度 河流数据 

分 类 号：P283[天文地球—地图制图学与地理信息工程]