## 2 Topological Map Construction Based on Regional Dynamic Growth
### Regional Growth Process  
Based on the metric map and the trajectory of the robot, the map building system will randomly initialize the region growing point on the trajectory (which is in the same coordinate system as the metric map). It is worth mentioning that this point is not the final center of the region (also called the topological vertex). Then, the circular growth of the region is achieved by using a circular scanner with the same degree of growth in all directions on the plane, rather than depending on the geometric structure or special characteristics of the environment. There are several important parameters in the regional dynamic growth algorithm, which are described below:  
* \(r_{\text{a}}\): The points' addition ratio in the circular scan, which refers to the ratio of qualified points in each circular scan. It can prevent malformation, making the growth area approximately circular or elliptical rather than elongated. * \(r_{\text{o}}\): The obstacle ratio in the circular scan, which refers to the ratio of unqualified points to the total qualified points in the convex hull region composed of qualified points in the added points  
Figure 1: The architecture of the topological map construction system. and areas in each annular scanning. It can prevent the region from growing into a concave region, and ensure the convexity of the topological region. * \(r_{\text{p}}\): The points pass ratio of the topological region, which refers to the ratio of all the points in the topological region to all the points in the circular region (ideal region). It can reflect the contrast between the growth area and the ideal area in the current state. It is used to modify the growth radius in real time, so its role is to prevent growth deficiency. * \(R_{\text{w}}\): The control weight of dynamic modification of the growth radius, which refers to the extent of radius modification in each region. The concept of the qualified point is mentioned above. If one of them is not satisfied, it is called an unqualified point. The qualified point needs to satisfy all the following conditions:  
1. The metric map area that corresponded to the point must be in a free space, and cannot be an occupied space or an unknown space. 2. The topological map area corresponding to the point must be a non-topological identifier area, which can only be a free space or a local area identifier. 3. Conditions 1 and 2 must be satisfied for all points through which the ray emitted from the region vertex passes. As the location of the robot's trajectory must be free and can basically traverse the whole environment, it is better to sample the growing points from the robot's trajectory. Then, the main steps of the region dynamic growth algorithm are as follows (Figure 2, the symbols in the Figure 2d will be described later):  
1. Determine the growth point and scan all the adjacent points around the current region vertex in a circular way. 2. Rays from the growth point to each point were calculated using the Bresenham algorithm Bresenham (1953), and all of the qualified points were screened. 3. Calculate the convex hull after each qualified point is added using the Graham scanning algorithm Bresenham (1953), and retain the point where the obstacle ratio satisfies the requirements. 4. Add qualifying points to the topological area. At the same time, the points pass ratio and the points add ratio in the current state are calculated. If the points' addition ratio is less than the threshold, the growth of the current region is exited, indicating that the region growth is completed ahead of time. If the addition rate is normal, the points pass ratio will be used to modify the maximum growth radius. The modified formula is shown in Equation  
However, Equation (2) is not suitable for multi-triangle calculation, so the triangle area calculation method is used in this paper. Firstly, the area of the triangle is calculated by vector cross-multiplication, as shown in Equation (3).