侯凱宇，徐景，鄭衡，李佑林，周鈺笛，李智文

長沙市規(guī)劃勘測設(shè)計研究院, 長沙 410000

1 引 言

在測繪地理信息、城市規(guī)劃等行業(yè)，經(jīng)常需要在某一個封閉區(qū)域構(gòu)建面要素（伍梅等，2005；梁晨等，2019)。例如，在控制性詳細(xì)規(guī)劃編制過程中，需要在路網(wǎng)合圍區(qū)域繪制用地地塊，人工繪制費(fèi)時費(fèi)力，迫切需要一種自動識別封閉區(qū)域并繪制面要素的方法。

封閉區(qū)域識別本質(zhì)上是計算機(jī)數(shù)據(jù)結(jié)構(gòu)中圖的閉合回路搜索問題（Du 等，2020；曹嘉琛和楊武東，2022)。圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，分為有向圖（倪文輝等，2018；金恒旭等，2022；崔建明等，2023)和無向圖（胡榮明等，2014；張傲，2021；王國良和任雪玉，2023)。有向圖表示連接兩點(diǎn)的線有方向；無向圖表示連接兩點(diǎn)的線沒有方向，封閉區(qū)域識別不需要方向。傳統(tǒng)的閉合回路搜索算法有深度優(yōu)先搜索和廣度優(yōu)先搜索，這兩種算法原本的目的是遍歷全圖和尋找最短路徑。劉旭（2017)為了解決經(jīng)典正方化樹圖布局算法無法獲得平均長寬比最優(yōu)結(jié)果的問題，結(jié)合深度優(yōu)先搜索技術(shù)，提出了基于深度優(yōu)先搜索（depth first search，DFS)的正方化樹圖布局算法。楊雅涵（2021)針對聯(lián)鎖系統(tǒng)辦理進(jìn)路功能中存在的通用性較差、搜索效率較低等問題，提出了以深度優(yōu)先搜索算法為基礎(chǔ)的進(jìn)路搜索方法，減少程序調(diào)試的過程，進(jìn)而提高搜索程序的安全性與可靠性。曹嘉琛和楊武東（2022)為了提高計算機(jī)聯(lián)鎖系統(tǒng)的效率，改進(jìn)傳統(tǒng)進(jìn)路搜索算法，提出了一種動態(tài)有向圖的站場數(shù)據(jù)結(jié)構(gòu)和改進(jìn)的深度優(yōu)先搜索算法。這些研究改進(jìn)了深度優(yōu)先搜索算法，優(yōu)化了圖的結(jié)構(gòu)或提高了圖的搜索效率，但搜索圖的節(jié)點(diǎn)時是無序的，搜索路線無法圍繞指定坐標(biāo)前進(jìn)。

本文研究一種封閉區(qū)域識別算法，只需要使用鼠標(biāo)點(diǎn)擊合圍區(qū)域即可識別包含鼠標(biāo)點(diǎn)擊位置的最小封閉區(qū)域。首先，以鼠標(biāo)點(diǎn)擊位置為基點(diǎn)建立緩沖區(qū)，將緩沖區(qū)內(nèi)的線和面在相交處打斷以構(gòu)建無向圖和鄰接表（殷茗等，2019)；其次，利用本文提出的改進(jìn)的深度優(yōu)先搜索算法搜索最小封閉區(qū)域，本文算法拓展了圖的鄰接表結(jié)構(gòu)，并使用旋轉(zhuǎn)角度控制鄰接點(diǎn)的訪問順序，實現(xiàn)了搜索路線始終圍繞指定坐標(biāo)前進(jìn)。

2 基于ArcGIS 對象模型構(gòu)建無向圖

ArcGIS Engine 是一個完整的嵌入式的GIS組件庫，可以用于構(gòu)建定制應(yīng)用（牟乃夏等，2015；蘭紅等，2019；黃立鑫等，2021)。封閉區(qū)域識別算法的輸入是任意的ArcGIS 線和面，輸出是封閉區(qū)域合圍形成的面。鄰接表中存儲了節(jié)點(diǎn)之間的ArcGIS 路徑信息，路徑由段組成，段是ArcGIS 最小的線單元，段可以是任意曲線。如果依次將封閉區(qū)域的路徑連接到一起，就可以在ArcGIS Engine 開發(fā)的軟件中構(gòu)建任意曲線組成的面。

2.1 無向圖

假設(shè)存在圖G=〈V,E〉，其中，V是非空集合，稱為節(jié)點(diǎn)集；E是V中元素構(gòu)成的二元組的集合，稱為邊集。如果邊沒有方向，則稱G是無向圖。圖的節(jié)點(diǎn)與節(jié)點(diǎn)之間是“多對多”的關(guān)系。在無向圖中，關(guān)聯(lián)一對節(jié)點(diǎn)的無向邊如果多于1 條，則稱這些邊為平行邊。既不含平行邊也不包含自環(huán)的圖，稱為簡單圖（黃競偉等，2000)，本文討論的是簡單無向圖（simple undirected graph，SUG)。如圖1所示，是一個含有4 個節(jié)點(diǎn)和4 條邊的簡單無向圖。節(jié)點(diǎn)與節(jié)點(diǎn)之間的連接關(guān)系可以存儲在鄰接矩陣或鄰接表中，本文選用鄰接表。鄰接表是單向鏈表的集合，鏈表的頭節(jié)點(diǎn)為圖的節(jié)點(diǎn)，鏈表的其他節(jié)點(diǎn)表示該節(jié)點(diǎn)連接的其他節(jié)點(diǎn)。例如，圖1 的鄰接表表示法，如圖2 所示。

圖1 簡單無向圖Fig.1 Simple undirected graph

圖2 鄰接表Fig.2 Adjacency list

2.2 擴(kuò)展鄰接表

本文構(gòu)建的圖屬于稀疏圖范疇，鄰接表表示稀疏圖比鄰接矩陣更加簡潔緊湊。在算法中，將鄰接表節(jié)點(diǎn)的結(jié)構(gòu)進(jìn)行擴(kuò)展，每個節(jié)點(diǎn)增加3 個屬性，P表示父節(jié)點(diǎn)，用于提取回路路徑；Color 表示節(jié)點(diǎn)顏色，用于標(biāo)識該節(jié)點(diǎn)是否已經(jīng)被訪問；M表示相遇點(diǎn)，用于判斷是否構(gòu)成封閉區(qū)域。

2.3 ArcGIS 線和面對象模型

以路徑為簡單無向圖的邊，以路徑的端點(diǎn)為圖的節(jié)點(diǎn)。路徑是連續(xù)的段的集合，段是線的最小組成單元；ArcGIS 中段有直線、圓弧、橢圓弧、貝澤爾曲線共四種。路徑是線和面的基本組成單元，線由路徑組成，面由閉合的路徑—— 環(huán)組成（圖3)。

圖3 ArcGIS 線和面的對象模型Fig.3 ArcGIS object model for lines and surfaces

構(gòu)建無向圖的步驟如下：首先，通過鼠標(biāo)點(diǎn)擊屏幕的位置獲得地理坐標(biāo)，以該坐標(biāo)建立緩沖區(qū)并獲取緩沖區(qū)內(nèi)的線和面；其次，將所有的線和面在交點(diǎn)處分割成多個路徑（不考慮路徑自交叉的情況)；最后，以路徑的起點(diǎn)和終點(diǎn)為節(jié)點(diǎn)建立鄰接表。實現(xiàn)求交點(diǎn)功能可以使用ArcGIS Engine 中的ITopologicalOperator 接口（牟乃夏等，2015)，也可以利用已有研究（Wei 等，2019；成雯，2021)算法求解交點(diǎn)。

3 基于改進(jìn)的深度優(yōu)先搜索的封閉區(qū)域識別

3.1 深度優(yōu)先搜索

深度優(yōu)先搜索算法被廣泛應(yīng)用于計算機(jī)圖形學(xué)，用于遍歷圖的節(jié)點(diǎn)及尋找兩個節(jié)點(diǎn)之間的最短路徑。深度優(yōu)先搜索采用了一種“一直向前走，走不通就掉頭”的思想。從圖中某節(jié)點(diǎn)S出發(fā)，先訪問S的一個鄰接點(diǎn)V，然后訪問V的所有鄰接點(diǎn)直到經(jīng)過V這條路徑的節(jié)點(diǎn)全部被訪問，再退回來訪問S的另一個鄰接點(diǎn)，直至圖中和S有路徑相通的節(jié)點(diǎn)都被訪問。如圖4 所示，若以節(jié)點(diǎn)A為起點(diǎn)，該圖的節(jié)點(diǎn)訪問順序有四種可能，分別是ABEC FHGD、ABEDGHFC、ACFHGDBE和ADGHF CBE。

圖4 深度優(yōu)先搜索Fig.4 Depth-first search

3.2 改進(jìn)的深度優(yōu)先搜索

對深度優(yōu)先搜索算法加以改進(jìn)，使之能夠快速尋找包含指定坐標(biāo)的最小封閉區(qū)域。算法的基本思路，如圖5（a)所示，在無向圖中尋找包含坐標(biāo)點(diǎn)C的最小封閉區(qū)域。

圖5 改進(jìn)的深度優(yōu)先搜索算法Fig.5 Improved depth-first search algorithm

3.3 選擇搜索起點(diǎn)

搜索起點(diǎn)的選擇直接影響到算法的執(zhí)行時間，因為要尋找包含指定坐標(biāo)點(diǎn)C的最小封閉區(qū)域，所以搜索起點(diǎn)選擇距離C最近的節(jié)點(diǎn)。如果以該節(jié)點(diǎn)為起點(diǎn)進(jìn)行搜索未能遍歷圖的所有節(jié)點(diǎn)且未能得到包含C的封閉回路，則選擇未訪問的節(jié)點(diǎn)中距離C最近的節(jié)點(diǎn)為起點(diǎn)。

3.4 起點(diǎn)鄰接點(diǎn)的訪問順序

圖5（a)中，選擇距離坐標(biāo)點(diǎn)C最近的節(jié)點(diǎn)V8為起點(diǎn)，V8的鄰接點(diǎn)有3 個，分別是V5、V7和V9。如果優(yōu)先訪問V7，則一定無法得到包含C的最小封閉區(qū)域；如果優(yōu)先訪問V5或V9，則有可能得到包含C的最小封閉區(qū)域，因此需要限制鄰接點(diǎn)的訪問順序。

在傳統(tǒng)的深度優(yōu)先搜索算法中，鄰接點(diǎn)的訪問順序是無序的，是一種盲目搜索法。本文利用旋轉(zhuǎn)角度解決鄰接點(diǎn)訪問順序問題，使起點(diǎn)優(yōu)先訪問鄰接點(diǎn)V5或V9。先求出直線V8C順時針或逆時針旋轉(zhuǎn)到V5、V7和V9的角度；根據(jù)旋轉(zhuǎn)角度將起點(diǎn)的3個鄰接點(diǎn)排序，再依次訪問這些節(jié)點(diǎn)。無論采用順時針旋轉(zhuǎn)還是逆時針旋轉(zhuǎn)都能保證V8首先訪問V5或V9，本文采用逆時針旋轉(zhuǎn)（圖5（b))。

3.5 非起點(diǎn)鄰接點(diǎn)的訪問順序

與起點(diǎn)鄰接點(diǎn)的訪問順序類似，非起點(diǎn)鄰接點(diǎn)的訪問順序也采用旋轉(zhuǎn)角度對鄰接點(diǎn)排序。定義當(dāng)前節(jié)點(diǎn)V，V的父節(jié)點(diǎn)為P，計算以V為頂點(diǎn)，VP逆時針旋轉(zhuǎn)至其他鄰接點(diǎn)的角度。如圖5（c)所示，V5V8逆時針旋轉(zhuǎn)至V5V6、V5V2和V5V4，按旋轉(zhuǎn)角度從小到大訪問鄰接點(diǎn)，那么下一個被訪問的節(jié)點(diǎn)是V6；但訪問V6的時候發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)V6的鄰接點(diǎn)只有父節(jié)點(diǎn)V5，所以原路返回并繼續(xù)訪問V5的下一個鄰接點(diǎn)V2。以此類推，V2之后依次訪問V3、V9和V8。

3.6 封閉區(qū)域提取

V9的鄰接點(diǎn)中最先被訪問的是V8，當(dāng)訪問V8時發(fā)現(xiàn)它的顏色是黑色，說明該節(jié)點(diǎn)已經(jīng)被訪問過了，從而構(gòu)成了封閉區(qū)域V8V5V2V3V9（圖5（c))。算法結(jié)束前要在V9的相遇點(diǎn)信息中記錄節(jié)點(diǎn)V8以便于后續(xù)的封閉區(qū)域提取。無向圖中僅V9含有相遇點(diǎn)信息，因此，以V9為起點(diǎn)提取封閉區(qū)域，V9的父節(jié)點(diǎn)為V3，V3不是V9的相遇點(diǎn)，記錄V9到V3的路徑信息；V3的父節(jié)點(diǎn)為V2，V2也不是V9的相遇點(diǎn)，記錄V3到V2的路徑信息；同理，記錄V2到V5的路徑；直到發(fā)現(xiàn)V8是V9的相遇點(diǎn)，記錄V5到V8和V8到V9的路徑后封閉區(qū)域提取完成。此時所有記錄的路徑信息構(gòu)成了環(huán)V8V5V2V3V9，ArcGIS 中環(huán)可以構(gòu)建面。

3.7 非直線邊的旋轉(zhuǎn)角度

當(dāng)2 個節(jié)點(diǎn)之間的邊為曲線時，計算旋轉(zhuǎn)角度不能直接使用2 個節(jié)點(diǎn)的連線進(jìn)行旋轉(zhuǎn)，應(yīng)當(dāng)使用過當(dāng)前節(jié)點(diǎn)的切線。如圖6 所示，假設(shè)指定坐標(biāo)點(diǎn)位于最小封閉區(qū)域PACD內(nèi)，節(jié)點(diǎn)A為當(dāng)前點(diǎn)，節(jié)點(diǎn)P、B、C為A的鄰接點(diǎn)，其中，P為A的父節(jié)點(diǎn)。按照本文定義的旋轉(zhuǎn)角度計算方法，以A為頂點(diǎn)，邊PA逆時針旋轉(zhuǎn)至AC和AB的角度分別為α和β，角β小于角α，導(dǎo)致先訪問B再訪問C，最終得到一個非最小封閉區(qū)域PABCD。顯然，PA逆時針旋轉(zhuǎn)會先遇到邊AC再遇到邊AB，過節(jié)點(diǎn)A作邊AC的切線AA′，PA旋轉(zhuǎn)至AA′的角度γ才是正確的旋轉(zhuǎn)角，角γ小于角β，則先訪問C，最終得到正確的最小封閉區(qū)域PACD。如果路徑A到C是一個混合了直線和各種曲線的復(fù)雜路徑，那么取A到C路徑上的第一個線段計算旋轉(zhuǎn)角度。

圖6 非直線邊的旋轉(zhuǎn)角度Fig.6 Rotation angle of non-straight edges

ArcGIS Engine 中提供了豐富的曲線接口，如圓弧接口（ICircularArc)、橢圓弧接口（IEllipticArc)、貝澤爾曲線接口（IBezierCurve)等，由此可以方便的求取曲線上某一點(diǎn)的切線。以圓弧為例，圖7 是ArcGIS 中定義的圓弧屬性，已知圓弧的起點(diǎn)、終點(diǎn)和圓心，易求得過點(diǎn)起點(diǎn)的切線，也可以使用曲線接口中的QueryTangent 方法求取切線。

圖7 ArcGIS 圓弧屬性Fig.7 ArcGIS circular arc properties

3.8 算法步驟

算法步驟如下所述。

（1)以指定坐標(biāo)點(diǎn)C為基點(diǎn)建立緩沖區(qū)，緩沖區(qū)內(nèi)的線、面要素的路徑添加到集合List＜IPath＞。

（2)對集合List＜IPath＞中的所有元素求交點(diǎn)（利用ArcGIS Engine 中的ITopologicalOperator 接口)，并在交點(diǎn)處打斷，得到簡單無向圖。

（3)遍歷圖中的邊以建立鄰接表，初始化表中的所有節(jié)點(diǎn)，顏色Color=白色，父節(jié)點(diǎn)P=空，相遇點(diǎn)M=空。

（4)計算圖中所有節(jié)點(diǎn)到C點(diǎn)的距離，選擇距離最小的節(jié)點(diǎn)作為深度優(yōu)先搜索的起點(diǎn)S。

（5)開始訪問當(dāng)前節(jié)點(diǎn)S，修改S的顏色Color[S]=黑色。

（6)計算S的旋轉(zhuǎn)角度：以S為頂點(diǎn)，直線SC逆時針旋轉(zhuǎn)到S的其他鄰接點(diǎn)的角度（如果S到鄰接點(diǎn)的邊是曲線，則計算SC逆時針旋轉(zhuǎn)到S至鄰接點(diǎn)路徑上第一個段的切線，下同)。

（7)按照旋轉(zhuǎn)角度從小到大對S的鄰接點(diǎn)排序。

（8)然后拿到S的一個鄰接點(diǎn)V。

（9)開始訪問當(dāng)前節(jié)點(diǎn)V，V的父節(jié)點(diǎn)P[V]=S，顏色 Color[V]=黑色。

（10)計算以V為頂點(diǎn)，VS逆時針旋轉(zhuǎn)至V的鄰接點(diǎn)的旋轉(zhuǎn)角度。

（11)按照旋轉(zhuǎn)角度從小到大對V的鄰接點(diǎn)排序。

（12)然后拿到V的鄰接點(diǎn)N。

（13)如果N不是V的父節(jié)點(diǎn)，且N未被訪問過，即 Color[N]=白色，將N設(shè)為當(dāng)前節(jié)點(diǎn)，跳到步驟（9)。

（14)如果N不是V的父節(jié)點(diǎn)，但N被訪問過，即 Color[N]=黑色，記錄相遇點(diǎn)M[V]=N，跳到步驟（19)。

（15)如果N是V的父節(jié)點(diǎn)，說明V的鄰接點(diǎn)訪問完畢（父節(jié)點(diǎn)的旋轉(zhuǎn)角度為360°，排在其他所有鄰接點(diǎn)之后)，將V的父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)，跳到步驟（9)。

（16)至此，與起點(diǎn)S相連通的所有節(jié)點(diǎn)都被訪問了，但仍然沒有找封閉區(qū)域，考慮無向圖中是否存在其他的連通分量（譚屯子等，2018；廖小飛等，2019)。

（17)遍歷圖中所有節(jié)點(diǎn)，如果發(fā)現(xiàn)節(jié)點(diǎn)V的顏色 Color[V]=白色，將V設(shè)為當(dāng)前節(jié)點(diǎn)，跳到步驟（5)。

（18)如果圖中所有節(jié)點(diǎn)均已被訪問，表示未尋找到包含C點(diǎn)的封閉區(qū)域，程序結(jié)束。

（19)開始提取封閉區(qū)域，拿到含有相遇點(diǎn)信息的節(jié)點(diǎn)E，E的相遇點(diǎn)為M[E]。

（20)獲取當(dāng)前節(jié)點(diǎn)V的父節(jié)點(diǎn)P[V]。

（21)根據(jù)鄰接表獲取節(jié)點(diǎn)V到節(jié)點(diǎn)P[V]的路徑信息，并記錄到路徑集合List＜IPath＞。

（22)如果P[V] =M[E]，跳到步驟（24)。

（23)如果P[V] ≠M(fèi)[E]，將P[V]設(shè)為當(dāng)前節(jié)點(diǎn)，跳到步驟（20)。

（24)根據(jù)鄰接表獲取節(jié)點(diǎn)M[E]到節(jié)點(diǎn)E的路徑信息，并記錄到路徑集合List＜IPath＞。

（25)根據(jù)路徑集合List＜IPath＞構(gòu)建ArcGIS 面幾何（利用ArcGIS Engine 中的IGeometryCollection接口依次添加路徑集合List＜IPath＞中的路徑)。

（26)程序結(jié)束。

4 實 驗

圖8（a)是由12 個節(jié)點(diǎn)組成的簡單無向圖，其中P點(diǎn)表示搜索基點(diǎn)；圖8（b)中圓形虛線表示緩沖區(qū)范圍，與緩沖區(qū)相交或被緩沖區(qū)包含的路徑參與簡單無向圖的構(gòu)建，并在圖中高亮顯示這些路徑。如果沒有找到封閉區(qū)域則擴(kuò)大緩沖區(qū)范圍，重新構(gòu)建無向圖，直至找到封閉區(qū)域或緩沖區(qū)達(dá)到閾值，閾值的設(shè)定可采用如下三種方式：①設(shè)置構(gòu)建緩沖區(qū)次數(shù)的上限；②設(shè)置緩沖區(qū)面積的上限；③設(shè)置緩沖區(qū)內(nèi)路徑數(shù)量的上限。

圖8 實驗Fig.8 Experiments

以P為基點(diǎn)建立緩沖區(qū)（圖8（b))，則參與構(gòu)建簡單無向圖的路徑有AB、AD、AE、AF，其中，A點(diǎn)到P點(diǎn)的距離最近，則無向圖的當(dāng)前節(jié)點(diǎn)為A。根據(jù)前文所述知圖中節(jié)點(diǎn)的訪問順序為ADEFB，節(jié)點(diǎn)D、E、F、B除父節(jié)點(diǎn)外，未找到其他被訪問過的鄰接點(diǎn)，所以封閉區(qū)域搜索失敗。

擴(kuò)大緩沖區(qū)半徑（圖8（c))，則參與構(gòu)建簡單無向圖的路徑有AB、AD、AE、AF、DG、DH、DC、ab、bc、cd、da。圖中節(jié)點(diǎn)的訪問順序為ADCGHEFB，同理封閉區(qū)域搜索失敗。此時，圖中還有abcd節(jié)點(diǎn)未被訪問，這表示abcd與其他節(jié)點(diǎn)不連通，其中，距離P點(diǎn)最近的節(jié)點(diǎn)為a，節(jié)點(diǎn)的訪問順序為adcb，節(jié)點(diǎn)b除父節(jié)點(diǎn)c外，還有鄰接點(diǎn)a被訪問過，所以得到封閉區(qū)域abcd，但由于該封閉區(qū)域未包含P點(diǎn)，所以封閉區(qū)域搜索失敗。

繼續(xù)擴(kuò)大緩沖區(qū)半徑（圖8（d))，則參與構(gòu)建簡單無向圖的路徑有AB、BC、CD、DA、AE、AF、DG、DH、ab、bc、cd、da，圖中節(jié)點(diǎn)的訪問順序為ADCB，可得到封閉區(qū)域ABCD且該封閉區(qū)域包含P點(diǎn)。注意，雖然封閉區(qū)域abcd未包含P點(diǎn)，但abcd被ABCD包含，所以ABCD應(yīng)對abcd進(jìn)行面內(nèi)構(gòu)島，否則ABCD就不是最小封閉區(qū)域。圖8（e)所示的黃色區(qū)域即為包含P點(diǎn)的最小封閉區(qū)域，在ArcGIS Engine 中利用IGeometry Collection 接口依次添加面ABCD和面abcd即可得到該最小封閉區(qū)域構(gòu)成的面。

5 結(jié) 論

本文提出一種改進(jìn)的深度優(yōu)先搜索算法，用于搜索包含指定坐標(biāo)點(diǎn)的最小封閉區(qū)域。在傳統(tǒng)深度優(yōu)先搜索算法的基礎(chǔ)上，利用旋轉(zhuǎn)角度限制鄰接點(diǎn)的訪問順序，使得搜索路線始終圍繞指定坐標(biāo)前進(jìn)，又因為鄰接表存儲了節(jié)點(diǎn)之間的ArcGIS 路徑，可以方便地構(gòu)建任意面要素。本文算法已應(yīng)用于ArcGIS Engine 開發(fā)的控規(guī)軟件（圖9)，利用點(diǎn)選功能（圖10)可以快速繪制規(guī)劃地塊，使用鼠標(biāo)點(diǎn)擊線與面構(gòu)成的合圍區(qū)域，即可搜索包含鼠標(biāo)點(diǎn)擊位置的最小封閉區(qū)域并創(chuàng)建規(guī)劃地塊面要素。

圖9 軟件菜單Fig.9 Software menu

圖10 繪制用地Fig.10 Draw land

在實現(xiàn)算法的過程中，搜索算法本身有著嚴(yán)密的邏輯，而簡單無向圖的構(gòu)建反而容易成為搜索失敗的原因。理由有三點(diǎn)：一是地圖中的線和面有著復(fù)雜的空間關(guān)系，如空間關(guān)系相等的要素要剔除；二是地圖中的線和面不可避免地存在拓?fù)溴e誤，如自相交需要提前判斷；三是因為簡單無向圖是一種理想的圖，它要求節(jié)點(diǎn)沒有自環(huán)且節(jié)點(diǎn)之間有唯一的路徑相連，這在實際情況中無法得到保證。綜上，在執(zhí)行封閉區(qū)域搜索算法前，需要對參與構(gòu)建簡單無向圖的線和面進(jìn)行合理的分析和預(yù)處理，才能保證搜索算法的順利執(zhí)行和面要素的成功構(gòu)建。