基于线缓冲区分析的街区合并方法

2011-12-28 03:19明霞
地理与地理信息科学 2011年6期
关键词:邻边链表延长线

郭 建 忠,谢 明霞,,李 柱 林

(1.信息工程大学测绘学院,河南郑州 450052;2.75719部队,湖北武汉 430074)

基于线缓冲区分析的街区合并方法

郭 建 忠1,谢 明霞1,2,李 柱 林2

(1.信息工程大学测绘学院,河南郑州 450052;2.75719部队,湖北武汉 430074)

制图综合不仅是地图学的核心理论和方法之一,而且始终是地图学家关注的焦点问题[1]。居民地街区综合是制图综合的关键部分,而面要素合并是居民地街区综合的一个重要环节[2]。当相邻街区的邻近边的最大距离小于规定指标时进行合并,街区合并效果的好坏在于合并后的街区能否保持原有街区的轮廓特征[3]。研究一种合理的面要素合并算法是一项具有价值和挑战性的工作。

1 基本概念

定义1:面要素相邻边 分别构造面A和面B的某条边lA和lB缓冲距离为d的缓冲区PA和PB,若PA和PB的交集不为空,则称lA和lB为面A和B的相邻边。

定义2:合并点 某一面要素相邻边lA的邻边与另一相邻边lB的交点称为合并点,若lA与其邻边的夹角小于设定阈值,则过lA的端点作其垂线,垂线与lB的交点也称为合并点。

2 基于线缓冲区分析的街区合并

2.1 街区数据预处理

在对街区数据进行合并处理前,需对原始的街区数据进行预处理,删除原始数据中存在的对街区合并无意义的冗余数据。根据街区轮廓多成直角转折、边线大多平行的特点,计算街区数据中相邻三点构成的折角的大小来判断是否为冗余点。具体步骤如下:

(1)依次存储构成街区的各顶点数据P1,P2,…,Pn。

(2)获取某一顶点Pi的两相邻顶点:

以顶点Pi为中间点,计算由Pi及其两相邻点构成的倒角θ的大小。

(3)若θ∈[5°,175°],保留顶点Pi;反之,将Pi标记为冗余点。

(4)重复步骤2、3,直至所有点判断完毕。去除所有被标记的冗余点,由剩余点按原顺序构成街区。

2.2 获取街区间相邻边

街区间相邻边定义的恰当与否是合理进行街区合并的关键所在。街区间相邻边的定义不仅要正确反映客观现实和主观判断,而且要方便计算获取。街区相邻边获取步骤如下:

(1)根据去除冗余点后的点数据,获取街区A和B所有边数据lAi(i=1,2,…,nA)和lBj(j=1,2,…,nB)。

(2)构造街区B的所有边lBj(j=1,2,…,nB)的缓冲区范围为d的缓冲区域PBj(j=1,2,…,nB)。

(3)构造街区A的某条边lAi缓冲区范围为d的缓冲区域PAi,若PAi∩PBj≠Ø(j=1,2,…,nB),则lAi和lBj为相邻边,将其加入相邻边集合NE。

(4)重复步骤3,直至街区A的所有边判断完毕;若相邻边集合中的个数大于2,获取NE中各相邻边的面归属,根据归属获取两个邻边集合NEA和NEB。

(5)计算集合NEA包含的邻边与NEB包含的邻边之间的端点距离和d=dis(lNEAi,lNEBi)(i=1,2,…,nNEA,j=1,2,…,nNEB),最小d值对应的两条邻边即为街区A和B的相邻边lNEA和lNEB。

2.3 计算合并点

相邻街区合并时,需要有中间点(街区合并点)将其点数据连通。根据所获取的相邻街区的相邻边计算街区合并点时,可以总结为以下3种情况:

(1)街区A和B的相邻边lNEA和lNEB中的短边与其两邻边l1和l2的夹角均在[75°,90°]范围内。求解短边两邻边l1和l2的延长线与相邻边lNEA和lNEB中的长边的交点,若交点在长边延长线上,判断相邻边lNEA和lNEB中的长边与其两邻边的夹角;同理,根据所述情况,求解相应交点,两个不在延长线上的交点即为街区A和B的合并点。

(2)街区A和B的相邻边lNEA和lNEB中的短边与其两邻边l1和l2的夹角均小于75°。过相邻边lNEA和lNEB中短边的两顶点作其垂线,求取该线与长边的交点,若交点在长边延长线上,判断相邻边lNEA和lNEB中的长边与其两邻边的夹角;同理,求解相应交点,两个不在延长线上的交点即为街区A和B的合并点。

(3)街区A和B的相邻边lNEA和lNEB中的短边与其两邻边l1和l2的夹角大小分别属于[75°,90°]和(0°,75°)。获取相邻边lNEA和lNEB中短边的两邻边中与其夹角小于75°的邻边与短边的交点,过该交点作短边垂线,求其与长边的交点;同时求解短边另一邻边的延长线与长边的交点,若交点在长边延长线上,判断相邻边lNEA和lNEB中的长边与其两邻边的夹角;同理,根据所述情况,求解相应交点,两个不在延长线上的交点即为街区A和B的合并点。

2.4 构造合并面

构造街区合并面时,首先按照以相邻边lNEA和lNEB的顶点作为相应街区面数据的首末节点的原则,按逆时针或顺时针的顺序调整构成街区的各节点。判断两合并点的归属,会出现以下两种情况:

(1)两合并点均在面相邻边lNEA和lNEB的长边上。在街区B的节点链表尾端追加由末节点所在的邻边计算得到的合并点P2,计算面相邻边lNEA中两顶点A1和A2与合并点P1和P2的距离,若dA1P1>dA1P2,则在链表中追加点A1,反之,追加点A2。判断追加点后的节点链表的末节点是否为街区A的节点链表的首或末节点,若为首节点,则顺序追加街区A节点链表中的各节点,若为末节点,则倒序追加街区A节点链表中的各节点。

(2)两合并点分别在面相邻边lNEA和lNEB上。首先判断面相邻边lNEB中与lNEA相交的邻边,获取该邻边与lNEB的交点,将该交点作为街区B节点链表中的末节点,以lNEB中另一点作为首节点重新构造街区B的节点链表,追加相邻边lNEB的邻边与lNEA的交点P1,判断面相邻边lNEA中与lNEB相交的邻边,获取该邻边与lNEA的交点,追加lNEA中不同于该交点的端点。同理,判断追加点后的节点链表的末节点是否为街区A的节点链表的首或末节点,若为首节点,则顺序追加街区A节点链表中的各节点,若为末节点,则倒序追加街区A节点链表中的各节点。

2.5 街区合并流程

基于线缓冲区分析的街区合并流程如图1所示。当同时合并多个街区要素时,可以对此流程进行循环处理。

图1 街区合并流程

3 实验分析

选取某地区1∶10 000部分居民地数据作为实验数据,综合目标比例尺为1∶50 000,街区合并前后的对比情况如图2所示,合并后街区轮廓上的小毛刺需通过轮廓概括进行去除。从图2中可以看出,合并后的街区保持了原有街区的分布特征,并遵循了街区轮廓多成直角转折、边线大多平行的原则,验证了本文设计的邻近边定位方法和构面规则的正确性。

图2 街区合并前后对比

[1] 王家耀.普通地图制图综合原理[M].北京:测绘出版社,1992

[2] 郭仁忠,艾廷华.制图综合中建筑物多边形的合并与化简[J].武汉测绘科技大学学报,2000,25(1):25-30.

[3] 钱海忠,武芳,朱鲲鹏,等.一种基于降维技术的街区综合方法[J].测绘学报,2007,36(1):102-107.

猜你喜欢
邻边链表延长线
关于哈林图的邻和可区别染色的注记
平行四边形面积公式的推导过程
南京地铁二号线既有线与延长线的施工及转场组织研究
2020年本刊原创题(二)
基于二进制链表的粗糙集属性约简
跟麦咭学编程
基于链表多分支路径树的云存储数据完整性验证机制
链表方式集中器抄表的设计
从游戏中得到的解题方法
平行四边形的判定检测题