## 3 Proposed Post Triangular Processing of the Midpoint Interpolation Method
It is determined whether the distance between \(q_{child}\) and \(q_{m ancestor}\) is free from obstacle collision (_isTrapped_() function). If it is free from collision, it is called _postTriangular_(); otherwise, it is called _interpolation_(). _postTriangular_() connects \(q_{child}\) and \(q_{m ancestor}\) as in the triangular rewiring method [8], and the \(q_{parent}\) between them is deleted from the path. _interpolation_() finds (interpolates) the points between \(q_{child}\) and \(q_{parent}\) and between \(q_{parent}\) and \(q_{ ancestor}\) that are free from obstacle collision when connected and rewires \(q_{child}\), \(q_{m ancestor}\), and those two points are found. If \(R\) and \(t\) are updated due to _postTriangular_() or _interpolation_(), \(q_{child}\) (the \(t\)-th waypoint of \(R\)), \(q_{parent}\), and \(q_{m ancestor}\) are updated accordingly. If \(q_{parent}\) is the last point in \(R\), \(f_{modify}\) is checked. Otherwise, the above process is repeated for the updated \(q_{child}\) and \(q_{m ancestor}\). Here, path modification by _postTriangular_() deletes the waypoints and makes a more optimal path but has the effect of sharpening the path shape, and path modification by _interpolation_() creates a new waypoint between the waypoints. Adding/inserting has the effect of making a more optimal path while also smoothing the path shape. Of course, due to the effect of making a more optimal path, path modification by _postTriangular_() is more efficient than that by _interpolation_(). The input values of _postTriangular_() of the post triangular processing of the midpoint interpolation method consist of the path \(R\), the focusing point index \(t\), and the path modification \(f_{modify}\) from the post triangular processing of midpoint interpolation method. Rewiring is performed on the \(t\)-th waypoint \(q_{child}\) of \(R\), the next point \(q_{parent}\), and the next point \(q_{m ancestor}\) of that point again. First, the path between \(q_{child}\) and \(q_{parent}\) and the path between \(q_{parent}\) and \(q_{m ancestor}\) are deleted. Then the path is inserted between \(q_{child}\) and \(q_{m ancestor}\). Finally, \(f_{modify}\) returns \"true\" because the path has been modified. Here, Path \(<\)\(A\), \(B\)\(>\) means a partial path from Waypoint A to Waypoint B in the complete path. ```
Input:\(R\leftarrow\) path R from postTriProCOfMidInterpolation \(t\leftarrow\) point index \(t\) from postTriProCOfMidInterpolation \(f_{modify}\leftarrow\) boolean\(f_{midify}\) from postTriProCOfMidInterpolation Output:\(R\leftarrow\) modified path R \(f_{modify}\leftarrow\) result of boolean\(f_{midify}\)//return by reference Procedure postTriangular From postTriProCOfMidInterpolation Begin \(q_{child}\gets t\)-th point in \(R\) \(q_{parent}\leftarrow\) next point of \(q_{child}\) in \(R\) \(q_{ancestor}\leftarrow\) next point of \(q_{parent}\) in \(R\) \(R\leftarrow\)Delete path<\(q_{child}\), \(q_{parent}\)> and path<\(q_{parent}\), \(q_{ancestor}\)> from \(R\) \(R\leftarrow\) Insert path<\(q_{child}\), \(q_{ancestor}\)> to \(R\) \(f_{midify}\leftarrow\)true End
```  
**Algorithm 4** Pseudocode of Proposed Post Triangular Function  
The goal of the proposed post triangular processing of midpoint interpolation method is to find an interpolation point (\(m_{F}(q_{0})\), \(m_{F}(q_{1})\)) free from obstacle collisions between waypoints (\(q_{0}\)-\(q_{1}\), \(q_{1}\)-\(q_{2}\)) while descending in the direction of the midpoint (\(q_{1}\)), as shown in Figure 6 in the interpolation process. However, the interpolation point \(m_{F}\) follows Equation (4):  
\[m_{F}(q_{i},k)=\left\{ \begin{array}{cc}\Big{(}\frac{m_{F}(q_{i},k-1),x+\xi(q_ {i}),x}{2},\frac{m_{F}(q_{i},k-1),y+\xi(q_{i}),y}{2}\Big{)},&k>0\\ q_{i},&k=0\end{array} \right.