基于非匀质空间下Voronoi图的城市影响范围研究.pdf

2097-3012(2023)03-0410-06 Journal of Spatio-temporal Information 时空信息学报 收稿日期:2022-04-01；修订日期:2023-06-01 作者简介:张晓贺，研究方向为地理信息系统与遥感图像处理。E-mail:nwu_ 基于非匀质空间下 Voronoi 图的城市影响范围研究 张晓贺 山西省测绘地理信息院，太原 030001 摘 要：为解决城市影响范围研究中忽略非匀质空间的问题，本文以光栅扫描算法为基础，提出了一种非匀质空间下面状加权 Voronoi 图生成算法。首先，对面状目标和栅格空间赋予不同的权重；其次，采用 33 邻域模板进行十字交叉 4 次光栅扫描，在距离变换中按栅格像元传递权重对距离进行分解，完成非匀质空间下面状加权Voronoi 图的生成；最后，以山西省 11 个地级市为研究区，进行了验证。结果表明，改进后的算法实现了非匀质空间面状加权 Voronoi 图的生成；相比点状加权 V 图，城市之间权重差异较大，距离较近时，面状加权 V 图更适合城市影响范围划分。关键词：加权；Voronoi 图；非匀质空间；城市影响范围 引用格式：张晓贺.2023.基于非匀质空间下 Voronoi 图的城市影响范围研究.时空信息学报,30(3):410-415 Zhang X H.2023.Research on urban influence range based on Voronoi diagram in inhomogeneous space.Journal of Spatio-temporal Information,30(3):410-415,doi:10.20117/j.jsti.202303013 1 引 言 城市影响范围是城市在社会、经济、政治、文化等因素共同作用下对周围区域所及的最大地域范围（顾朝林等，1999）。确定城市影响范围，是城市规划的一项重要工作，有利于明确城市间的空间作用关系，促进城市合理布局。常用的城市影响范围研究方法有赖利模型、引力模型、潜力模型、断裂点模型、缓冲区分析、Voronoi 图（简称 V 图）、加权 V 图等。其中，赖利模型、引力模型、潜力模型、断裂点模型侧重理论分析，不能实现城市影响范围的具体划分（邓羽等，2013；常小刚和闫浩文，2015）；缓冲区分析不能对空间进行完全划分（黄杏元和徐寿成，1998）；V 图是对空间的一种完全划分，可以实现城市影响范围的具体划分（赵春燕等，2010；赵佳星等，2020）。V 图生成算法可分为矢量和栅格两类。常用的矢量算法有分治算法、插入算法、扫描线算法等。矢量算法计算复杂，不利于海量数据的处理（李成名和陈军，1998），且只能处理点和线段（Okabe 等，2000）。常见的栅格生成算法有扩张算法、距离变 换算法、层次算法、细分算法、确定归属算法、光栅扫描算法（胡鹏等，2006）等。其中，综合考虑精度和效率因素，光栅扫描算法更具有优势，不需要考虑空间目标数量、分布和形状（Fabbri 等，2008）。传统光栅扫描算法，通过 33（或者 55）邻域模板在正反两次扫描中将一个栅格的信息传递给邻近的栅格，生成普通 V 图（Chen，1999）。目前虽然有一些改进算法（Xu 等，2014；江威等，2015；刘青平等，2019），但还不能满足非匀质空间和面状加权。李佳田等（2016）提出了非理想平面梯度 V 图构建算法，只适合简单的点发生元；田松等（2014）基于结晶法提出了顾及障碍物的加权V 图算法，谢顺平等（2010）提出了一种基于网络分析的加权 V 面域图构建算法，可以将交通路网纳入 V 图的生成中，但都未扩展到整个非匀质空间。基于此，本文改进了光栅扫描算法，研究了非匀质空间下面状加权 V 图的生成。以山西省 11 个地级市为研究区，选取城市常住人口、辖区面积、国内生产总值（GDP）等 18 项指标，采用主成分分析法构建了城市综合实力评价指标体系，用山西省坡度图构建非匀质空间，生成了其地级市影响范围 张晓贺：基于非匀质空间下 Voronoi 图的城市影响范围研究 411 图，并进行了对比分析。以期为促进山西省城镇科学规划提供参考。2 非匀质空间面状加权 V 图构建方法 2.1 方法原理 本文针对面状加权目标，改进了传统光栅扫描算法距离变换中的传递信息；针对非匀质空间，由于每个栅格像元传递权重不同，单个像元与目标点之间有众多不同传递权重的其他像元，其到目标点的最短路径会沿着传递权重最高的像元延伸，这样就导致最短路径不一定是直线，不能直接通过横纵坐标值来计算欧氏距离，所以本文按栅格像元传递权重对距离进行分解，用距离累加值代替传统的欧氏距离；为了提高归属精度，采用了“十字交叉”光栅扫描。在光栅扫描的时候使用 33 邻域模板（图 1），通过“十字交叉”4 次扫描实现距离变换，如图 2所示：“左下右上”纵向扫描时使用了模板（a）；“右上左下”纵向扫描时使用了模板（b）；“左上右下”横向扫描时使用了模板（c）；“右下左上”横向扫描时使用了模板（d）。图 1 八邻域示意图 Fig.1 8-neighborhood sketch 图 2 扫描模板 Fig.2 Scanning template 在距离变换的时候，所传递的信息为距离累加值最小时对应父结点行列号与最近目标点的行列号、目标编号、目标权重及距离累加值：12/()kknDDdww，minknnDD（1）式中，knD 为第 n 次扫描 k 邻域计算的距离累加值；kD 为 k 邻域传递过来的距离累加值；d 为距离递增值，如图 3 所示，四角取值2，上下左右取值1；w1为 k 邻域传递过来的目标权重；w2为该栅格像元在非匀质空间中的传递权重。Dn为该栅格像元第 n次扫描计算的最小距离累加值。图 3 距离递增图 Fig.3 Incremental distance graph 四次交叉扫描结束后，连通最短路径生成非匀质空间下面状加权V图。由于采用了光栅扫描方式，改进后的算法时间复杂度同样只受栅格化后像元数量的影响，不受目标数量、分布和形状的影响。2.2 算法描述 输入：（1）发生元，即面状目标矢量数据，按城市综合实力评价指标赋予权重；（2）非匀质空间，即栅格传递权重图，本文按坡度对栅格赋予传递权重。输出：非匀质空间下面状加权V图。算法：（1）将面状目标和非匀质空间组合栅格化为MN大小的3通道图像，通道1记录最近城市编号，通道2记录最近城市权重，通道3记录栅格所代表空间的传递权重；（2）定 义 用 于 标 注 的 结 构 体 数 组mark TMNT.r，T.c，T.x，T.y，T.n，T.w，T.d，分别记录父结点行列号（r，c）、最近目标点的行列号（x，y）、城市编号 n、城市权重 w，以及距离累加值 d；（3）“左下右上”纵向扫描，按式（1）计算4邻域传递过来的最小距离累加值，并用Tij记录最小值对应父结点行列号与最近目标点的行列号、城市编号、城市权重，以及距离累加值；（4）同步骤（3）继续完成“十字交叉”4次扫描并连通最短路径；（5）用TMN.n 生成面状加权V图。3 城市综合实力评价指标体系 3.1 选择评价指标 城市综合实力评价是一个多维度的概念，因此412 Journal of Spatio-temporal Information 时空信息学报 2023,30(3)要遵循全面性、可比性、可操作性等原则，选取不同角度的指标进行评价。如表1所示，本文从城市规模水平、城市经济水平、社会发展水平、基础设施水平四个方面选取了18项指标来构建山西省11个地级市评价指标体系，评价指标数据来自2020年山西省统计年鉴（山西省统计局，2020）。表 1 城市综合实力评价指标体系 Tab.1 Evaluation index system for urban comprehensive strength 一级指标 二级指标 城市规模水平 X1 城市常住人口/万人 X2 辖区面积/km2 城市经济水平 X3 GDP/万元 X4 人均 GDP/元 X5 一般公共预算收入/万元 X6 一般公共预算支出/万元 X7 第二产业总产值/亿元 X8 第三产业总产值/亿元 X9 社会消费品零售总额/万元 X10 固定资产投资（不含农户）/万元 社会发展水平 X11 住户存款余额/万元 X12 全体居民人均可支配收入/元 X13 教育支出/万元 X14 研究与试验发展经费/亿元 基础设施水平 X15 卫生机构床位数/张 X16 普通高等学校数量/所 X17 互联网宽带接入用户数/万户 X18 公路通车里程/km 3.2 数据处理（1）标准化处理。对原始数据进行标准分数处理，首先计算数据的平均值和标准差，然后计算数据的标准化值。（2）主成分分析。先通过正交变换将一组可能 存在相关性的变量数据转换为一组线性不相关的变量，求得标准化后数据的协方差矩阵，计算特征值和相对应的特征向量；然后以主成分对总方差累计贡献率大于85%的标准提取 n 个主成分。由表2知，前两个因子的累计贡献率已达92.061%。表 2 总方差解释表 Tab.2 Explanation of total variance 初始特征值 提取载荷平方和 成分 总计 方差百分比 累计/%总计 方差百分比 累计/%1 12.314 68.409 68.409 12.314 68.409 68.409 2 4.257 23.652 92.061 4.257 23.652 92.061 3 0.771 4.286 96.347 （3）求得11个地级市的综合实力分数：211nmijjikkjSAPW （2）式中，Ak为第k个主成分贡献率；Pij为i市第j项指标的z-score标准化值，Wj为指标j在主成分k上的得分系数。为了消除负值，便于后期V图研究，张晓贺：基于非匀质空间下 Voronoi 图的城市影响范围研究 413 利用式（2）对城市得分进行线性映射，映射区间A，B取值为1，10，计算结果作为城市权重，如表3所示。其中：min1maxmin()iiSSwBAASS （3）式中，A为映射区间最小值；B为映射区间最大值。表 3 城市综合实力最终得分 Tab.3 Final score for urban comprehensive strength 城市 综合实力得分 映射后得分 太原 1.96 10 大同 0.07 4 阳泉 1.08 1 长治 0.02 4.27 晋城 0.49 2.76 朔州 0.83 1.75 晋中 0.03 4.28 运城 0.35 5.24 忻州 0.25 3.45 临汾 0.21 4.81 吕梁 0.15 4.64 4 山西省城市影响范围 以2021年山西省11个地级市建城区范围作为V图的发生元，并将表3中映射后得分作为影响权重赋予相应的发生元；因为城市影响主要通过人类活动实现，而人类活动会受地形影响，坡度越大，人类活动越受限制，即栅格像元的传递能力和坡度成反比，所以取山西省坡度图作为构建非匀质空间要素，按照式（4）给每个栅格像元赋予传递权重，坡度线性映射区间A，B取值为1，50：min2maxmin1()iiGGwBAAGG （4）式中，w2i为栅格像元i的传递权重；Gi为栅格像元对应的坡度值（）；A为映射区间最小值；B为映射区间最大值。其中，山西省坡度区间为0 45.264，如图4所示。以改进后的面状加权V图算法为基础，利用ArcEngine开发相应模块，生成山西省11个地级市影响范围图。作为对比，匀质空间下取欧氏距离，分别构建点状和面状加权V图。如图5所示，通过生成的V图分析，总体上，太原作为省会城市，位于山西省中部，行政和区位 图 4 山西省坡度图 Fig.4 Slope map of Shanxi Province 优势得天独厚，其综合水平名列榜首，影响范围几乎囊括了整个山西省中部；运城、临汾、长治得分区别不大，占据了晋南大部分地区，晋城得分相对较低，划分影响范围相对较小；大同得分虽然不高，但由于独处晋北，影响范围囊括了整个山西北部，添加地形因素后，划分的影响范围增大；忻州、朔州、阳泉、晋中、吕梁影响范围受限于太原，尤其是晋中得分虽然比大同高，但因为离太原较近，其影响范围要远小于大同；添加地形因素后，由于山脉阻隔，朔州和忻州划分的影响范围增大。叠加对比图5（a）、（b），点状加权V图（呈弧形）不仅不能准确反映城市范围特征，且会将权重小的城市（阳泉、晋中）凸出区域划分到权重大的城市（太原）影响范围内（图6中点状加权V错分区域），可见当城市之间权重差异较大、距离较近时，面状加权V图（呈不规则线段）比点状加权V图更能精确划分城市影响范围；结合图4，对比图5（b）、（c），山西省山区较多，均质空间加权V图不能反映地形特点，非匀质空间加权V图沿地形分布，城市影响范围划分受地形因素影响较大，尤其 414 Journal of Spatio-temporal Information 时空信息学报 2023,30(3)图 5 山西省城市影响范围 V 图 Fig.5 Influence range map of cities in Shanxi Province 图 6 点状加权 V 图与面状加权 V 图局部对比 Fig.6 Local comparison between point-weighted Voronoi diagram and area-weighted Voronoi diagram 是在太原与忻州V图边界的划分上表现比较明显，可见非匀质空间加权V图更贴近实际。5 结 论 本文通过对V图算法的研究，改进了光栅扫描算法，实现了非匀质空间下面状加权V图的生成。以山西省11个地级市为研究对象，选取了18项指标，采用主成分分析法构建了城市综合实力评价指标体系，用山西省坡度图构建了非匀质空间，对山西省城市影响范围进行了研究。研究表明：（1）山西省地级市影响范围呈现中心省会超强，南北相对均衡的特点；（2）相比点状加权V图，城市之间权重差异较大、距离较近时，面状加权V图更适合城市影响范围划分。如何科学确定评价指标计算城市综合得分确定城市权重，以及如何改进非匀质空间下V图生成算法，提高边界精度等问题还有待进一步研究。参考文献 常小刚,闫浩文.2015.城市影响范围划分的地理对象影响域分析方法以河南省为例.兰州交通大学学报,34(4):160-165 邓羽,刘盛和,蔡建明,兰肖雄.2013.中国中部地区城市影响范围划分方法的比较.地理研究,32(7):1220-1230 顾朝林,等.1999.中国城市地理.北京:商务印书馆 胡鹏,游涟，杨传勇，吴艳兰.2006.地图代数.2 版.武汉:武汉大学出版社 黄杏元,徐寿成.1998.GIS 动态缓冲带分析模型及其应用.中国图象图形学报.3(10):871-873 江威,吴艳兰,谭树东,马艺文.2015.一种多发生元 Voronoi 图的栅格生成方法.地理与地理信息科学,31(5):39-43,2 李成名,陈军.1998.Voronoi 图生成的栅格算法.武汉测绘科技大学学报,23(3):208-210 李佳田,罗富丽,余莉,张蓝,康顺,林艳.2016.梯度 Voronoi 图及其构建算法.武汉大学学报(信息科学版),41(2):163-170 刘青平,赵学胜,王磊,孙文彬.2019.横-纵扫描的 Voronoi 图栅格生成算法.测绘学报,48(3):393-399 山西省统计局.2020.山西统计年鉴（2020）.北京:中国统计出版社 张晓贺：基于非匀质空间下 Voronoi 图的城市影响范围研究 415 田松,崔希民,孙云华,崔伟宏,李文杰.2014.顾及障碍物的一般图形Voronoi图及其加权图的ArcGIS栅格实现.地理与地理信息科学,30(4):42-45 谢顺平,冯学智,鲁伟.2010.基于道路网络分析的 Voronoi 面域图构建算法.测绘学报,39(1):88-94 赵春燕,蒋琼星,周建平.2010.基于加权 Voronoi 图的湖南省城市影响范围分析.测绘通报,(6):59-61 赵佳星,吕伟才,葛祥,陈卫卫.2020.基于加权 Voronoi 图评价安徽省城市空间吸引力影响范围.测绘通报,(4):125-129 Chen J.1999.A raster-based method for computing Voronoi diagrams of spatial objects using dynamic distance transformation.International Journal of Geographical Information Science,13(3):209-225 Fabbri R,Da F Costa L,Torelli J C,Bruno O M.2008.2D Euclidean distance transform algorithms:A comparative survey.ACM Computing Surveys,40(1):1-44 Okabe A,Boots B,Sugihara K,Chiu S,Kendall D.2000.Spatial Tessellations:Concepts and Applications of Voronoi Diagrams.2nd ed.London:John Wiley&Sons Xu M,Cao H,Wang C Y.2014.Raster-based parallel multiplicatively weighted Voronoi diagrams algorithm with MapReduce.Advanced Intelligent Systems,177-188 Research on urban influence range based on Voronoi diagram in inhomogeneous space ZHANG Xiaohe Shanxi Institute of Surveying,Mapping and Geoinformation,Taiyuan 030001,China Abstract:The delimitation of urban spatial influence regions is an important work that helps clarify the spatial relationships between cities and promotes the rational urban layout.However,inhomogeneous space elements such as terrain are often neglected in urban influence study.Compared with other algorithms,the Voronoi graph is a complete division of space,which can realize the specific division of urban influence range.The raster scanning algorithm of the Voronoi graph offers more advantages and does not require consideration of the number,distribution,and shape of targets.Although there are some improved Voronoi graph algorithms,they may not fully satisfy the inhomogeneous space and the targets with different weights.In an inhomogeneous space,grid pixels have different transfer weights.When calculating distances,numerous other pixels with different transfer weights between a given pixel and the target.The shortest path to the target usually follows the pixel with the highest transfer weight.In this way,the shortest path is generally not a straight line,and the distance cannot be calculated directly using euclidean distance based on horizontal and vertical coordinate values.Building upon the raster scanning algorithm,this paper proposes an improved algorithm for generating a weighted Voronoi diagram generation algorithm for area targets in inhomogeneous space.In this paper,distance is decomposed based on the transfer weights of grid pixels,replacing the traditional euclidean distance with the cumulative distance value.Area targets are decomposed into point targets with the same weight and target numbering.To improve the attribution accuracy,a cross-crossing scanning is adopted.Firstly,inhomogeneous space and area targets are rasterized,with different influence weights assigned to grid pixels occupied by area targets,and varying transfer weights assigned to all grid pixels in inhomogeneous space.Then a 33 neighborhood template is used for cross-crossing four times scanning,transmitting information such as the row and column number of the parent node,the row and column numbering of the nearest target point,the target numbering,the target weight and the cumulative value of the distance when the cumulative value of the distance to target is the smallest.Finally,by considering the target numbering of each grid pixel,the shortest paths are connected to generate the weighted Voronoi diagram of area targets in inhomogeneous space.In the experiment,11 prefecture-level cities in Shanxi Province were selected as research targets,and 18 indicators such as urban resident population,area of jurisdiction,and gross domestic product were employed.The slope map of Shanxi Province was used to construct inhomogeneous space.The results show that the improved algorithm realizes the generation of weighted Voronoi diagram for area targets in inhomogeneous space,making it better suited for delineating urban spatial influenced regions under complex terrain conditions compared to the ordinary Voronoi diagram.Additionally,the time complexity is only affected by the quantity of raster pixels.Therefore,this paper provides a better method for promoting the scientific planning of cities under complex terrain conditions.Key words:weighted;Voronoi diagrams;inhomogeneous space;urban spatial influenced regions