A polyhedral C-space obstacle

Most of the previous ideas generalize nicely for the case of a polyhedral robot that is capable of translation only in a 3D world that contains polyhedral obstacles. If $ {\cal A}$ and $ {\cal O}$ are convex polyhedra, the resulting $ {\cal C}_{obs}$ is a convex polyhedron.

Figure 4.20: Three different types of contact, each of which generates a different kind of $ {\cal C}_{obs}$ face.
\begin{figure}\begin{center}
\begin{tabular}{ccc}
\psfig{file=figs/typeFV.eps,wi...
...uein} \\
Type FV & Type VF & Type EE \\
\end{tabular}
\end{center}\end{figure}

There are three different kinds of contacts that each lead to half-spaces in $ {\cal C}$:

  1. Type FV: A face of $ {\cal A}$ and a vertex of $ {\cal O}$
  2. Type VF: A vertex of $ {\cal A}$ and a face of $ {\cal O}$
  3. Type EE: An edge of $ {\cal A}$ and an edge of $ {\cal O}$ .
These are shown in Figure 4.20. Each half-space defines a face of the polyhedron, $ {\cal C}_{obs}$. The representation of $ {\cal C}_{obs}$ can be constructed in $ O(n + m + k)$ time, in which $ n$ is the number of faces of $ {\cal A}$, $ m$ is the number of faces of $ {\cal O}$, and $ k$ is the number of faces of $ {\cal C}_{obs}$, which is at most $ nm$ [411].

Steven M LaValle 2012-04-20