## 2 Polygonal Approximation Algorithm of Curvilinear Obstacle
### Douglas-Peucker Algorithm  
The DP algorithm is a representative method of polygonal approximation. The purpose of a DP algorithm is to find a similar piecewise linear curve with fewer points given a closed curve. The algorithm uses the concept of dissimilarity based on the maximum distance between the original curve points and their simplified piecewise linear curve [17; 18]. Figure 1: An example of Vertical Cell Decomposition (VCD) and its path. The algorithm (Algorithm 1) measures the distance between each point of a curve and the base line, which is the line segment with the same first and last points with the curve, to find the farthest point from the line segment with the maximum perpendicular distance. Here, \(C\) is the set of obstacle contours, which is the set of point lists of the obstacle; \(\varepsilon\) is the threshold value for the maximum dissimilarity tolerance; \(R\) is the final result of the polygonal approximation of all obstacles; \(c\) is a point list of the obstacle contour, which is arranged in counter-clockwise order; \(pl\) is a point list; \(r_{1}\) and \(r_{2}\) indicate each result of the recursiveDP procedure; \(r\) indicates the final result of the polygonal approximation of an obstacle by DP algorithm. ```
Input: \(C\leftarrow\) Set of point lists of the obstacle \(\varepsilon\leftarrow\) Threshold value for maximum dissimilarity tolerance Output: \(R\leftarrow\) Final result of polygonal approximation of all obstacles represented as a set of point lists Begin DP Procedure
1 for each \(c\) in \(C\)do
2 find two points in \(c\), \(p_{1}\) and \(p_{2}\), which have the maximum distance from each other and \(p_{1}\) is in front of \(p_{2}\)
3\(r_{1}\leftarrow\) recursiveDP(\(pl[p_{1}\ldots\)\(p_{2}]\), \(\varepsilon\)) // \(pl\): point list of a segment of obstacle contour
4\(r_{2}\leftarrow\) recursiveDP(\(pl[p_{2}\ldots\) starting point of \(c\ldots\)\(p_{1}]\), \(\varepsilon\))
5\(r\leftarrow\) point list[\(r_{1}[0]\ldots\)\(r_{1}[\text{end}_{1}-1]\)\(r_{2}[0]\ldots\)\(r_{2}[\text{end}_{2}-1]\)] // end\({}_{i}\): number of points in \(r_{i}\)insert \(r\) to \(R\)
6 endfor End DP Procedure
```  
**Algorithm 1**Pseudo Code of the Initial DP. In the recursive procedure of DP algorithm (Algorithm 2), the line segment is further divided into two sub-line segments using the farthest point as the via-point whenever the maximum perpendicular distance is greater than or equal to the threshold value for maximum dissimilarity tolerance, \(\varepsilon\). This process is recursively repeated until the maximum perpendicular distance is less than \(\varepsilon\). Here, \(r_{1}\) and \(r_{2}\) are each the result of the recursiveDP procedure, and \(r\) is the result of the polygonal approximation of the given curve. Figure 2 shows the process of the DP algorithm. \(l_{b}\) is the base line, which is identical to \(line_{base}\) in Algorithm 2. \(l_{b1}\) is determined with the starting point \(P_{1}\) and ending point \(P_{2}\), which makes the widest width of the given obstacle. Then, we check whether \(dist_{max}\) is less than \(\varepsilon\). If \(dist_{max}\) is less than \(\varepsilon\), two vertices of \(l_{b1}\) are inserted into the point list of the polygonal approximation. If \(dist_{max}\) is greater than or equal to \(\varepsilon\), a new base line \(l_{b2}\) with \(P_{1}\) and \(P_{3}\) is made, new \(dist_{max}\) is found again based on \(l_{b2}\), and the above procedures are repeated. The obstacle approximation result by DP algorithm does not guarantee the circumscription of the original obstacle. In other words, some interior points of the obstacle region may not be included inside the polygon by the DP algorithm. Similarly, some exterior points of the obstacle region may be included inside the polygon by the DP algorithm. Thus, if the result of the DP algorithm on a curvilinear obstacle is directly used for path planning, the generated path may penetrate inside the real obstacle region, and the robot may easily collide with the obstacle.