最小封闭区域识别及构面算法研究与实现  

Research and implementation of minimum enclosing region recognition and construction plane algorithm

作　　者：侯凯宇 徐景 郑衡 李佑林 周钰笛 李智文 HOU Kaiyu;XU Jing;ZHENG Heng;LI Youin;ZHOU Yudi;LI Zhiwen(Changsha Planning&Design Survey Research Institute,Changsha 410000,China)

机构地区：[1]长沙市规划勘测设计研究院,长沙410000

出　　处：《时空信息学报》2023年第3期377-383,共7页JOURNAL OF SPATIO-TEMPORAL INFORMATION

基　　金：湖南省自然资源厅科技项目(20230113GH)。

摘　　要：针对计算机数据结构中图的闭合回路搜索,无法寻找包含指定坐标的最小封闭区域的问题,本文提出一种改进的深度优先搜索算法寻找最小封闭区域。首先,以指定坐标为基点建立缓冲区;其次,用缓冲区内的线和面建立简单无向图;最后,使用改进的深度优先搜索算法进行搜索,搜索过程中利用旋转角度控制邻接点的访问顺序,从而实现搜索路线始终围绕指定坐标前进。结果表明,本文算法能够快速寻找包含指定坐标的最小封闭区域。When utilizing ArcGIS Engine for software development,it necessary to determine the minimum enclosing surface that contains specific coordinates.In other words,ArcGIS Engine cannot identify the minimum enclosing region that encompasses these coordinates.Recognizing a closed region essentially involves solving a closed-loop search problem within computer data structures.Traditional closed-loop search algorithms include depth-first search(DFS)and breadth-first search(BFS).In this paper,an improved DFS algorithm is proposed to find the minimum enclosing region that includes the specified coordinates within ArcGIS Engine.The improved DFS algorithm builds a simple undirected graph(SUG)based on the ArcGIS object model of lines and surfaces.It then uses the algorithm to traverse the SUG and search for the smallest closed region that contains the specified coordinates.The detailed steps of the algorithm are as follows:First,a buffer is established based on the specified coordinates,and all ArcGIS lines and surfaces that intersect with or are contained within the buffer are obtained.These lines and surfaces within the buffer are divided into ArcGIS paths(ArcGIS lines and surfaces are composed of ArcGIS paths).Second,a SUG is established using the path as the edges and the endpoints of these paths as nodes.The paths connecting the nodes are recorded in the adjacency list of the SUG.Since a SUG requires only one edge to be connected between nodes,when it is found that there is a self-loop or parallel edge in the graph,it is necessary to break the self-loop or parallel edge and add a node at the breakpoint.Third,the algorithm selects the SUG node closest to the specified coordinate point as the starting point.It calculates the included angle between the specified coordinate point,the starting point,and the adjacent starting point before traversing.Fourth,the algorithm accesses all adjacent points of the starting point in ascending or descending order of the included angle.During this process,it calculates the angle between t

关 键 词：无向图 封闭区域 深度优先搜索 邻接表 邻接点 缓冲区 路径 ArcGISEngine 

分 类 号：P208[天文地球—地图制图学与地理信息工程] TU984[天文地球—测绘科学与技术]