|
To construct an $l$-connected DSGP from a voxel $s\in\ds{m}$ to a voxel $t\in\ds{m}$,
the algorithm iteratively computes the set of voxels that are $l$-connected to $s$,
belong to $\dsrp{m,n}{s,t}$, and ensure the direction towards $t$.
Then it executes a Prioritized-BFS to get a/the $l$-connected shortest path while
minimizing its maximum isothetic distance from $\rp{s,t}$.
The adjacency list $L$ of the underlying undirected graph $G(V,E)$ is prepared
based on $l$-adjacency of the voxels in $\dsrp{m,n}{s,t}$.
The list $L$ is not prepared for the entire set $\dsrp{m,n}{s,t}$ but only for
the part of $\dsrp{m,n}{s,t}$ starting from $s$ and ending at $t$.
The voxels adjacent to each voxel $p\in V$ are inserted in the adjacency chain
$L[p]$ of $p$ in non-decreasing order of their isothetic distances from
$\rp{s,t}$.
This is needed to maintain locally minimum isothetic distance from $\rp{s,t}$
while running Prioritized-BFS.
To maintain the global minimum isothetic distance from $\rp{s,t}$ throughout the
path $\gp{l}{m,n}{s,t}$, we use dynamic programming.
We keep track of a variable $\delta(p,\gp{l}{m,n}{s,t})$ associated with each voxel $p$
in the traversed set, using the following recurrence.
\[
\delta\left(p,\gp{l}{m,n}{s,t}\right) = \left\{
\begin{array}{l@{}l}
0 & \mbox{if $p=s$}\\
\max\bigg(\id\left(p,\rp{s,t}\right),\min
\limits_{q\in \vadj{l}{p}}\left
\{\delta \left( q,\gp{l}{m,n}{s,t} \right)\right\}\bigg)& \mbox{otherwise}
\end{array}\right.
\]
where $\vadj{l}{p}$ denotes the set of $l$-neighbors of $p$ that have been
visited by the algorithm on reaching $p$.
Figure on left:
Discrete spherical geodesics and their corresponding circles for $r=30$, class NS, $l=1$.
The sequence of red voxels is $\gp{1}{1,2}{s,t}$ with $s(8,25,14)\in\qoct{6}$ and
$t(29,3,6)\in\qoct{3}$, which, when combined
with $\gp{1}{1,2}{t,s}$, shown in yellow, yields the discrete 3D geodesic circle passing through $s$, $t$,
and centered at $o$.
Shown in blue are 16 longitude circles produced by extending the geodesics from source points
taken from the discrete great circle on $zx$-plane to destination point $t(0,30,0)$ for each.
|
