Medial-axis sampling [455,635,971]

Figure 5.30: The medial axis is traced out by the centers of the largest inscribed balls. The five line segments inside of the rectangle correspond to the medial axis.
\begin{figure}\centerline{\psfig{file=figs/medial.idr,width=5.0in}}\end{figure}

Rather than trying to sample close to the boundary, another strategy is to force the samples to be as far from the boundary as possible. Let $ (X,\rho)$ be a metric space. Let a maximal ball be a ball $ B(x,r) \subseteq X$ such that no other ball can be a proper subset. The centers of all maximal balls trace out a one-dimensional set of points referred to as the medial axis. A simple example of a medial axis is shown for a rectangular subset of $ {\mathbb{R}}^2$ in Figure 5.30. The medial axis in $ {\cal C}_{free}$ is based on the largest balls that can be inscribed in $ \operatorname{cl}({\cal C}_{free})$. Sampling on the medial axis is generally difficult, especially because the representation of $ {\cal C}_{free}$ is implicit. Distance information from collision checking can be used to start with a sample, $ {\alpha }(i)$, and iteratively perturb it to increase its distance from $ \partial{\cal C}_{free}$ [635,971]. Sampling on the medial axis of $ W \setminus {\cal O}$ has also been proposed [455]. In this case, the medial axis in $ {\cal W}\setminus {\cal O}$ is easier to compute, and it can be used to heuristically guide the placement of good roadmap vertices in $ {\cal C}_{free}$.

Steven M LaValle 2020-08-14