Circular propagation algorithm

Unfortunately, the above algorithm isn't always optimal, as illustrated in section . The reason for this is that the order used in the bucket sorting propagation, dist_E(dp), may be different from the metric order D(p). Indeed, the value of d_path isn't exactly m.d after m dilations by B_d, but may vary because of the discrete shape of B_d.
Therefore, it is more efficient to replace the bucket sorting propagation by a variant of Ragnelmam's circular propagation algorithm [127]. In this method, all pixels in the propagation front are stored in a single list, but are only propagated if the value of their distance is lower than a given threshold. If not, they are left in the list for later processing. After all pixels in the list have been considered for propagation with a given threshold, this threshold is incremented and the list is processed again.
For the B_d-geodesic DT, things are a little more complex. Indeed, in a non-convex domain, dist_e(dp+n) isn't always larger than dist_e(dp). In particular, when turning around a corner of the domain, it may decrease locally. A single list circular propagation could then create multiple propagation fronts. To handle this, we use two lists. list1 contains all pixels for which $D(p) \leq t$ and list2 those for which D(p) > t. The threshold t is only incremented once list1 is empty. The algorithm goes as follows.

Algorithm 9   B_d-geodesic DT by circular propagation.