## 3 Map Construction Method
### Road Centerline Extraction
#### 3.1.1 Constructing Constrained Delaunay Triangulation  
Compared with the traditional Delaunay triangulation, the construction of the constrained Delaunay triangulation required mandatory constraints on the polygon using the road edge nodes and line segments as constraints so that the road boundary becomes an edge in the triangle construction process [32]. For road areas, original points are often used to describe important morphological features of areas, such as inflection points and intersection points, and the number of these points is usually small. The construction of triangulation directly with constraints may generate some narrow and elongated triangles that do not correctly represent the proximity between polygons [33; 34]. Hence, the densification of road points is required, as shown in Figure 3a.  
In general, the densification step is related to lane width, which can be set to 3-3.75 m. Considering the smoothness of the following road centerline connection, the road point densification step is set to 3 m in our experiment. The Delaunay triangulation is to be constructed using the point-by-point insertion method, and the schematic diagram of  
Figure 3: Illustration of the steps to construct a constrained Delaunay triangle. (**a**) Points densification; (**b**) Constructing Delaunay triangulation; (**c**) Determination of road triangles; (**d**) Constructing CDT.  
the construction is shown in Figure 3b. The basic idea of this method is to first find the minimum convex hull boundary containing the data region, then build the initial triangular network in it, and finally insert all the remaining points into the triangular network one by one [35] to ensure that it retains the Delaunay triangulation.  
The triangulation constitutes a dissected structure in planar space, treating its basic unit as a single triangle. In order to identify the triangle within the road, the inclusion relationship between the center of gravity P of the triangle and the road area is taken as the judgment basis. In detail, if the gravity center of a triangle is located within the road, then the triangle is considered as a road triangle and needs to be retained. Otherwise, the triangle is not taken as a road triangle and needs to be removed. As shown in Figure 3c, when the center of gravity P\({}_{1}\) is located within the road, then the blue triangle is a road triangle. In contrast, when the center of gravity P\({}_{2}\) is not located within the road, then the gray triangle does not belong to the road triangle.  
Then, all the road triangles are kept as the basis for road centerline extraction. The center of gravity of the triangle, which is calculated according to Equation (9), determines the inclusion relationship between itself and the road.  
\[\begin{array}{l}x_{p}=(x_{1}+x_{2}+x_{3})/3\\ y_{p}=(y_{1}+y_{2}+y_{3})/3\end{array} \tag{9}\]  
where \(x_{1},x_{2},x_{3}\) are the horizontal coordinates of the three vertices of the triangle to be judged, \(y_{1},y_{2},y_{3}\) are the vertical coordinates of the three vertices of the triangle to be judged, \(x_{p}\) is the value of the horizontal coordinate of the center of gravity P of the triangle, and \(y_{p}\) is the value of the vertical coordinate of the center of gravity P of the triangle.  
The result of triangle extraction is shown in Figure 3d.