江苏龙网

  1. 首页 > 生活 > >

现在常用的地图标记避让算法有哪些啊?

一点点点帅 其实讲的挺好的，我简单补充注记是NP难问题，ArcGIS为了提升自己的注记配置效果，专门购置了Maplex注记引擎；商业实现上来看，Maplex是最值得学习的；开源实现的话，可以参考mapserver的maplabel.c或QGIS。1. 关于注记的位置： 4方位模型、8方位模型、滑动模型2. 实时标注和离线切图的时间要求不同，导致其算法实现的差异。 对于实时标注而言，算法设计主要面向如何实时避让和注记，需要将注记位置预处理和实时配置结合起来，合理的预存储数据结构将能够实现最合理的结合；如Petzold提出的reactive conflict graph是其中一种数据结构。 离线切图(将矢量数据渲染成地图瓦片)的话，不太需要关注时间效率，因此注记效果是算法追求的目标。因此，各种数学优化算法如模拟退火、遗传算法等在这里都有用武之地。
■网友
自动地图标记应该算是GIS中最复杂的问题之一吧（属于NP复杂度问题，所以通常不能找到最优解，只能找到较优解），已经有不少的文章讨论过相关算法。跟解决其他NP问题一样，大部分算法的思路都是提供一个启发（heuristic）给算法作为下一步执行的依据。常见的算法大致可分为这么几类（或者是他们的结合）：基于规则的算法（rule-based algorithms）：给算法预先拟定一些规则（这些规则的好坏会在很大程度上影响结果的好坏），按照这些规则执行算法。比如对地名的标注：首先标注且不冲突重要城市的标注；尽量标注在城市的上方，如果遇到冲突则再依次尝试右左下。其他规则还可以描述诸如标注的方向，边缘处如何解决等等。局部优化算法（local optimization algorithms）：依次摆放标注尽量使之不出现冲突，直到某一处标记所有潜在的位置都会出现冲突时，则选择冲突最少（例如给标注拟定一个轮廓，选择重合面积最少的）的一处摆放。这个方法通常结果不会太好，但速度很快。分而治之算法（divide-and-conquer algorithms）：这既可以作为一种策略，也可以作为一种算法的思路。作为策略，比如很有可能在有些地方标注比较稀疏（例如沙漠地区城市较少），可以将那些地方隔离，用快速简单的算法得到令人满意的结果，这在很大程度上能够提高整体的效率（如果地地图很大标注很多，运算时间可能会很长）；而在那些标注密集的地方采用更复杂的算法。作为算法，将地图内容分成小块进行标注，小块再分成更小的小块（递归地），当集合小到可以进行较好的标注（比如分到只对两个地名进行不冲突标注），然后再考虑他们的结合。这种算法分割和结合的方法对结果影响比较大。我觉得除非你自己就是想研究/比较各种算法或者想提出新算法，或者对标注结果有特别或较高的要求，不然没有必要自己去实现这些算法（感觉要花点时间）。ArcGIS QGIS这些平台工具一般都包含地图标记工具。QGIS: 2. Lesson: The Label ToolArcGIS: ArcGIS Help 10.1好像没听过离线切图，不好发表意见。


    推荐阅读


    上一篇：咋看 360 启动私有化这一举动

    下一篇：怎样提高注册用户上传头像的数量