最小封閉區域識別及構面算法研究與實現

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

長沙市規劃勘測設計研究院, 長沙 410000

1 引 言

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

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