Computing the shortest path from the B_d-geodesic DT

In [93], the shortest path between pixels q and r is found as follows. First, the geodesic distance from q is computed. Then, the path is generated by steepest descent from r. Pixel r is the first point of the path, then the neihgbor of r with the smallest distance value, then the neighbor's neighbor, and so on until q is reached.
Using the B_d-geodesic distance transformation in the first step, the steepest descent cannot be used to backtrack the distance propagation from r to q. Indeed, around corners of the domain, D(p) may have local minima when the obstacles are smaller than B_d. Instead, we chose to store explicitely the origin of the propagation for each pixel, that is pixel p_m-1 in eq. (). The distance propagation can then be easily backtracked by iteratively looking up the origin of the current last pixel in the path. The algorithm goes as follows

Algorithm 10   Computes the shortest path between two points.

The core of the algorithm is highly similar to that of section , with the only additional line marked by $\{ * \}$. The initialization is modified to take q as the only object pixel. The path generation step is of course new. Note that it can be used to generate paths from any pixel r to the same target q.
The result of this algorithm is illustrated at figure and the synthetic 2D data used in figures and .

  

Figure 9.3: Shortest path. Left: Domain and points to link Right: path computed by the path-planning algorithm with d = 6.