## 2 Topological Map Construction Based on Regional Dynamic Growth
### Regional Adjustment Process  
After the growth of the previous section, the whole environment will be divided into regions of different sizes because of the dynamic growth. The small areas not only waste the vertex resources of the topological map, but also cannot be used for the interactive navigation of the actual scene. Therefore, it is necessary to merge small areas and optimize the topological map. In order to improve the coverage of topographic maps, the region can be regenerated. During the secondary growth process, if the radius of the current region is less than the threshold value and no new points are added, or the maximum radius of secondary growth is meeted, the growth process will quit. The method is similar to regional growth in Section 2.1, which is not discussed here again. In addition, the Kruskal algorithm is used to adjust the topological map before region merging, and the minimum spanning tree form of the topological map is obtained, which further simplifies the map structure.The next step is to merge some areas. The region merging algorithm first counts the topological vertices that meet the merge requirements. It needs to satisfy the following two conditions:  
1. The radius of the main vertex area is less than the threshold. 2. The total area of the merged area is less than the threshold. 3. The obstacle ratio of the merged area is less than the threshold. ```
0: To merge small areas, delete the original topological vertices and generate new topological vertices, and change the color identification of the topological area. 0: Topological region vertex sequence set \(P_{\text{m}}\) to be merged. 0: The status of this subarea merge: true means the merge was successful; false means no merge occurred. 1: initialize the set of topological vertex ordinals \(V_{\text{com}}=\{\}\) that need to be merged
2: initialize the point set \(P_{\text{com}}\)= \(\{\}\) of the points contained in the merged region
3: initialize the point set \(P_{i}\)= \(\{\}\) of the disqualified points around the merged area
4: initialize the first vertex information (\(p_{\text{first}}\leftarrow\text{P}_{\text{m}}^{0}\)) of the merge process
5: calculate the weighted center coordinate \(p_{\text{c}}\gets P_{\text{m}}\)
6: calculate the average scan radius \(r_{\text{c}}\gets P_{\text{m}}\)
7:for\(r\) in \([0,r_{\text{c}}]\)
8:\(P\leftarrow\)loop traversal of all the points contained within the scan radius. 9:for\(P_{i}\) in \(P\)
10:if (\(P_{i}\) belongs to the topological area)
11:\(P_{\text{com}}\gets P_{i}\)
12:else\(P_{i}\gets P_{i}\)
13:if (\(P_{\text{com}}\) is empty)
14:returnfalse
15:\(P_{\text{h}}\leftarrow\)calculate the current convex hull (\(P_{\text{com}}\))
16: calculate the number of unqualified points containing \(P_{i}\) in convex hull \(P_{\text{h}}\)
17:if (obstacle ratio \(r_{\text{a}}\) doesn't satisfies the requirements)
18:returnfalse
19: delete all of the vertex information in \(P_{\text{m}}\)
20: Merge the vertex regions in \(P_{\text{m}}\) and add the region identifier at the same time
21:\(p_{\text{c}}^{\prime}\leftarrow\)calculate the center of the area
22:\(r_{\text{n}}\leftarrow\)calculate the radius of the merged area
23: Add a new topological vertex (\(r_{\text{n}},p_{\text{c}}^{\prime},P_{\text{com}}\))
24:returntrue
```  
**Algorithm 2**Region Merging  
After the vertex numbers that need to be merged are obtained, the region merge can be performed. The main steps are as follows:  
1. The points in the corresponding topological region of all the vertices are extracted, and the qualified points (identical with the vertex color marker) and the failure points (different from the vertex color) are counted. 2. The convex hulls of qualified points are calculated, the unqualified points of convex hulls are counted from the failure points, and the obstacle ratio is calculated. If the obstacle ratio is greater than the threshold, then exit. 3. If the obstacle ratio is less than the threshold, the region merging is carried out, the original vertex is deleted, and a new vertex is established.