## 2 Polygonal Approximation Algorithm of Curvilinear Obstacle
### Proposed Expanded Douglas-Peucker (EDP) Algorithm  
The path planning for curvilinear obstacles using DP algorithm may not be collision-free. The basic philosophy of the EDP algorithm is to guarantee the circumscription of obstacles by expanding the polygon of the DP algorithm with the maximum dissimilarity tolerance. In addition, by appending additional points near the convex corner, the convex corner clearance is considered, where the robot control may become more difficult during path following. Figure 3 shows the operation of EDP based on the counter-clockwise traversal. The first step is to perform the DP algorithm. If the half angle between line segments \(l_{0}\) and \(l_{1}\) is 0-90\({}^{\circ}\), i.e., the corner of DP polygon is convex, the perpendicular half-lined to \(l_{0}\) and \(l_{1}\) are \(v_{0}\) and \(v_{1}\) at the corner point, respectively. Then, the points on the arc, with the center point as the convex corner and the radius of \(\varepsilon\), are appended starting from \(v_{0}\) and rotating with angle \(\theta_{rot}\) until they meet \(v_{1}\) in the counter-clockwise direction. These points are added for the convex corner clearance. If the half angle between line segments \(l_{0}\) and \(l_{1}\) is 90\({}^{\circ}\) or more, i.e., the corner of DP polygon is concave, the point far from the cross point of \(l_{0}\) and \(l_{1}\) with distance \(\varepsilon\) to the outer direction of the obstacle is appended. The above procedures are repeated for the remaining corner points of the DP polygon. Algorithm 3 shows the abstract version of the pseudo code of the EDP algorithm. Figure 3: Abstract process of Expanded Douglas–Peucker (EDP) algorithm: (**a**) Before applying EDP for a convex corner; (**b**) After applying EDP for a convex corner; (**c**) Before applying EDP for a concave corner; (**d**) Overall appearance after applying EDP for a concave corner. Here, \(R_{DP}\) is the set of point lists of the polygonal approximation of the obstacles by the DP algorithm; \(\epsilon\) is the threshold value for maximum dissimilarity tolerance; \(\theta_{rot}\) is a constant angle for obstacle corner clearance; \(R\) is the final result of the polygonal approximation of all obstacles by the EDP algorithm, and \(r_{DP}\) is a point list of the obstacle polygonal approximation by the DP algorithm, which is arranged in counter-clockwise order. Figure 4 illustrates the detailed version of the EDP algorithm (Algorithm 4). Figure 4: Detailed process of the EDP: (**a**) Convex; (**b**) Concave. Since \(P_{n-1}^{\ \rightarrow}P_{n}=(x_{n}-x_{n-1},\ y_{n}-y_{n-1})\) and \(P_{n-1}^{\ \rightarrow}P_{n}\bot P_{n}^{\ \rightarrow}Q_{0}\),  
unit vector of  
\[P_{n}^{\ \rightarrow}Q_{0}=\frac{1}{\sqrt{\left(y_{n}-y_{n-1}\right)^{2}+ \left(x_{n}-x_{n-1}\right)^{2}}}\left(y_{n}-y_{n-1},\ -(x_{n}-x_{n-1})\right)^{T} \tag{1}\]  
Therefore,  
\[Q_{0}=\frac{\varepsilon}{\sqrt{\left(y_{n}-y_{n-1}\right)^{2}+ \left(x_{n}-x_{n-1}\right)^{2}}}\left(y_{n}-y_{n-1},\ -(x_{n}-x_{n-1})\right)^{T} \tag{2}\]  
In addition, since \(Q_{i}\) (\(i=1,\,2,\,\ldots,\,m-1\)) are on the arc with center point \(P_{n}\) and radius \(\varepsilon\), rotating \(Q_{i}\) with angle \(\theta_{rot}\) in the counter-clockwise direction yields  
\[Q_{i}=\left( \begin{array}{cc}\cos\theta_{rot}&-\sin\theta_{rot}\\ \sin\theta_{rot}&\cos\theta_{rot}\end{array} \right)\left(Q_{i-1}-P_{n}\right) +P_{n} \tag{3}\]  
Similarly, in the case of a concave corner,  
\[\overset{\rightarrow}{OP_{n}}+P_{n}^{\ \rightarrow}Q_{s}=\left(x_{n},y_{n} \right)^{T}+\left( \begin{array}{cc}\cos(\pi-\theta)&-\sin(\pi-\theta)\\ \sin(\pi-\theta)&\cos(\pi-\theta)\end{array} \right)\left(x_{n-1}-x_{n},\ y_{n-1}- y_{n}\right)^{T} \tag{4}\]  
Around the convex vertex of DP polygon, the concept of \(\theta_{rot}\) is used for the convex corner clearance.