...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Transactions in GIS: TG >A Topology-Inferred Graph-Based Heuristic Algorithm for Map Simplification
【24h】

A Topology-Inferred Graph-Based Heuristic Algorithm for Map Simplification

机译：基于拓扑图的启发式地图简化算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this article we present a heuristic map simplification algorithm based on a novel topology-inferred graph model. Compared with the existing algorithms, which only focus either on geometry simplification or on topological consistency, our algorithm simplifies the map composed of series of polylines and constraint points while maintaining the topological relationships in the map, maximizing the number of removal points, and minimizing error distance efficiently. Unlike some traditional geometry simplification algorithms, such as Douglas and Peucker's, which add points incrementally, we remove points sequentially based on a priority determined by heuristic functions. In the first stage, we build a graph to model the topology of points in the map from which we determine whether a point is removable or not. As map generalization is needed in different applications with different requirements, we present two heuristic functions to determine the priority of points removal for two different purposes: to save storage space and to reduce computation time. The time complexity of our algorithm is O(nlogk)which is efficient enough to be considered for real-time applications. Experiments on real maps were conducted and the results indicate that our algorithm produces high quality results; one heuristic function results in higher removal points saving storage space and the other improves the time performance significantly.
机译：在本文中，我们提出了一种基于新型拓扑推断图模型的启发式地图简化算法。与仅专注于几何简化或拓扑一致性的现有算法相比，我们的算法简化了由一系列折线和约束点组成的地图，同时保持了地图中的拓扑关系，最大程度地减少了移除点的数量，并将误差最小化有效距离。与某些传统的几何简化算法（例如Douglas和Peucker的算法）逐渐增加点不同，我们根据启发式函数确定的优先级顺序删除点。在第一阶段，我们将建立一个图形来对地图中点的拓扑进行建模，然后从中确定点是否可移动。由于在具有不同要求的不同应用程序中需要对地图进行概括，因此我们提供了两种启发式函数来确定点移除的优先级，以实现两种不同目的：节省存储空间并减少计算时间。我们算法的时间复杂度为O（nlogk），足以用于实时应用。在真实地图上进行了实验，结果表明我们的算法产生了高质量的结果;一种启发式功能导致更高的移除点数，从而节省了存储空间，另一种则显着提高了时间性能。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号