This scheme is based on the intuition that it is sometimes better to sample along the boundary, , rather than waste samples on large areas of that might be free of obstacles. Figure 5.29a shows one way in which this can be implemented. For each sample of that falls into , a number of random directions are chosen in ; these directions can be sampled using the sampling method from Section 5.2.2. For each direction, a binary search is performed to get a sample in that is as close as possible to . The order of point evaluation in the binary search is shown in Figure 5.29a. Let denote the path for which and . In the first step, test the midpoint, . If , this means that lies between and ; otherwise, it lies between and . The next iteration selects the midpoint of the path segment that contains . This will be either or . The process continues recursively until the desired resolution is obtained.
Steven M LaValle 2012-04-20