# TA-RRT*: Adaptive Sampling-Based Path Planning Using Terrain Analysis
## 3 Proposed Method
### Terrain-Based Step Size Adaptation
#### 3.3.1 Terrain Density  
In this study, the terrain complexity is quantified by converting the terrain into a BEV image and subsequently into a grid map, where the number of detected corners indicates the complexity. If obstacles are represented in the BEV, they can be identified, allowing for the generation of paths that avoid them. First, the terrain corners \(C\) around \(q_{\text{nearest}}\) are identified to calculate the terrain density \(\rho\). Here, \(\rho\) is defined as the number of terrain corners, serving as a measure of terrain complexity. A higher \(\rho\) indicates a more complex terrain with many corners, while a lower \(\rho\) indicates a simpler terrain. A k-dimensional (KD) tree is utilized to calculate \(\rho\) efficiently. This data structure partitions the space recursively at each level of the tree, alternating dimensions for division [25]. By using a KD tree, the number of terrain corners within a given radius can be quickly determined by narrowing the search range.  
Figure 3(a) shows an example of the searching result for corners within a radius around a reference point using a KD tree. The gray area represents the terrain (obstacle), and the red dots represent the corners. The KD tree recursively partitions the space, with black and blue dashed lines representing horizontal and vertical divisions. The purple dot and dashed circle represent the reference point and its radius, while the green dots indicate corners within that radius. First, since the variance of the detected corners along the X-axis is greater than that along the Y-axis, the first partition is performed based on the X-axis. At this stage, these nodes are sorted along the X-axis, and the median node (5, 9) is selected as the partitioning point, dividing the space along the X-axis (black dashed line). Next, for the nodes within the left and right subspaces of node (5, 9), these nodes are sorted along the  
Figure 3: Examples of (**a**) the corner detection result, where red points represent identified corners, and (**b**) the PDF derives from the result of (**a**).  
Y-axis, and the median nodes (1, 5) and (8, 2) are chosen to partition the subspaces along the Y-axis (blue dashed lines), respectively. This process continues recursively, alternating between the X-axis and Y-axis at each depth level in the KD tree.  
Figure 4b illustrates the tree structure based on these partitions as shown in Figure 4a. The first partition node (5, 9) becomes the root node of the KD tree. Its child nodes are the median nodes of the left and right subspaces, (1, 5) and (8, 2), respectively. This process is recursively applied to each subspace to construct the tree structure. Then, using the constructed tree, the number of corners \(\rho\) within the radius \(R\) around \(q_{\text{nearest}}\) is calculated. For example, as shown in Figure 4a, when the reference point is \(q_{\text{nearest}}=(2,6)\) and \(R=2\), neither node (5, 9) nor the line dividing the space intersects with the radius. Therefore, as shown in Figure 4b, node (8, 2) and its subordinate nodes are not examined, which allows the KD tree to reduce the computation time for determining terrain density.