Sampling on the ${\cal C}_{free}$ boundary [22,26]

This scheme is based on the intuition that it is sometimes better to sample along the boundary, $\partial{\cal C}_{free}$, rather than waste samples on large areas of ${\cal C}_{free}$ that might be free of obstacles. Figure 5.29a shows one way in which this can be implemented. For each sample of ${\alpha }(i)$ that falls into ${\cal C}_{obs}$, a number of random directions are chosen in ${\cal C}$; these directions can be sampled using the ${\mathbb{S}}^n$ sampling method from Section 5.2.2. For each direction, a binary search is performed to get a sample in ${\cal C}_{free}$ that is as close as possible to ${\cal C}_{obs}$. The order of point evaluation in the binary search is shown in Figure 5.29a. Let $\tau: [0,1]$ denote the path for which $\tau(0) \in {\cal C}_{obs}$ and $\tau(1) \in {\cal C}_{free}$. In the first step, test the midpoint, $\tau(1/2)$. If $\tau(1/2) \in {\cal C}_{free}$, this means that $\partial{\cal C}_{free}$ lies between $\tau(0)$ and $\tau(1/2)$; otherwise, it lies between $\tau(1/2)$ and $\tau(1)$. The next iteration selects the midpoint of the path segment that contains $\partial{\cal C}_{free}$. This will be either $\tau(1/4)$ or $\tau(3/4)$. The process continues recursively until the desired resolution is obtained.