摘 要：針對(duì)大數(shù)據(jù)下地理空間網(wǎng)絡(luò)子集探測(cè)效率較低的問題，文章通過引入“弧段到點(diǎn)”和“點(diǎn)到弧段”兩個(gè)索引表，提出了一種地理空間網(wǎng)絡(luò)子集快速探測(cè)方法。該方法創(chuàng)新性地通過兩個(gè)索引表直接實(shí)現(xiàn)了弧段和端點(diǎn)的查找定位，避免了傳統(tǒng)子集探測(cè)方法中因查找搜索計(jì)算冗余度過高導(dǎo)致的效率低下問題，顯著提升了地理空間網(wǎng)絡(luò)子集探測(cè)的計(jì)算效率。通過MATLAB軟件模擬生成了包含不同數(shù)量隨機(jī)點(diǎn)的狄洛尼三角網(wǎng)，利用該方法和傳統(tǒng)方法分別進(jìn)行了子集探測(cè)。結(jié)果表明，兩種方法均可實(shí)現(xiàn)子集的成功探測(cè)，但是該方法顯著改善了子集探測(cè)效率。

關(guān)鍵詞：地理空間網(wǎng)絡(luò)；子集探測(cè)；索引表

中圖分類號(hào)：TP39；TP208 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引 言

隨著技術(shù)和理論科學(xué)的發(fā)展，地理空間數(shù)據(jù)越來越趨向于多元化[1]。尤其在測(cè)繪、遙感、地理信息科學(xué)、國土、交通等領(lǐng)域中[2-10]，地理空間數(shù)據(jù)不僅涉及點(diǎn)、線、面等基礎(chǔ)幾何圖形，還涉及點(diǎn)與點(diǎn)之間、線與線、面與面之間的幾何網(wǎng)絡(luò)拓?fù)潢P(guān)系。例如，日常生活常用的地圖數(shù)據(jù)最基本的圖件包括點(diǎn)（目標(biāo)當(dāng)前的位置）、線（位置之間的連線，如道路、構(gòu)建筑物邊界）和面（連線形成的面，如構(gòu)建筑物的區(qū)域范圍）。除此之外，基本圖件相互組合也會(huì)形成地理空間網(wǎng)絡(luò)。例如，道路網(wǎng)可以認(rèn)為是由線將關(guān)鍵節(jié)點(diǎn)連接，最終形成一個(gè)巨大的二維地理空間網(wǎng)絡(luò)，進(jìn)而為日常生活生活（如交通、運(yùn)輸?shù)龋┨峁┛煽康幕A(chǔ)數(shù)據(jù)。同時(shí)，在測(cè)繪遙感領(lǐng)域中，在進(jìn)行數(shù)據(jù)處理之前，有時(shí)需要首先基于海量目標(biāo)點(diǎn)建立狄洛尼三角網(wǎng)（即地理空間網(wǎng)絡(luò)），針對(duì)三角網(wǎng)中的頂點(diǎn)之間的連線（弧段）進(jìn)行參數(shù)解算，最后針對(duì)弧段上的參數(shù)進(jìn)行空間積分，進(jìn)而得到所有點(diǎn)上的結(jié)果。在地理信息數(shù)據(jù)挖掘過程中，空間上的點(diǎn)、線、面等基礎(chǔ)元素往往也需要通過一定的數(shù)學(xué)范式進(jìn)行聚類分析，其中道路網(wǎng)會(huì)作為一個(gè)重要數(shù)據(jù)源進(jìn)行輔助分析和解算。上述應(yīng)用和數(shù)據(jù)處理過程的前提往往是需要相應(yīng)的地理空間網(wǎng)絡(luò)是一個(gè)完整的、連通的網(wǎng)絡(luò)，然而實(shí)際情況中，相應(yīng)的地理空間網(wǎng)絡(luò)可能會(huì)存在子集，進(jìn)而影響后續(xù)數(shù)據(jù)處理。例如，在測(cè)繪遙感領(lǐng)域中，InSAR（合成孔徑雷達(dá)干涉測(cè)量）高相干點(diǎn)往往是通過構(gòu)建一個(gè)完整的地理空間網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)處理，針對(duì)網(wǎng)絡(luò)中兩點(diǎn)之間的連線進(jìn)行參數(shù)解算，解算完成后需要剔除參數(shù)解算結(jié)果可靠性較低的弧段[11-14]，進(jìn)而原有的完整地理空間網(wǎng)絡(luò)可能會(huì)包含若干子集，即無法通過某一目標(biāo)點(diǎn)和最終的網(wǎng)絡(luò)遍歷到所有的InSAR高相干點(diǎn)，嚴(yán)重影響后期的數(shù)據(jù)處理。在地理信息數(shù)據(jù)挖掘領(lǐng)域中，將道路網(wǎng)作為輔助數(shù)據(jù)進(jìn)行計(jì)算時(shí)，需要首先進(jìn)行數(shù)據(jù)清洗以提高地理大數(shù)據(jù)情況下的計(jì)算效率。然而，數(shù)據(jù)清洗之后，其原始的道路網(wǎng)會(huì)出現(xiàn)中斷、缺失、重復(fù)等空間邏輯錯(cuò)誤，使得原始完整的道路網(wǎng)形成了多個(gè)子集，進(jìn)而極大影響了地理信息工作者的數(shù)據(jù)挖掘效率及可靠性。

傳統(tǒng)方法在進(jìn)行地理空間網(wǎng)絡(luò)子集探測(cè)時(shí)的基本思想如下[11]：輸入數(shù)據(jù)為每一個(gè)弧段兩個(gè)端點(diǎn)的序號(hào)索引，即大小為M×2的矩陣A，每一行代表一個(gè)弧段的兩個(gè)端點(diǎn)對(duì)應(yīng)的索引。對(duì)于完整的、連通的狄洛尼三角網(wǎng)，基于序號(hào)索引即可實(shí)現(xiàn)從任意點(diǎn)出發(fā)到達(dá)網(wǎng)絡(luò)內(nèi)的所有點(diǎn)。例如，設(shè)定序號(hào)為1的網(wǎng)絡(luò)頂點(diǎn)為種子點(diǎn)，在序號(hào)索引矩陣A中搜索包含序號(hào)1的弧段，假設(shè)共有3個(gè)弧段包含端點(diǎn)1，則將這3個(gè)弧段的另外3個(gè)的端點(diǎn)（非端點(diǎn)1）作為種子點(diǎn)，將端點(diǎn)1標(biāo)記為已搜索過的點(diǎn)，將這3個(gè)弧段標(biāo)記為已搜索過的弧段，再在矩陣A中搜索與這3個(gè)種子點(diǎn)相連的其他端點(diǎn)，假設(shè)此時(shí)有7個(gè)弧段包含這3個(gè)種子點(diǎn)（不包含已搜索過的3個(gè)弧段），此時(shí)將這7個(gè)弧段的另外7個(gè)端點(diǎn)作為種子點(diǎn)，將之前的3個(gè)種子點(diǎn)標(biāo)記為已搜索過的點(diǎn)，將這7個(gè)弧段標(biāo)記為已搜索過的弧段，重復(fù)這一過程，直至沒有新的弧段與種子點(diǎn)相連，此時(shí)標(biāo)記過的弧段和端點(diǎn)即位同一個(gè)子集，并將相關(guān)弧段和子集進(jìn)行標(biāo)記。如若當(dāng)前子集并未包括網(wǎng)絡(luò)中的所有端點(diǎn)，則以子集外的任意一個(gè)端點(diǎn)為種子點(diǎn)，重復(fù)上述過程直至所有端點(diǎn)均進(jìn)行了標(biāo)記?；谏鲜鲞^程即可實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的不同子集標(biāo)記與探測(cè)，進(jìn)而可進(jìn)行后續(xù)的參數(shù)解算或者拓?fù)浣Y(jié)構(gòu)分析。

然而，隨著地理空間數(shù)據(jù)量不斷變大，上述序號(hào)索引矩陣A所包含的弧段數(shù)可達(dá)數(shù)億個(gè)，因此傳統(tǒng)方法需要每次在矩陣A中查找對(duì)應(yīng)的端點(diǎn)序號(hào)，其計(jì)算冗余度非常大（每次都需要從數(shù)億行矩陣中查找種子點(diǎn)的位置），效率極低，進(jìn)而極大地影響了后續(xù)的計(jì)算分析過程。基于此，本文提出了一種地理空間網(wǎng)絡(luò)子集探測(cè)方法，通過建立“點(diǎn)到弧段”和“弧段到點(diǎn)”的兩個(gè)索引表，直接通過兩個(gè)索引表中的序號(hào)索引即可定位到相應(yīng)的弧段或端點(diǎn)，有效避免計(jì)算機(jī)搜索查找過程中的冗余計(jì)算，顯著提高了子集探測(cè)的計(jì)算效率，進(jìn)而為后續(xù)計(jì)算分析提供了可靠保障。

1 探測(cè)方法

如圖1所示，黑色端點(diǎn)即為地理空間網(wǎng)絡(luò)中的端點(diǎn)，端點(diǎn)之間的連線即為狄洛尼三角網(wǎng)中兩點(diǎn)之間的弧段，灰色弧段和藍(lán)色弧段組成了原始的完整的地理空間網(wǎng)絡(luò)。然而，在數(shù)據(jù)處理過程中，灰色弧段可能因?yàn)榭煽啃暂^低、數(shù)據(jù)遺失等原因無法被用于后續(xù)分析，而剩下的藍(lán)色弧段則組成了4個(gè)子集。本文提出的地理空間網(wǎng)絡(luò)子集探測(cè)方法其目的即為賦予四個(gè)藍(lán)色弧段子集不同的標(biāo)簽，以示區(qū)別。在子集探測(cè)之前需要首先對(duì)所有的頂點(diǎn)和弧段進(jìn)行編號(hào)，進(jìn)而建立“弧段到點(diǎn)”和“點(diǎn)到弧段”兩個(gè)索引表。

圖1 地理空間網(wǎng)絡(luò)及其子集示意圖

圖2給出了地理空間網(wǎng)絡(luò)中端點(diǎn)和弧段之間連接的示意圖，其中藍(lán)色圓圈表示端點(diǎn)，圓圈內(nèi)的數(shù)字表示端點(diǎn)序號(hào)，紅色線段表示弧段，線段旁的數(shù)字表示弧段序號(hào)。在該地理空間網(wǎng)絡(luò)中，9個(gè)端點(diǎn)（藍(lán)色圓圈）之間通過構(gòu)建狄洛尼三角網(wǎng)共得到了17條弧段（紅色線段）。根據(jù)端點(diǎn)與弧段之間的連接關(guān)系，可直接建立“弧段到點(diǎn)”和“點(diǎn)到弧段”的兩個(gè)索引表（如表1、表2所示）。在“弧段到點(diǎn)”的索引表中，我們得到的是一個(gè)M×2的矩陣（M表示總的弧段數(shù)），矩陣的行索引m即表示第m個(gè)弧段（m=1，2，3，…，M），第m行兩個(gè)元素所對(duì)應(yīng)的數(shù)值表示第m個(gè)弧段兩個(gè)端點(diǎn)的序號(hào)，這里的端點(diǎn)序號(hào)與“點(diǎn)到弧段”索引表中的端點(diǎn)索引序號(hào)的相對(duì)應(yīng)的。在“點(diǎn)到弧段”的索引表中，我們得到的是N×1的cell數(shù)據(jù)（cell表示MATLAB中的變量格式，N表示總的端點(diǎn)數(shù)），cell的索引n即表示第n個(gè)端點(diǎn)（n=1，2，3，…，N），第n個(gè)cell中包含一個(gè)一維數(shù)組，數(shù)組中的每一個(gè)元素?cái)?shù)值表示與第n個(gè)端點(diǎn)相連的弧段序號(hào)，這里的弧段序號(hào)與“弧段到點(diǎn)”索引表中的弧段索引序號(hào)是相對(duì)應(yīng)的?；凇盎《蔚近c(diǎn)”和“點(diǎn)到弧段”這兩個(gè)索引表，在查詢與某端點(diǎn)連接的弧段或者與某弧段連接的端點(diǎn)時(shí)，就無須在一系列弧段端點(diǎn)中反復(fù)的查詢某一個(gè)端點(diǎn)的位置，直接通過兩個(gè)索引表的行索引或者cell索引實(shí)現(xiàn)快速定位查找，進(jìn)而顯著提升整個(gè)地理空間網(wǎng)絡(luò)子集的探測(cè)效率，為后續(xù)計(jì)算分析提供可靠保障。

為了使讀者更好地理解本文方法，下面將介紹如何基于“弧段到點(diǎn)”和“點(diǎn)到弧段“兩個(gè)索引表實(shí)現(xiàn)子集探測(cè)。假如以端點(diǎn)1為第一個(gè)種子點(diǎn)，則基于表2可快速查詢到與端點(diǎn)1相連的弧段序號(hào)。如表2所示，與端點(diǎn)1連接的弧段序號(hào)有1，2，3，此時(shí)在表1中取出第1，2，3行（即第1，2，3弧段），進(jìn)而可以得到與端點(diǎn)1相連的弧段另一端點(diǎn)的序號(hào)為1，2，4，5，將端點(diǎn)2，4，5和弧段1，2，3并將這些子種子點(diǎn)賦予與端點(diǎn)1相同的標(biāo)簽，并將與端點(diǎn)1相連的所有弧段的另一端點(diǎn)2，4，5分別作為子種子點(diǎn)，通過表2可得到與端點(diǎn)2，4，5相連的弧段（表2中的第2，4，5個(gè)cell）分別有弧段2/4/5、1/9/10/17和3/4/6/8/10/11，由于弧段1/2/3已經(jīng)被賦予了標(biāo)簽，則此時(shí)只進(jìn)一步分析剩余的弧段，即弧段4/5/6/8/9/10/11/17，將這些弧段賦予標(biāo)簽之后，根據(jù)這些弧段編號(hào)，則可從表1中查詢出對(duì)應(yīng)弧段（弧段序號(hào)即為索引表1中的行號(hào)）所包含的端點(diǎn)，將這些端點(diǎn)中尚未賦予標(biāo)簽的端點(diǎn)作為子種子點(diǎn)，同時(shí)將這些子種子點(diǎn)賦予標(biāo)簽，則可依次、反復(fù)基于表1和2得到與端點(diǎn)1相連的弧段和端點(diǎn)。查詢停止條件為：通過弧段與所有的子種子點(diǎn)連接的另一端點(diǎn)都已經(jīng)被賦予了標(biāo)簽，則此時(shí)便完成了第一個(gè)子集的遍歷。

然后以未被賦予標(biāo)簽的某一個(gè)端點(diǎn)作為第二個(gè)種子點(diǎn)，基于上述步驟完成第二個(gè)子集的遍歷；

重復(fù)上述過程，直至所有頂點(diǎn)均被賦予了標(biāo)簽，此時(shí)相同標(biāo)簽的頂點(diǎn)即為同一個(gè)連通的子集，進(jìn)而實(shí)現(xiàn)了地理空間網(wǎng)絡(luò)子集快速探測(cè)。

2 方法驗(yàn)證

為了驗(yàn)證本文方法，我們使用MATLAB軟件開展了相關(guān)編程實(shí)驗(yàn)。首先，使用函數(shù)rand隨機(jī)產(chǎn)生了6 000個(gè)空間二維點(diǎn)的（x，y）坐標(biāo)，利用MATLAB函數(shù)delaunayTriangulation并生成狄洛尼三角網(wǎng)。如圖3（a）所示，藍(lán)色線段表示狄洛尼三角網(wǎng)的弧段，線段的端點(diǎn)即為6 000個(gè)空間隨機(jī)點(diǎn)的位置。進(jìn)一步，人為剔除了狄洛尼三角網(wǎng)中的部分弧段，使得原有完整的空間網(wǎng)絡(luò)形成9個(gè)獨(dú)立子集（圖3（b）中的淺藍(lán)色線段）。在利用本文方法對(duì)圖3（b）進(jìn)行子集探測(cè)之前，需要根據(jù)表1中的規(guī)則建立“弧段到點(diǎn)”和“點(diǎn)到弧段”兩個(gè)索引表，然后利用本文提出的索引表使用方法對(duì)輸入的網(wǎng)絡(luò)進(jìn)行子集探測(cè)。如圖3（c）所示，不同散點(diǎn)顏色代表不同的子集，且不同子集的空間分布與圖3（b）中輸入的子集數(shù)據(jù)完全一致，說明本文方法可以非常準(zhǔn)確地識(shí)別出9個(gè)子集。此外，地理空間網(wǎng)絡(luò)數(shù)據(jù)處理過程中的效率對(duì)于研究工作和實(shí)際應(yīng)用至關(guān)重要。本文提出的子集探測(cè)方法，在6 000個(gè)隨機(jī)點(diǎn)的網(wǎng)絡(luò)探測(cè)過程中用時(shí)僅為0.02秒。當(dāng)隨機(jī)點(diǎn)增加到60萬個(gè)時(shí)，本文方法的子集探測(cè)用時(shí)也僅為1.6秒。為了對(duì)比本文方法在計(jì)算效率上的優(yōu)勢(shì)，本文同樣使用了傳統(tǒng)方法進(jìn)行圖3（b）網(wǎng)絡(luò)的子集探測(cè)，結(jié)果表明傳統(tǒng)方法在6 000個(gè)點(diǎn)的時(shí)候用時(shí)為1.8秒，在60萬個(gè)點(diǎn)的時(shí)候用時(shí)為2 540秒。可以看出，當(dāng)空間網(wǎng)絡(luò)中點(diǎn)越多時(shí)，本文方法的效率優(yōu)勢(shì)越為明顯。因此，在相關(guān)地理網(wǎng)絡(luò)分析中展示出了極大的優(yōu)勢(shì)和潛力。相關(guān)實(shí)驗(yàn)所使用的計(jì)算機(jī)配置如下：蘋果筆記本M1 Pro，系統(tǒng)版本v13.2.1，16 GB內(nèi)存，1 TB硬盤，MATLABR2022b。

3 結(jié) 論

地理空間數(shù)據(jù)的廣泛應(yīng)用極大便利和豐富了日常生活和科學(xué)研究，然而大數(shù)據(jù)情況下的地理信息數(shù)據(jù)也不斷趨于復(fù)雜化，其體現(xiàn)在拓?fù)潢P(guān)系的復(fù)雜化、數(shù)據(jù)種類的復(fù)雜化以及應(yīng)用實(shí)踐的復(fù)雜化。其中地理空間數(shù)據(jù)網(wǎng)絡(luò)是應(yīng)對(duì)上述問題的有效途徑之一，而其中的網(wǎng)絡(luò)子網(wǎng)探測(cè)是網(wǎng)絡(luò)應(yīng)用的關(guān)鍵步驟之一?；诖?，本文提出了一種地理空間網(wǎng)絡(luò)子集快速探測(cè)方法，通過引入“弧段到點(diǎn)”和“點(diǎn)到弧段”兩個(gè)索引表，避免了傳統(tǒng)子集探測(cè)方法中因查找搜索計(jì)算冗余度過高導(dǎo)致的效率低下問題，顯著提升了地理空間網(wǎng)絡(luò)子集探測(cè)的計(jì)算效率。并且，通過利用MATLAB編程實(shí)現(xiàn)和驗(yàn)證了該算法。本文首先生成了包含6 000個(gè)點(diǎn)和60萬個(gè)點(diǎn)的狄洛尼三角網(wǎng)，并手動(dòng)剔除了部分網(wǎng)絡(luò)連接以形成獨(dú)立的子集。在此基礎(chǔ)上，利用本文方法和傳統(tǒng)子集探測(cè)方法進(jìn)行了子集探測(cè)。結(jié)果表明，本文方法在兩種不同數(shù)量級(jí)網(wǎng)絡(luò)的子集探測(cè)過程中均可實(shí)現(xiàn)秒級(jí)的探測(cè)效率，而對(duì)于傳統(tǒng)方法，當(dāng)網(wǎng)絡(luò)中包含較多點(diǎn)時(shí)，其子集探測(cè)效率顯著降低，因此驗(yàn)證了本文方法在地理空間網(wǎng)絡(luò)中子集探測(cè)的計(jì)算效率優(yōu)勢(shì)，可為后續(xù)的計(jì)算分析提供可靠保障。

參考文獻(xiàn)：

[1] 黎堅(jiān).基礎(chǔ)地理信息數(shù)據(jù)處理關(guān)鍵技術(shù)的研究與應(yīng)用 [J].現(xiàn)代信息科技，2020，4（13）：28-29+32.

[2] 王鉞，周鵬輝，潘海澤，等.路網(wǎng)形態(tài)與住宅價(jià)格的多尺度空間關(guān)系研究——基于空間網(wǎng)絡(luò)分析與多尺度地理加權(quán)回歸模型 [J].地理與地理信息科學(xué)，2022，38（1）：103-109.

[3] 王玉秋，張國強(qiáng).交通運(yùn)輸網(wǎng)絡(luò)規(guī)劃的地理空間視角 [J].綜合運(yùn)輸，2016，38（12）：78-81.

[4] 趙紅偉，諸云強(qiáng)，侯志偉，等.地理空間元數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)的構(gòu)建 [J].地理科學(xué)，2016，36（8）：1180-1189.

[5] 呂雪鋒，程承旗，席福彪.地理空間大數(shù)據(jù)存儲(chǔ)管理的地理網(wǎng)絡(luò)地址研究 [J].地理與地理信息科學(xué)，2015，31（1）：1-5.

[6] 李凱鋒，呂志平，石善斌，等.網(wǎng)絡(luò)導(dǎo)航中基于SVG的地理空間數(shù)據(jù)組織與傳輸 [J].測(cè)繪工程，2008（5）：8-11.

[7] 汪詩峰.空間網(wǎng)絡(luò)分析關(guān)鍵技術(shù)研究 [D].北京：中國科學(xué)院研究生院（遙感應(yīng)用研究所），2006.

[8] 張銘曉.基于道路網(wǎng)絡(luò)中心性分析的醫(yī)療空間可達(dá)性研究 [D].武漢：武漢大學(xué)，2016.

[9] 許志海.空間網(wǎng)絡(luò)圖的表示、量測(cè)與分析 [D].鄭州：解放軍信息工程大學(xué)，2007.

[10] 馬紅利，許文婧，左飛航.陜西西咸新區(qū)交通網(wǎng)絡(luò)空間格局通達(dá)性研究 [J].測(cè)繪技術(shù)裝備，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的成都地區(qū)地表沉降空間分布研究 [J].北京測(cè)繪，2022，36（1）：74-77.

[13] 劉佳斌，徐卓揆，何偉.基于PSInSAR的水溶礦區(qū)沉降預(yù)測(cè) [J].地理空間信息，2020，18（7）：103-105+130+8.

[14] 王寅珂.PSInSAR技術(shù)在地面沉降監(jiān)測(cè)中的應(yīng)用研究 [J].測(cè)繪與空間地理信息，2020，43（4）：209-213.

作者簡介：吳智慧（1995—），女，漢族，河南商丘人，助理工程師，碩士研究生，研究方向：時(shí)空大數(shù)據(jù)挖掘。