!"#$%&
中地图点状要素标注算法设计
于秀兰
’
陈滢
’
饶芳艳
’
刘东
(
)*+
中国研究中心
’
北京
,---./
0123
’
045678
’
9:;<0
=
75
>
4?@
>
7;@
A
摘要
B
提出针对
CD?E)F
的地图点状要素标注算法
’
该算法适用于
CD?E)F
中基于会话模式的地图浏览服务
G
首先应用基于规
则的静态点状要素标注算法得到在某一比例尺下的初始结果
’
当用户在地图上浏览并申请服务时
’
在初始标注结果基础上采用增
量标注算法完成用户请求
G
增量算法大大降低了服务处理开销
’
从而可以满足大量用户并发申请
G
该算法已经成功应用于基于位置
的信息服务系统中
G
关键词
B
点状要素标注
H
增量算法
H
CD?E)F
H
制图
中图分类号
B
I
J-.
文献标识码
B
K
文章编号
B,---LM,NN(J--JAONL-MJL-O
,
引言
CD?E)F
是互联网络技术和地理信息系统
(
E)F
A
结合的产物
G
CD?E)F
有效地将
E)F
功能从传统台式
终端扩展到网络终端
’
如
)5PD95DP
浏览器
G
随着应用领
域的不断扩张
’
以及无线网络和移动计算技术的进展
’
CD?E)F
的功 能已 经转 移到 移动 通 讯设 备
’
例 如
’
在
IQK
或手机上实现电子地图的浏览
G
在
CD?E)F
中的
一种主要服务是地图浏览服务
’
其简化的服务模型如
图
,
所示
G
地图浏览服务是基于会话机制的
’
由客户浏览器
发出第一个服务请求开始
’
此时服务器为该客户建立
一个会话
G
CD?E)F
服务器根据请求命令动态地生成
地图数据并返回给客户浏览器
G
此交互过程持续直至
客户主动关闭该会话或超时
G
地图标注的算法和性能一直是制图和
E)F
的基
础问题
’
自然也是
CD?E)F
研究的一个重要内容
G
地
图标注可以很大程度提高地图的可理解性
G
标注包括
点状要素标注
R
线状要素标注和区域要素标注
G
一个有
效的标注系统必须同时解决这三种标注任务
S,T
G
但是
各种标注任务之间又有相对的独立性
’
可以各自独立
研究
G
随着计算技术的发展
’
各种应用的
图
,
CD?E)F
地图浏览服务简化模型
计算机自动标注系统得到了很大发展
’
其中点状要素
标注系统是研究的重要内容之一
G
对地图中的点进行标注问题的研究对象是给定区
域内的点集合及每个点的候选标注位置集合
G
待标注
点的候选标注集分为两类
B
(,A
有限候选标注位置
SJ’MT
H
(JA
无限连续候选位置
(
F34U4563:?D3
A
SV’/T
G
无论候选标注集数量如何
’
标注算法的目标是选
出最佳的标注位置集合
G
这里评价最佳的标准有许多
形式
’
如任意两个标注位置不重叠
’
或标注 点数量最
多
’
重叠最少等等
’
甚至还要求符合美学标准
G
标注算
法已经被证明是
WI
问题
’
目前已发表的标注方法包
括
B
专家 系统
(
X2YD9PF0ZPD@
A’
模拟 退火
(
F4@13:PDU
K55D:3456
A
SMT
’
贪婪算法
(
E9DDU0
A
SMT
’
离散梯度下降算
法
(
Q4Z79DPD E9:U4D5P
A
SMT
’
穷 尽 搜 索
(
X28:1ZP4[D
ZD:978
A
SMT
’
启发 算法
(
\D194ZP47@DP8;U
A
SJ’OT
等 等
G
根
据
];5^894ZP;5ZD5
等人
SMT
的研究成果
B
目前标注质量
最高的是模拟退火算法
G
其标注效率要优于穷尽搜索
算法
’
贪婪算法
’
离散梯度下降等算法
’
但模拟退火的
时间消耗很大
G
如上所述
’
标注算法的最佳性具有不同的衡量标
准
’
在实际应用中
’
不同的服务对标注系统又有着不同
的要求
’
例如在
CD?E)F
中
’
用户在 一定的标 注质量
下
’
更关心的是标注的效率
’
即标注算 法的时间 复杂
性
G
尤其在目前比较热门的基于位置的信息服务系统
(
_*F
’
_;7:P4;5
L
?:ZDUFD9[47DZ
A
中
’
同一时
收稿日期
BJ--JL-N
修订日期
BJ--JL-.
作者简介
B
于秀兰
’(,‘N,aA’
女
’
黑龙江省齐齐哈尔市人
’,‘‘-
年考入哈尔滨工业大学
’,‘‘‘
年
‘
月获得哈尔滨工业大学通信与电
子工程系信号与信息处理专业博士学位
’
同年进入中国科学院大气物理研究所进行博士后的研究工作
GJ--,
年
O
月博士
后出站
’
加盟
)*+
中国研究中心
’
目前是
)*+
中国研究中心高级研究员
G
JM
万方数据