## 2 Polygonal Approximation Algorithm of Curvilinear Obstacle
### Proposed Expanded Douglas-Peucker (EDP) Algorithm
Modified Opposite Angle-Based Exact Cell Decomposition (OAECD) Algorithm for Path Planning with Curvilinear Obstacles

The basic concept of the modified OAECD algorithm is to reduce as possible as many cells after the execution of the EDP algorithm and increase the calculation efficiency. Using the concept of inclusion of an opposite angle, OAECD first tries to connect the closest neighboring cell in the opposite angle region. OAECD does not randomly or sequentially process the points but processes in the order from a close pair to a far pair through three consecutive steps, which are similar to the human method. In addition, OAECD does not try to make an additional decomposition if the shape of the generating cell is convex. The detailed algorithm for the modified OAECD consists of three steps [18]. Figure 6 shows how the decomposing lines are formed between the obstacles for each step of the modified OAECD algorithm. In the first step, the modified OAECD finds the closest neighboring vertex in the set of all vertices of other obstacles for every convex vertex (CV) of each obstacle. For every CV of each obstacle and its closest neighboring vertex (NV) in other obstacles, a new decomposing line is drawn if there is no existing decomposing line with the current CV, its closest NV is inside the region of the opposite angle of the current CV, and no intersection is made with other obstacles or other decomposing lines. Figure 6: Decomposition results of each step in the modified Opposite Angle-Based Exact Cell Decomposition (OAECD) algorithm after the EDP algorithm: (**a**) Environment; (**b**) Result of step 1; (**c**) Result of step 2; (**d**) Result of step 3. In the second step, for every CV among the remaining vertices and a vertex (AV) in another obstacle inside the region of the opposite angle of the current CV, a new decomposing line is drawn if there is no decomposing line with the current CV, the AV in another obstacle is the shortest one from the current CV among all available AVs, and there is no intersection with other obstacles or other decomposing lines. Finally, in the third step, for every CV of the remaining vertices, a new decomposing line is drawn in the direction of the equiangular line of the opposite angle of the current CV until it intersects with the boundary of the environment, obstacle, or another decomposing line, if no decomposing line is connected with the current CV or more than one decomposing line is already connected from another CV, and the created angle near the current CV is larger than \(180^{\circ}\). The OAECD can be properly applied in a static environment. Although a single-sensed map may generate noise, it can sense multiple times for the same environment in a short period and remove the noise on the map by the moving average method [20] or the median method [21]. Based on these methods, one can plan the route. However, this process is only accurate in the static environment. In the dynamic environment, it is difficult to resolve the sensor noise completely by the moving average method or the median method for the same position because the obstacle moves. Algorithms 5-7 show the pseudo code of the modified OAECD algorithm for each step in the process. Here, \(v_{c1}\) is a convex vertex of an obstacle; \(V_{c}\) is the set of point lists, which is the result of the EDP polygonal approximation of all obstacles; \(v_{a1}\) is the closest neighboring vertex from \(v_{c1}\); V is the set of all vertices of the obstacles; \(V_{check}\) is the point set to check for processing.