% Geometric intuition of the convex decomposition (supplement S-IV).
% All coordinates are computed by calc_convex.py from
%   eq:sup_ellipsoid_quadratic  and  eq:sup_halfspace_normal
% and pasted here verbatim; do not hand-edit the numbers.
\documentclass[tikz,border=1pt]{standalone}
\input{figstyle}

\tikzset{
  obst/.style={circle, fill=sitec, inner sep=0pt, minimum size=1.7pt},
  obstx/.style={circle, draw=sitec, line width=0.3pt, fill=white,
                inner sep=0pt, minimum size=1.7pt},
  hsp/.style={corrc, line width=0.35pt, dash pattern=on 1.4pt off 1.0pt},
  ell/.style={parkc, line width=0.6pt},
  sph/.style={sitec, line width=0.35pt, dash pattern=on 1.0pt off 1.0pt},
  segl/.style={exitc, line width=1.0pt},
}
\newcommand{\allobst}{%
  \foreach \x/\y in {0.30/1.42, 3.75/1.62, 4.85/1.35, 1.90/-1.62,
                     4.35/-1.45, 5.35/-1.02, -0.55/0.85}
    {\node[obst] at (\x,\y) {};}%
  \foreach \x/\y in {3.10/-1.12, 1.35/1.05, 2.55/1.28, 5.75/0.62,
                     0.65/-1.30, -1.05/0.12, 6.35/-0.18}
    {\node[obst] at (\x,\y) {};}%
}

\begin{document}
\begin{tikzpicture}[scale=0.50]

% ============================ panel (a) ==================================
\begin{scope}
  \begin{scope}
    \clip (-1.45,-2.80) rectangle (6.65,2.80);
    % initial sphere: radius = segment half-length, before the minor-axis shrink
    \draw[sph] (2.600,0) circle [radius=2.6000];
    % collision-free ellipsoid after shrinking along the minor axis
    \draw[ell, fill=parkc, fill opacity=0.10] (2.600,0)
          ellipse [x radius=2.6000, y radius=1.1413];
  \end{scope}
  % shrink direction along the minor axis
  \foreach \s in {1,-1}
    {\draw[line width=0.35pt, ->, >={Latex[length=1.0mm,width=0.8mm]}]
       (2.600,\s*2.45) -- (2.600,\s*1.30);}
  % the path segment, fully enclosed by the ellipsoid
  \draw[segl] (0,0) -- (5.200,0);
  \node[obst, fill=exitc] at (0,0) {};
  \node[obst, fill=exitc] at (5.200,0) {};
  \node[obst, fill=black] at (2.600,0) {};
  \allobst
  % the obstacle that stops the shrink lies exactly on the boundary
  \draw[confc, line width=0.45pt] (3.100,-1.120) circle [radius=0.19];
  \node[annt, anchor=north] at (0.00,-0.10) {$\mathbf{p}_0$};
  \node[annt, anchor=north] at (5.20,-0.10) {$\mathbf{p}_1$};
  \node[annt, anchor=south west] at (2.62,0.04) {$\mathbf{d}$};
  \node[annt, parkc, anchor=south] at (2.60,1.20) {$\mathcal{E}$};
  \node[annt, confc, anchor=north west] at (3.28,-1.22) {$\mathbf{o}_i$};
  \node[annt, sitec, anchor=south east] at (4.60,1.95) {initial sphere};
  \node[panel, anchor=north] at (2.60,-2.95) {(a)};
\end{scope}
% ============================ panel (b) ==================================
\begin{scope}[shift={(9.4,0)}]
  % convex polytope P = { p | A p <= b }, 7 retained half-spaces
  \fill[corrc, fill opacity=0.13]
       (-1.201,-0.765) -- (0.732,-1.324) -- (6.182,-0.855) --
       (6.393,-0.009) -- (5.057,1.299) -- (2.346,1.278) --
       (-0.983,0.515) -- cycle;
  \draw[corrc, line width=0.6pt]
       (-1.201,-0.765) -- (0.732,-1.324) -- (6.182,-0.855) --
       (6.393,-0.009) -- (5.057,1.299) -- (2.346,1.278) --
       (-0.983,0.515) -- cycle;
  \begin{scope}
    \clip (-1.45,-2.80) rectangle (6.65,2.80);
    % supporting half-space boundaries, tangent to the ellipsoid metric
    \draw[hsp] (-8.848,-2.148) -- (9.085,-0.605); % o_7
    \draw[hsp] (8.611,2.716) -- (-8.933,-1.309);  % o_1
    \draw[hsp] (8.990,1.328) -- (-9.009,1.193);   % o_2
    \draw[hsp] (9.555,-3.105) -- (-3.307,9.487);  % o_11
    \draw[hsp] (-8.943,1.473) -- (8.349,-3.525);  % o_5
    \draw[hsp] (0.474,9.049) -- (-2.554,-8.694);  % o_12
    \draw[hsp] (3.846,-10.233) -- (8.197,7.233);  % o_13
    \draw[ell, dash pattern=on 1.2pt off 1.0pt] (2.600,0)
          ellipse [x radius=2.6000, y radius=1.1413];
  \end{scope}
  \draw[segl] (0,0) -- (5.200,0);
  % retained obstacles: solid; pruned as redundant: hollow
  \foreach \x/\y in {0.30/1.42, 3.75/1.62, 4.85/1.35, 1.90/-1.62,
                     4.35/-1.45, 5.35/-1.02, -0.55/0.85}
    {\node[obstx] at (\x,\y) {};}
  \foreach \x/\y in {3.10/-1.12, 1.35/1.05, 2.55/1.28, 5.75/0.62,
                     0.65/-1.30, -1.05/0.12, 6.35/-0.18}
    {\node[obst] at (\x,\y) {};}
  % one normal drawn from its tangency anchor to the generating obstacle
  \draw[line width=0.35pt, ->, >={Latex[length=1.0mm,width=0.8mm]}]
       (2.555,1.141) -- (2.55,1.28);
  \node[annt, anchor=west] at (2.70,1.62)
       {$\mathbf{a}_i^{\!\top}\mathbf{p}=b_i$};
  \node[annt, corrc, anchor=north east] at (6.30,-0.95) {$\mathcal{P}$};
  \node[panel, anchor=north] at (2.60,-2.95) {(b)};
\end{scope}
\end{tikzpicture}
\end{document}