Robust line simplification on the plane
Robust line simplification on the plane
复制标题
DOI：
10.1016/j.cageo.2013.08.011
复制
发表时间：
2013-12-01
影响因子：
4.4
通讯作者：
Pallero, J. L. G.
中科院分区：
文献类型：
--
作者：
Pallero, J. L. G.
线的简化是地图综合中的一项重要任务，无论是在传统的纸质系列地图中，还是在地理信息系统和网络地图服务器服务中。使用适当的方法，应通过抑制冗余信息，同时根据新的比例保持原始元素的形状，获得原始元素的准确表示。为此，最广泛使用的算法之一是所谓的Douglas-Peucker算法。它可能会导致不一致的结果，如自相交或与其他元素的相交，因此操作员的监督是必要的自动处理。在这项工作中，一个强大的和易于实现的道格拉斯-Peucker算法的变化，在两个维度的个别线简化。新算法的鲁棒性是基于线段相交的概念，它可以很容易地并行实现。该算法采用标准C99语言编写，可通过OpenMP进行串行或并行编译。算法本身和实现它的程序都是作为自由软件分发的。该方案的有效性进行了测试，使用GSHHG地理数据库，可以通过Web免费获得。结果的输出精度，执行速度和并行实现的可扩展性。(C)2013爱思唯尔有限公司保留所有权利。
Line simplification is an important task in map generalization, in traditional paper series as well as in geographic information systems and web map server services. Using the adequate method an accurate representation of the original elements should be obtained by suppression of redundant information while maintaining the shape of the original elements according to the new scale. To that effect one of the most widely used algorithms is the so-called Douglas-Peucker algorithm. It can lead to inconsistent results such as self-intersections or intersections with other elements, so the operator's supervision is necessary following the automatic treatment. In this piece of work a robust and easy-to-implement variation of the Douglas-Peucker algorithm for individual line simplification in two dimensions is presented. The robustness of the new algorithm is based on the concept of intersection of segments and it can be easily implemented in parallel. The new algorithm brings about correct results regardless of tolerance and morphology of the original line or polygon.The algorithm is coded in standard C99 and it can be compiled for serial or parallel execution via OpenMP. Both the algorithm itself and a program that implements it are distributed as free software. The validity of the solution was tested using the GSHHG geography database that can be obtained free through the Web. Results about accuracy of the output, execution speed and scalability of the parallel implementation are presented. (C) 2013 Elsevier Ltd. All rights reserved.