适用于道路沿线信息查询的矢量压缩算法_张丹_「金点文库网」分享知识创造价值

世界卫生日-读后感100字

60
测绘通报
2017
年第
9
期
2017（ 9）：60-64．DOI：10．13474j．cnki．11-2246．2017．0288．
引文格式
：
张丹
，
胡泊
．
适用于道路沿线信息查询的矢量压缩算法
［J］．
测绘通报
，
适用于道路沿线信息查询的矢量压缩算法
张
1，2
丹
，
胡泊
1
（1．
黄河水利职业技术学院
，
河南开封
475004；
2．
河南理工大学矿山空间信息技术国家测绘地理信息局重点实验室
，
河南焦作
454003）
摘要
：
针对矢量数字地图中道路布局错综复杂的问题
，
提出了一种用于查询道路沿线信息的矢量压缩算法
。
该方法首先基于夹角
然后利用矢量压缩算法对道路折线进行简化
、分析地物点是否在道路沿线的和欧氏距离对道路端点与拐角凸侧地物点进行判断
，
缓冲区内
，
从而实现地物信息与道路沿线的邻近度判断
。
试验结果表明该方法的高效性和有效性
，
具有复杂道路情况下沿线地物
点的查询分析功能
。
关键词
：
GIS；
缓冲区分析
；
叠加分析
；
矢量压缩中图分类号
：P208
文献标识码
：A0911（2017）09-0060-0 5
文章编号
：0494-
AVectorCompressionAlgorithm forInformationSearchingonＲoadPolyline
2
ZHAN GDan
1，
，HUBo
1
（1．YellowＲiverConserva ncyTechnicalInstitute，Kaifeng475004，China；
2．Ke yLaboratoryofMineSpatialInformationTechnologies，NA SG，HenanPolytechnicUniversity，Jiaozuo454003，China）
Abstract：Aimingattheintricatelayoutofroadsonve ctordigitalmaps，thepapercomesupwithanalgorithmfors earchingfeatures
informationwithinroadpolylineb ufferfieldbasedonvectorcompression．Judgingthefeatu resinformationinendpointsandcorner
thensimplify theroadpolylinebymethodofvectorcompression，analyze the
convexfieldwithincludedangleandEuclideandis tance
，
proximitybetweenpointfeaturesandroad polyline．Andrealizethesearchingfunctionbasedonthis methodonGoogleMap．Experimental
resultsshowthatt healgorithmisefficient，fastandaccurateforsearching alongtheroadpolyline．
Keywords：GIS；bufferanalys is；overlayanalysis；vectorcompression
GIS
查询是从众多的时空实体中选择满足用户
［1］
要求的空间实体
，
空间分析是
GIS
的核心内容之
［2］
一
。
矢量数字地图中道路信息主要以折线
（
由一
Hormann
算法进行了对比分析
。
上述算法需要遍历求出判断点与每一条折线段
之间的最短距离
，
然后与缓冲区阈值进行比较
，
若小
于阈值
，
则判定点在缓冲区内
，
否则不在缓冲区内
。
由此可见
，
这些算法计算过程烦琐
、
效率较低
，
不适
用于节点较多且形状错综复杂的折线
。
针对上述问
题
，
本文提出一种判断点是否在折线缓冲区内的矢
量压缩算法
，
该方法通过对折线的逐步压缩和简化
，
确定与地物点相距最近的道路折线段
，
从而进行点
与线的邻近度判断
，
实现空间查询功能
。
实例验证
结果表明该算法快速
、
有效
，
具有一定的实际应用
价值
。
而道路缓冲区则系列的道路节点组成
）
形式表示
，
［3］
主要是以折线对象为中心线形成的多边形区域
。
判断点与多边形关系的叠加分析是查询道路沿线地
［4-5 ］
，
物信息的重要方法常用的叠加分析多是基于
6］
介绍了基于拓扑模型和文献
［
多边形裁剪算法
，
简单数据模型的两类算法
，
在比较两者优劣性基础
上提出基于交点搜索的多边形叠加分析算法
。
现有
的多边形裁剪算法多针对具体类型的多边形
，
使得
Hodgeman、
算法复杂
、
时间消耗大
，
如
Sutherl-
梁
-
Barsk y、NLN
算法要求裁剪多边形是凸多边形
［7-9］
。
Weiler
算法
，
以及近几年出现的
Vatti
算法及
Greiner-Ho rmann
算法
［10-12］
，
则可以处理一般常见的
12］提出用单线性链表数据结构的多边形
。
文献
［
一般多边形裁剪算法
，
并与
Vatti
算法及
Greiner-
1
1．1常用缓冲区分析方法
道路沿线缓冲区建立
传统的缓冲区分析是在地理实体周围建立一定［13］
宽度的缓冲区多边形
。
角分线法是建立折线缓
06-21
收稿日期
：2017-
基金项目
：2016
年度国家重点研发计划重点专项
（2016YFC0803103）
mail：40663113@qq．com
作者简介
：
张丹
（1980—），
男
，
硕士
，
讲师
，
研究方向为测绘科学与技术
。E-

2017
年第
9
期张丹
，
等
：
适用于道路沿线信息查询的矢量压缩算法
61
冲区的最简单方法
；
凸角圆弧法则是为减小由于凸
侧角点进一步变锐时
，
拐角凸侧处缓冲区远离折线
其中圆弧的节点所引起的偏差而用圆弧进行弥合 ，
两端点为过节点作其相邻两折线段的垂线并与凸侧
［14-15］
。
本文采用凸角圆弧
缓冲区边界形成的交点
法建立折线缓冲区
，
并将点在道路折线缓冲区的情
况分为
3
种
：
区域
1
表示端点处缓冲区
、
区域
2
表示
拐角凸侧处缓冲区
、
区域
3
表示一般区域缓冲区
，
如
图
1
所示
。
在发散的扇形阴影区域
P
i
MN
内
（
若同时满足在多
个节点凸侧的发散扇形阴影区域内
，
则将
A
与距离
予以保留
，
否则将该点最近的节点
P
i
进行判断
），
过滤
。
（3）
若
AP
i
≤
d，
则点
A
位于缓冲区内
。
图
3
图
1
凸角圆弧法生成的折线缓冲区
凸角圆弧缓冲区判断
2
本文算法
折线可以分为理想型折线和一般型折线两类
。
理想型折线
：
折线每个拐弯处的夹角≥
90°（
如
1．2
1．2．1
端点与拐角凸侧缓冲区分析
端点缓冲区分析
端点缓冲区的判定步骤为
（
如图
2
所示
，
以端
点
P
0 为例
）：
（1）
连接
AP
0
、A
1
P
0
，A
1
一侧分别与在折线
A、
折线形成夹角∠
AP
0
P
1
和∠
A
1
P
0
P1
。
（2）
若夹角≤
90°，
将此点直接过滤
；
反之
，
则将
AP
0
与阈值
d
进行比较
，
此时如果
AP
0
≤
d，
判断点
A
在端点 P
0
的缓冲区内
；
若
AP
0
＞d，
则不在该缓冲
区内
。
同理
，
对
P
n
进行分析
，
若点被过滤
，
则需进行后
续算法
。
图
4
所示
），
折线轨迹大幅度逐步远离起始点
。
图
4
理想型折线
一般型折线
：
折线拐角处夹角有锐角有钝角
，
如
“
发夹弯
”“
十字路口自相交
”
等
，
使得折线呈各式各
样且错综复杂
（
如图
5
所示
），
在实际情况下此类折
线更具有普遍性
。
图
2
端点处缓冲区判断
1．2．2
拐角凸侧缓冲区分析
用圆弧对折线在拐角凸侧区域进行拟合
，
形成
凸角圆弧缓冲区
。
对经过由上节端点处过滤所剩余
的点
，
可按下列步骤进行判定
（
如图
3
所示
）：
（1）
连接
A P
i
并与折线在靠
A
点一侧形成夹角
∠
AP
iP
i
－
1
和∠
AP
i
P
i
+
1
。
（2）
若∠
AP
i
P
i
－ 1
和∠
AP
i
P
i
+
1
均大于90°，
则点
图
5
一般型折线
对于理想型折线可用较小夹角法对道路一般
区域的点进行缓冲区分析
，
具体为
：
若使点
A与某

62
测绘通报
2017
年第
9
期 节点
P
i
的距离离最短
，
则设
A
仅可能与 P
i
相关的
折线段形成缓冲区关系
，
通过比较
AP i
与折线形成
并过
A
对形成较小角的临近
A
侧的两夹角大小
，
的折线段作垂线
，
垂距
L
即为点到此折线的最短 距离
。
对于一般型折线
，
如图
5
中点
A与节点
P
3
的距
离最短
，
而实际上最短的折线是
P
4
P
5
，
与节点
P
3
无
关 ，
因此较小夹角法无法适用一般型折线
。
2．1
矢量压缩算法
为适应一般型折线
，
本文提出基于矢量压缩的
算法
，
即对被过滤的点采用基于矢量压缩算法进行
判断
。
首先计算待判定点与某节点取得的最短距
离
，
利用较小夹角法在局部进行初步缓冲区判断
：
（1）
若判定点不在局部折线段的缓冲区内
，
可
将其全部消去
，
并对折线进行压缩简化 。
（2）
在折线断开处用虚拟线段连接
，
这样可以
保证折线的连续性
，
并不参与后续计算
。
（3）
判断点是否在缓冲区内
，
当点同时在多条
折线段的阈值内
，
满足其中之一即可停止计算
， 或当
折线无法再压缩时停止计算
。
2．2
算法原理与实现
2． 2．1
算法原理
P
n
分别为折线的起
、P
i
为中间设
P
0
、
始端点
，
图
6
一般型折线
（2）
从距离集
S_C
中取出
A
与某节点
P
i 间的
令
S
min
=
AP
2
。
最短距离
S
min
，
（3）
连接
AP
i
，
在折线靠
A
一侧形成两夹角
∠
AP
i
P
i
－
1
和∠
AP
i
P
i
+
1
， 通过比较可知
：
∠
AP
2
P
3
=
m in
（
∠
AP
2
P
1
，A
点初步∠
AP
2
P
3
）。
根据较小夹角法
，
找到折线段 P
2
P
3
，
过
A
作垂直于
P
2
P
3
的垂线
AM，
则
A
到线段
P2
P
3
的距离为
L
=
AM
=
AP2
×
sin
∠
AP
2
P
3
（4）（4）
若
L
≤阈值
d，
则点
A
在折线缓冲区内
，
计
P
2
P
3
，
算结束
；
否则
，
去掉节点
P
2
和线段
P
2
P1
、
形成
虚拟线段
P
1
P
3
，
折线被第一次简化
。
折线每压缩一
L_C、S_C
均会发生改次
，
与折线相关的集合
P_C、
变
，
形成新的折线和新的点集合
P_C、
线段集合
L_C
及距离集合
S_C。
（5）
对形成的新折线
，
重复步骤
（1）—
步骤
（4），
当判断出点A
在折线缓冲区内
，
则立即停止计算
；
否则
，
继续简化压缩
。
（6）
若折线再无法继续压缩
（
如图
7所示
），
且
仍未判断出点在缓冲区内
，
则计算终止
， 说明点
A
不在折线缓冲区内
。
1，2，…，n），
节点
（i
=
0，
折线由节点及节点间的折线
P_C、L_C
表示组成折线的节点集合
、
段组成
，
线段
集合
，
即
P _C
=
｛P
0
，P
1
，P
2
，…，Pi
－
1
，P
i
，P
i
+
1
， …，P
n
－
1
，P
n
（1）
L_C
=｛P
0
P
1
，P
1
P
2
，P
2
P
3
，…，P
i
－
1
P
i
，P
i
P
i
+
1
，…，
P
n
－
1
P
n
｝（2）
S_C
为遍历判定点与各节点间的距离集合
S_C
=
｛s_AP
0
，s_AP
1
，…，s_APi
，…，s_AP
n
｝（3）
上述
3
个集合
，
可对折线本身及待判断点与折
线关系进行描述
：
（1）
点
A
为待判定的地物要素点
，d
为缓冲区
L
为计算得到的点与折线段的距离
。
阈值
，
（2）
地图上各点的经纬度坐标已知
，
用
（lat，
lng）
表示
。
（3）
在压缩过程中
，
若出现两条虚拟线段相邻
的情况
，
由于其均不参与计算
，
可自动将它们压缩合
并
，
用新的虚拟线段取代
。
2．2．2
算法实现
图
6
为一般型折线
，
压缩算法的实现过程为
：（1）
对点
A
到折线点集
P_C
中各节点遍历计
算距离
，
得到距离集
S_C。
3
实例验证与结果分析
为验证本文方法有效性
，
选择普通道路与复杂
道路形状两种情况
，
对道路沿线地物信息进行查询
试验
。
（1）
普通道路情况
。
在桂林市叠彩区标注米粉
店若干
（
如图
8
所示
），
然后沿
“
叠彩路
—
芙蓉路
—
凤北路
—
中山路
— 三皇路
—
四会路
”
轨迹在地图上
画出道路沿线
，设置缓冲区阈值为
30m。
点击查询
按钮
，
系统解析出此道路沿线周边的米粉店
，
并在图
中显示
（
如图
9
所示）。
部分标记点的具体查询结
果见表
1。

2017
年第
9
期张丹
，
等
：
适用于道路沿线信息查询的矢量压缩算法
63
（2）
复杂道路情况
。
与上述试验区相同
，
药店
标记点位置如图
10
所示
，
试验结果如图
11
所示
，
试
验具体数据见表
2。
图
7
判定点在折线缓冲区内的矢量压缩过程
图
10
药店标记点位置
图
8
米粉店标记点位置
图
11
表
2
地物点
ID
1
2 3
4
7
道路沿线缓冲区查询结果
道路沿线范围内药店查询结果
（
部分点
）
地物点坐标
与道路实际判断
最短距离
m
结果
22．098
11．0
10．036
11．879
15．962
42．396
60．942
是
是
是
是
是
否
否
准确
与否
是
是
是
是
是
是
是
（25．27021，110．28420）
（25．26985，110．28531）
（25．26864，110．28285）
（25．27002，110．28371）（25．26964，110．28183）
（25．26921，110．28453）
（25．27051，110．28308）
图
9
表
1
地物点
ID
1
2
4
5
6
9
10
道路沿线缓冲区查询结果
8
9
道路沿线范围内米粉店查询结果
（
部分点
） 地物点坐标
与道路实际判断
最短距离
m
结果
14．78821．713
21．250
32．028
13．243
144．574 228．421
是
是
是
否
是
否
否
准确
与否
是
是
是
是
是
是
是
通过上述试验
，
可得出如下结论
：
（1）
本文算法查询准确率高
， 适用于各种类型
的折线形式
。
（2）
计算效率高
，
冗余小
。
当判断出地物信息
在道路沿线缓冲区内
，
即停止计算
。
（3）
仅利用道路节点和地物标记点的经纬度数
据
，
通过夹角和欧氏距离即可进行计算
。
（25．28673，110．30118）
（25．2868 4，110．30288）
（25．28428，110．30046）
（25．28472， 110．29797）
（25．28355，110．29677）
（25．28638，11 0．29854）
（25．28743，110．29668）
4
结语
本文提出了一种用于查询道路沿线地物信息的

64
测绘通报
1974，17（ 1）：32-42．
2017
年第
9
期
矢量压缩算法
。试验结果表明
，
该算法对折线节点
多
、
折线错综复杂等情况，
具有较好的适应性
，
且在
降低了计算量
，
显著提高了计算满足高精度的同时
，
效率
。
参考文献
：
［1］
沙薇
，
盛业华
，
杨林
．
基于
GIS
的高速公路沿线设施管
J］．
计算机应用与软理信息查询系统的设计与实现
［
200 9，26（1）：112-114．
件
，
［2］
［3］
王满
，
孙海燕
．
基于地图代数的缓冲区分析算法的研
J］．
测绘信息与工程
，2009，34（3）：33-34．
究
［
赖云波
，
孙棣华
，
廖孝勇
，
等
．
基于道路缓冲区分析的
．计算机应用研究
，2011，28（9）：
地图匹配算法
［J］
3312 -3314．
［4］
王少华
，
钟耳顺
，
卢浩
，等
．
基于非均匀多级网格索引
J］．
地理与地理信息科学
，的矢量地图叠加分析算法
［
2013，29（3）：17-20．
［5］
［6］
［7］
朱效民
，
赵红超
，
刘焱
，
等
．
矢量地图叠加分析算法研
J］．
中国图象图形学报
，2010，1 5（11）：1696-1706．
究
［
J］．
计算薛胜
，
潘懋
，
王勇
．
多边形叠置分析算法研究
［
2003（2）： 57-59．
机工程与应用
，
SUTHEＲLANDIE，HODGEMANGW．Ｒ eentrant
PolygonClipping［J］．Communicationsofthe ACM，
［8］LIANGY，BAＲSKYBA．AnAnalysisandAlgorithmf or
．CommunicationsoftheACM，PolygonClipping［J］1983，26（11）：868-877．
［9］FOLEYJD，DAMA，FEINEＲSK ，etal．Computer
Graphics，PrinciplesandPractice［M ］．Boston：Addison-
Wesley，1990．
［10］
陈占龙，
吴信才
，
吴亮
，
等
．
基于单调链和
STＲ
树的简
．
测绘学报
，
单要素模型多边形叠置分析算法
［J］
2010，39（1）：102-108．
［11］
陈占龙
，
张丁文
，
吴亮
，
等
．
基于图模型的多边形自动
． 计算机应用研究
，2012，29（5）：
并行构建算法
［J］
163 4-1636．
［12］
刘勇奎
，
高云
，
黄有群
，
等
．
一个有效的多边形裁剪算
J］．
软件学报
，2003， 14（4）：845-856．
法
［
［13］
崔爽
，
苏鸿 ，
叶良松
，
等
．
一种基于空间对象的缓冲区
J］． 地理与地理信息科学
，2011，27（1）：38-
分析算法
［
41 ．
［14］
王家耀
．
空间信息系统原理
［M］．
北京
：
科学出版社
，
2001：291-309．
［15］
邬伦
，——
原理
、
刘瑜
，
张晶
，
等
．
地理信息系统
—
方法和
M］．
北京
：
科学出版社
，2001：168-171．
应用
［
櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂
2010，30（5）：90-96．
（
上接第
41
页
）
［2］SCHAFFＲINB，USYA．OnT otalLeast- square
AdjustmentwithConstraints［J］．IAG-Symp，20 05，128：
417-421．
［3］SCHAFFＲINB，IESEＲA．OnWeig htedTotalLeast-
．JournalofsquareAdjustmentforLi nerＲegression［J］
Geodesy，2008，82（7）：415-421．
［4］
王乐洋
，
许才军
，
鲁铁定
．
病态加权总体最小二乘平差
．
武汉大学学报
（
信息科学版
），
的岭估计解法
［J］
2011，35（11）：1346-1350．
［5］AMIＲIS，JA ZAEＲIS．WeightedTotalLeastSquares
FormulatedbySt andardLeastSquaresTheory［J］．
JournalofGeodesy，2 012，2（2）：113-124．
［6］VIAHIDM．OnWeightedTotalLea st-squaresfor
GeodeticTransformations［J］．Journa lofGeodesy，2012，
86（5）：359-367．
［7］JAZAEＲIS， AMIＲIS，SHAＲIFIMA．IterativeAlgorithm
forWeighted TotalLeastSquaresAdjustment［J］．Survey
Ｒeview，20 14，46（334）：19-27．
［8］
陈玮娴
，
陈义
，
袁庆
，
等
．
加权总体最小二乘在三维激
．
大地测量与地球动力学
，
光标靶拟合中的应用
［J］
［9］
苍桂华
，
李明峰
，
岳建平
．
以入射角定权的点云数据加
J］．
大地测量与地球权总体最小二乘平面拟合研究
［
2014，34（3）：95-98．
动力学
，
［10］
龚循强
，．
测绘李志林
．
稳健加权总体最小二乘法
［J］
2014，43（9）：888-894．
学报
，
［11］
王彬
，
李建成
，
高井祥
，
等
．
抗差加权整体最小二乘模
J］．
测绘学报
，2015，44（6）：602-
型的牛顿
-
高斯算法
［
607．
［12］
陈玮娴 ，．
大地测量与地袁庆
．
抗差总体最小二乘
［J］
2012， 32（6）：111-114．
球动力学
，
［13］
官云兰
，
刘绍堂
，
周世健
，
等
．
基于整体最小二乘的稳
．
大地测量与地球动力学
，
健点云数据平面拟合
［J］
2011，31 （5）：80-83．
［14］
杨元喜
．
抗差估计的概念和任务
［J ］．
测绘通报
，2004
（4）：36-39．
［15］
杨元喜，
宋力杰
，
徐天河
．
大地测量相关观测抗差估计
J］．
测绘学报
，2002，31（2）：95-99．
理论
［
［16］ 袁庆
，
楼立志
，
陈玮娴
．
基于加权整体最小二乘的点云
J］．
测绘通报
，2011（3）：1-3．
数据平面拟合法
［