## 2 Polygonal Approximation Algorithm of Curvilinear Obstacle
### Proposed Expanded Douglas-Peucker (EDP) Algorithm
When \(\theta_{rot}\geq\angle Q_{0}P_{n}Q_{m}\), there is no additionally appending vertex, and \(Q_{m}=Q_{1}\); when \(\theta_{rot}\)\(<\angle Q_{0}P_{n}Q_{m}\), there are additionally appending vertices \(Q_{1},Q_{2},\,\ldots,\) which makes the effect of securing additional free space near the obstacle corner relatively difficult to path following. Algorithm 4 shows the detailed version of the pseudo code of the EDP algorithm. ```
Input:\(R_{DP}\leftarrow\) Result of DP polygonal approximation of all obstacles represented as a set of point lists \(\varepsilon\leftarrow\) Threshold value for maximum dissimilarity tolerance \(\theta_{rot}\leftarrow\) Constant angle for obstacle corner clearance Output:\(R\leftarrow\) Final result of the EDP polygonal approximation represented as a set of point lists Begin Expanded-DP Procedure
1 for each \(r_{DP}\) in \(R_{DP}\)do
2 for each point \(P_{n}(x_{n},y_{n})\) in point list \(r_{DP}\)do
3 if\(\angle P_{n+1}P_{n}P_{n+1}<\pi\)then
4\(\theta\leftarrow\frac{1}{2}\angle P_{n+1}P_{n}P_{n+1}\)
5\(dist\leftarrow\varepsilon\) \(Q_{0}\leftarrow(x_{n},y_{n})^{T}+\frac{\varepsilon}{



line of the obstacle by proposition [P1], boundary point \(c\) should be identical to \(P_{n}\) or included in the range of [\(P_{n-1}\), \(P_{n}\)] or (\(P_{n}\), \(P_{n+1}\)). If point \(c\) is identical to \(P_{n}\), it is trivial that \(c\) cannot be located outside of the polygon with vertices \(Q_{m}\), \(Q^{\prime}\), \(Q^{\prime}\), \(Q^{\prime}\),..., \(Q^{\prime}\), and \(Q^{\prime\prime}\), since \(P_{n}\) is inside the polygon. If point \(c\) is included in the range of [\(P_{n-1}\), \(P_{n}\)], the distance from point \(c\) to the line segment \(\overline{P_{n-1}P_{n}}\) should be less than \(\varepsilon\) by proposition [P3]. Therefore, \(c\) cannot be located outside of the polygon with vertices \(Q_{m}\)\(\sim\)\(Q^{\prime}\). If point \(c\) is included in the range of (\(P_{n}\), \(P_{n+1}\)], the distance from point \(c\) to the line segment \(\overline{P_{n}P_{n+1}}\) should be less than \(\varepsilon\) by proposition [P4]. Therefore, \(c\) cannot be located outside of the polygon with vertices \(Q^{\prime}_{m}\)\(\sim\)\(Q^{\prime\prime}\). Therefore, no boundary point of the obstacle region is outside of the polygon with vertices \(Q_{m}\), \(Q^{\prime}\),..., \(Q^{\prime}\), and \(Q^{\prime\prime}\) in the case of convex \(P_{n}\). If \(P_{n}\) is a concave point,

Let us assume that there is a boundary point \(c\in[P_{n-1}\), \(P_{n+1}]\) of the obstacle such that \(c\) is located outside of the polygon \(Q_{m}\), \(Q^{\prime}\), \(Q^{\prime\prime}\), such as Figure 5b, which consists of the resulting points from the EDP algorithm on the obstacle. Since \(P_{n-1}\), \(P_{n}\), and \(P_{n+1}\) are points on the boundary line of the obstacle by proposition [P1], boundary point \(c\) should be identical to \(P_{n}\) or included in the range of [\(P_{n-1}\), \(P_{n}\)] or (\(P_{n}\), \(P_{n+1}\)). If point \(c\) is identical to \(P_{n}\), it is trivial that \(c\) cannot be located outside of the polygon with vertices \(Q_{m}\), \(Q^{\prime}\), and \(Q^{\prime\prime}\), since \(P_{n}\) is inside the polygon. If point \(c\) is included in the range of [\(P_{n-1}\), \(P_{n}\)], the distance from point \(c\) to the line segment \(\overline{P_{n-1}P_{n}}\) should be less than \(\varepsilon\) by proposition [P3]. Therefore, \(c\) cannot be located outside of the polygon with vertices \(Q_{m}\) and \(Q^{\prime}\),...

Once the polygonal approximation with the EDP algorithm is completed, it is possible to solve the obstacle collision problem that may occur when DP algorithm is used for the polygonal approximation of a curvilinear obstacle. Since the polygon created by the EDP algorithm can guarantee the circumscription of obstacles, this result of EDP can be used to apply OAECD in path planning with curvilinear obstacles. Figure 5: Circumscription of EDP: (**a**) Convex; (**b**) Concave.