摘 要：针对大数据下地理空间网络子集探测效率较低的问题，文章通过引入“弧段到点”和“点到弧段”两个索引表，提出了一种地理空间网络子集快速探测方法。该方法创新性地通过两个索引表直接实现了弧段和端点的查找定位，避免了传统子集探测方法中因查找搜索计算冗余度过高导致的效率低下问题，显著提升了地理空间网络子集探测的计算效率。通过MATLAB软件模拟生成了包含不同数量随机点的狄洛尼三角网，利用该方法和传统方法分别进行了子集探测。结果表明，两种方法均可实现子集的成功探测，但是该方法显著改善了子集探测效率。
关键词：地理空间网络；子集探测；索引表
中图分类号：TP39；TP208 文献标识码：A 文章编号：2096-4706（2024）15-0065-04
A Fast Detection Method for Geospatial Network Subset
WU Zhihui
（Guangzhou Urban Planning Survey， Design and Research Institute， Guangzhou 510060， China）
Abstract： Aiming at the problem of low detection efficiency of geospatial network subsets under big data， this paper proposes a fast detection method for geospatial network subsets by introducing two index tables of “arc to point” and “point to arc”. This method innovatively realizes the search and positioning of arcs and points directly through the two index tables， avoids the inefficiency caused by excessive search calculation redundancy in traditional subset detection methods， and significantly improves the calculated efficiency of geospatial network subset detection. The Delaunay Triangulation network containing different numbers of random points is simulated and generated by MATLAB software， and the subset detection is carried out by using the proposed method in this paper and the traditional method. The results show that both methods can achieve successful subset detection， but the method proposed in this paper significantly improves the efficiency of subset detection.
Keywords： geospatial network; subset detection; index table
0 引 言
随着技术和理论科学的发展，地理空间数据越来越趋向于多元化[1]。尤其在测绘、遥感、地理信息科学、国土、交通等领域中[2-10]，地理空间数据不仅涉及点、线、面等基础几何图形，还涉及点与点之间、线与线、面与面之间的几何网络拓扑关系。例如，日常生活常用的地图数据最基本的图件包括点（目标当前的位置）、线（位置之间的连线，如道路、构建筑物边界）和面（连线形成的面，如构建筑物的区域范围）。除此之外，基本图件相互组合也会形成地理空间网络。例如，道路网可以认为是由线将关键节点连接，最终形成一个巨大的二维地理空间网络，进而为日常生活生活（如交通、运输等）提供可靠的基础数据。同时，在测绘遥感领域中，在进行数据处理之前，有时需要首先基于海量目标点建立狄洛尼三角网（即地理空间网络），针对三角网中的顶点之间的连线（弧段）进行参数解算，最后针对弧段上的参数进行空间积分，进而得到所有点上的结果。在地理信息数据挖掘过程中，空间上的点、线、面等基础元素往往也需要通过一定的数学范式进行聚类分析，其中道路网会作为一个重要数据源进行辅助分析和解算。上述应用和数据处理过程的前提往往是需要相应的地理空间网络是一个完整的、连通的网络，然而实际情况中，相应的地理空间网络可能会存在子集，进而影响后续数据处理。例如，在测绘遥感领域中，InSAR（合成孔径雷达干涉测量）高相干点往往是通过构建一个完整的地理空间网络进行数据处理，针对网络中两点之间的连线进行参数解算，解算完成后需要剔除参数解算结果可靠性较低的弧段[11-14]，进而原有的完整地理空间网络可能会包含若干子集，即无法通过某一目标点和最终的网络遍历到所有的InSAR高相干点，严重影响后期的数据处理。在地理信息数据挖掘领域中，将道路网作为辅助数据进行计算时，需要首先进行数据清洗以提高地理大数据情况下的计算效率。然而，数据清洗之后，其原始的道路网会出现中断、缺失、重复等空间逻辑错误，使得原始完整的道路网形成了多个子集，进而极大影响了地理信息工作者的数据挖掘效率及可靠性。
传统方法在进行地理空间网络子集探测时的基本思想如下[11]：输入数据为每一个弧段两个端点的序号索引，即大小为M×2的矩阵A，每一行代表一个弧段的两个端点对应的索引。对于完整的、连通的狄洛尼三角网，基于序号索引即可实现从任意点出发到达网络内的所有点。例如，设定序号为1的网络顶点为种子点，在序号索引矩阵A中搜索包含序号1的弧段，假设共有3个弧段包含端点1，则将这3个弧段的另外3个的端点（非端点1）作为种子点，将端点1标记为已搜索过的点，将这3个弧段标记为已搜索过的弧段，再在矩阵A中搜索与这3个种子点相连的其他端点，假设此时有7个弧段包含这3个种子点（不包含已搜索过的3个弧段），此时将这7个弧段的另外7个端点作为种子点，将之前的3个种子点标记为已搜索过的点，将这7个弧段标记为已搜索过的弧段，重复这一过程，直至没有新的弧段与种子点相连，此时标记过的弧段和端点即位同一个子集，并将相关弧段和子集进行标记。如若当前子集并未包括网络中的所有端点，则以子集外的任意一个端点为种子点，重复上述过程直至所有端点均进行了标记。基于上述过程即可实现整个网络的不同子集标记与探测，进而可进行后续的参数解算或者拓扑结构分析。
然而，随着地理空间数据量不断变大，上述序号索引矩阵A所包含的弧段数可达数亿个，因此传统方法需要每次在矩阵A中查找对应的端点序号，其计算冗余度非常大（每次都需要从数亿行矩阵中查找种子点的位置），效率极低，进而极大地影响了后续的计算分析过程。基于此，本文提出了一种地理空间网络子集探测方法，通过建立“点到弧段”和“弧段到点”的两个索引表，直接通过两个索引表中的序号索引即可定位到相应的弧段或端点，有效避免计算机搜索查找过程中的冗余计算，显著提高了子集探测的计算效率，进而为后续计算分析提供了可靠保障。
1 探测方法
如图1所示，黑色端点即为地理空间网络中的端点，端点之间的连线即为狄洛尼三角网中两点之间的弧段，灰色弧段和蓝色弧段组成了原始的完整的地理空间网络。然而，在数据处理过程中，灰色弧段可能因为可靠性较低、数据遗失等原因无法被用于后续分析，而剩下的蓝色弧段则组成了4个子集。本文提出的地理空间网络子集探测方法其目的即为赋予四个蓝色弧段子集不同的标签，以示区别。在子集探测之前需要首先对所有的顶点和弧段进行编号，进而建立“弧段到点”和“点到弧段”两个索引表。
图1 地理空间网络及其子集示意图
图2给出了地理空间网络中端点和弧段之间连接的示意图，其中蓝色圆圈表示端点，圆圈内的数字表示端点序号，红色线段表示弧段，线段旁的数字表示弧段序号。在该地理空间网络中，9个端点（蓝色圆圈）之间通过构建狄洛尼三角网共得到了17条弧段（红色线段）。根据端点与弧段之间的连接关系，可直接建立“弧段到点”和“点到弧段”的两个索引表（如表1、表2所示）。在“弧段到点”的索引表中，我们得到的是一个M×2的矩阵（M表示总的弧段数），矩阵的行索引m即表示第m个弧段（m=1，2，3，…，M），第m行两个元素所对应的数值表示第m个弧段两个端点的序号，这里的端点序号与“点到弧段”索引表中的端点索引序号的相对应的。在“点到弧段”的索引表中，我们得到的是N×1的cell数据（cell表示MATLAB中的变量格式，N表示总的端点数），cell的索引n即表示第n个端点（n=1，2，3，…，N），第n个cell中包含一个一维数组，数组中的每一个元素数值表示与第n个端点相连的弧段序号，这里的弧段序号与“弧段到点”索引表中的弧段索引序号是相对应的。基于“弧段到点”和“点到弧段”这两个索引表，在查询与某端点连接的弧段或者与某弧段连接的端点时，就无须在一系列弧段端点中反复的查询某一个端点的位置，直接通过两个索引表的行索引或者cell索引实现快速定位查找，进而显著提升整个地理空间网络子集的探测效率，为后续计算分析提供可靠保障。
为了使读者更好地理解本文方法，下面将介绍如何基于“弧段到点”和“点到弧段“两个索引表实现子集探测。假如以端点1为第一个种子点，则基于表2可快速查询到与端点1相连的弧段序号。如表2所示，与端点1连接的弧段序号有1，2，3，此时在表1中取出第1，2，3行（即第1，2，3弧段），进而可以得到与端点1相连的弧段另一端点的序号为1，2，4，5，将端点2，4，5和弧段1，2，3并将这些子种子点赋予与端点1相同的标签，并将与端点1相连的所有弧段的另一端点2，4，5分别作为子种子点，通过表2可得到与端点2，4，5相连的弧段（表2中的第2，4，5个cell）分别有弧段2/4/5、1/9/10/17和3/4/6/8/10/11，由于弧段1/2/3已经被赋予了标签，则此时只进一步分析剩余的弧段，即弧段4/5/6/8/9/10/11/17，将这些弧段赋予标签之后，根据这些弧段编号，则可从表1中查询出对应弧段（弧段序号即为索引表1中的行号）所包含的端点，将这些端点中尚未赋予标签的端点作为子种子点，同时将这些子种子点赋予标签，则可依次、反复基于表1和2得到与端点1相连的弧段和端点。查询停止条件为：通过弧段与所有的子种子点连接的另一端点都已经被赋予了标签，则此时便完成了第一个子集的遍历。
然后以未被赋予标签的某一个端点作为第二个种子点，基于上述步骤完成第二个子集的遍历；
重复上述过程，直至所有顶点均被赋予了标签，此时相同标签的顶点即为同一个连通的子集，进而实现了地理空间网络子集快速探测。
2 方法验证
为了验证本文方法，我们使用MATLAB软件开展了相关编程实验。首先，使用函数rand随机产生了6 000个空间二维点的（x，y）坐标，利用MATLAB函数delaunayTriangulation并生成狄洛尼三角网。如图3（a）所示，蓝色线段表示狄洛尼三角网的弧段，线段的端点即为6 000个空间随机点的位置。进一步，人为剔除了狄洛尼三角网中的部分弧段，使得原有完整的空间网络形成9个独立子集（图3（b）中的浅蓝色线段）。在利用本文方法对图3（b）进行子集探测之前，需要根据表1中的规则建立“弧段到点”和“点到弧段”两个索引表，然后利用本文提出的索引表使用方法对输入的网络进行子集探测。如图3（c）所示，不同散点颜色代表不同的子集，且不同子集的空间分布与图3（b）中输入的子集数据完全一致，说明本文方法可以非常准确地识别出9个子集。此外，地理空间网络数据处理过程中的效率对于研究工作和实际应用至关重要。本文提出的子集探测方法，在6 000个随机点的网络探测过程中用时仅为0.02秒。当随机点增加到60万个时，本文方法的子集探测用时也仅为1.6秒。为了对比本文方法在计算效率上的优势，本文同样使用了传统方法进行图3（b）网络的子集探测，结果表明传统方法在6 000个点的时候用时为1.8秒，在60万个点的时候用时为2 540秒。可以看出，当空间网络中点越多时，本文方法的效率优势越为明显。因此，在相关地理网络分析中展示出了极大的优势和潜力。相关实验所使用的计算机配置如下：苹果笔记本M1 Pro，系统版本v13.2.1，16 GB内存，1 TB硬盘，MATLABR2022b。
3 结 论
地理空间数据的广泛应用极大便利和丰富了日常生活和科学研究，然而大数据情况下的地理信息数据也不断趋于复杂化，其体现在拓扑关系的复杂化、数据种类的复杂化以及应用实践的复杂化。其中地理空间数据网络是应对上述问题的有效途径之一，而其中的网络子网探测是网络应用的关键步骤之一。基于此，本文提出了一种地理空间网络子集快速探测方法，通过引入“弧段到点”和“点到弧段”两个索引表，避免了传统子集探测方法中因查找搜索计算冗余度过高导致的效率低下问题，显著提升了地理空间网络子集探测的计算效率。并且，通过利用MATLAB编程实现和验证了该算法。本文首先生成了包含6 000个点和60万个点的狄洛尼三角网，并手动剔除了部分网络连接以形成独立的子集。在此基础上，利用本文方法和传统子集探测方法进行了子集探测。结果表明，本文方法在两种不同数量级网络的子集探测过程中均可实现秒级的探测效率，而对于传统方法，当网络中包含较多点时，其子集探测效率显著降低，因此验证了本文方法在地理空间网络中子集探测的计算效率优势，可为后续的计算分析提供可靠保障。
参考文献：
[1] 黎坚.基础地理信息数据处理关键技术的研究与应用 [J].现代信息科技，2020，4（13）：28-29+32.
[2] 王钺，周鹏辉，潘海泽，等.路网形态与住宅价格的多尺度空间关系研究——基于空间网络分析与多尺度地理加权回归模型 [J].地理与地理信息科学，2022，38（1）：103-109.
[3] 王玉秋，张国强.交通运输网络规划的地理空间视角 [J].综合运输，2016，38（12）：78-81.
[4] 赵红伟，诸云强，侯志伟，等.地理空间元数据关联网络的构建 [J].地理科学，2016，36（8）：1180-1189.
[5] 吕雪锋，程承旗，席福彪.地理空间大数据存储管理的地理网络地址研究 [J].地理与地理信息科学，2015，31（1）：1-5.
[6] 李凯锋，吕志平，石善斌，等.网络导航中基于SVG的地理空间数据组织与传输 [J].测绘工程，2008（5）：8-11.
[7] 汪诗峰.空间网络分析关键技术研究 [D].北京：中国科学院研究生院（遥感应用研究所），2006.
[8] 张铭晓.基于道路网络中心性分析的医疗空间可达性研究 [D].武汉：武汉大学，2016.
[9] 许志海.空间网络图的表示、量测与分析 [D].郑州：解放军信息工程大学，2007.
[10] 马红利，许文婧，左飞航.陕西西咸新区交通网络空间格局通达性研究 [J].测绘技术装备，2022，24（1）：12-16.
[11] ZHANG L，DING X，LU Z. Modeling Psinsar Time Series Without Phase Unwrapping [J].IEEE Transactions on Geoscience and Remote Sensing，2011，49（1）：547-556.
[12] 张通德，冯晓，党升.基于PSInSAR的成都地区地表沉降空间分布研究 [J].北京测绘，2022，36（1）：74-77.
[13] 刘佳斌，徐卓揆，何伟.基于PSInSAR的水溶矿区沉降预测 [J].地理空间信息，2020，18（7）：103-105+130+8.
[14] 王寅珂.PSInSAR技术在地面沉降监测中的应用研究 [J].测绘与空间地理信息，2020，43（4）：209-213.
作者简介：吴智慧（1995—），女，汉族，河南商丘人，助理工程师，硕士研究生，研究方向：时空大数据挖掘。
