# Example: Using signed distance functions to embed contours in discrete grids

Published 2012-02-26 | Author: Josh Chang

The figure demonstrates the embedding of an interface $\partial\Omega$ into a discrete grid using the signed Euclidean distance function. The distances are computed using 4 iterations of a Newton-Raphson algorithm. The image is similar to the one in my paper:

@article{chang2010tracking,
title={Tracking monotonically advancing boundaries in image sequences
using graph cuts and recursive kernel shape priors},
author={Chang, J. and Chou, T. and Brennan, K.},
journal={Medical Imaging, IEEE Transactions on},
number={99},
pages={1--1},
year={2010},
publisher={IEEE}
}
The example is based on the SWAN wave model example by Marco Miani.

Do you have a question regarding this example, TikZ or LaTeX in general? Just ask in the LaTeX Forum.
Oder frag auf Deutsch auf TeXwelt.de. En français: TeXnique.fr.

% Using signed distance functions to embed contours in discrete grids
% Author: Josh Chang
\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{positioning}
\usetikzlibrary{calc}
\usetikzlibrary{arrows,shapes,backgrounds}
\begin{document}
\begin{tikzpicture}[scale=2,every node/.style={minimum size=1cm},on grid]

% slanting: production of a set of n 'laminae' to be piled up.
% N=number of grids.
\begin{scope}[
yshift=-100,every node/.append style={
yslant=0.5,xslant=-1.3},yslant=0.5,xslant=-1.3
]
% opacity to prevent graphical interference
\fill[white,fill opacity=0.9] (0,0) rectangle (4,4);
\draw[step=4mm, thin, gray] (0,0) grid (4,4); %defining grids
\draw[black,very thick] (0,0) rectangle (4,4);%marking borders
\draw [ultra thick](0,1) parabola bend (2,2) (4,1)  ; % parabola curve

\coordinate (sphi) at (0.6,3.4);
\node at (sphi) [fill=black,circle,scale=0.1] {$s$};

\pgfkeys{/pgf/number format/.cd, fixed, zerofill, precision =1}

\foreach \x in {0,...,9} {
\foreach \y in {0,...,9} {
%calculate the signed distance
%
% use newton raphson for 4 iterations to compute the distance
%
\pgfmathparse{0.2+0.4*\x}
\pgfmathresult \let\xpoint\pgfmathresult;
\pgfmathparse{0.2+0.4*\y}
\pgfmathresult \global\let\ypoint\pgfmathresult;

\pgfmathparse{\xpoint}
\pgfmathresult \global\let\xx\pgfmathresult;
% Run 4 iterations of Newton-Raphson to compute distance
\foreach \iter in {1,...,4} {
\pgfmathparse{0.25*(\xx*\xx*\xx-6*\xx*\xx+4*(\xx-2)*\ypoint
+12*\xx-8*\xpoint+8)}
\pgfmathresult \let\functionderv\pgfmathresult;
\pgfmathparse{3*(\xx-2)*(\xx-2)/4+\ypoint}
\pgfmathresult \let\functiondervv\pgfmathresult;
\pgfmathparse{\xpoint-\functionderv/(\functiondervv)}
\pgfmathresult \let\xx\pgfmathresult;
}

\pgfmathparse{-\xx*\xx/4+\xx+1}
\pgfmathresult \global\let\yy\pgfmathresult;
\pgfmathsetmacro{\dd}{sqrt((\xpoint-\xx)* (\xpoint-\xx)
+ (\ypoint-\yy)*(\ypoint-\yy ))/.4};
\pgfmathparse{int(\yy*100)}
\pgfmathresult \let\yyy\pgfmathresult;
\pgfmathparse{int(\ypoint*100)}
\pgfmathresult \let\yypoint\pgfmathresult;
\ifnum \yyy > \yypoint { %% Signed distance
\pgfmathparse{-\dd} \pgfmathresult \global\let\dd\pgfmathresult;
}
\fi
\node[scale=0.7,thick] at (\xpoint,\ypoint)
{$\mathbf{\pgfmathprintnumber{\dd}}$};
}
}

\end{scope}

\begin{scope}[
yshift=-160,every node/.append style={
yslant=0.5,xslant=-1.3},yslant=0.5,xslant=-1.3
]
%marking border
\draw[black,very thick] (0,0) rectangle (4,4);

%draw bottom parabola
\draw [ultra thick](0,1) parabola bend (2,2) (4,1)  ;
\draw[-latex,thick](2.8,1)node[right,scale=1.5]{$\partial\Omega$}
to[out=180,in=270] (2,1.99);

\node at (2,0.5) [scale=1.5] {$\Omega$};
\node at (1.2,2.7) [scale=1.5] {$S\setminus\Omega$};
\coordinate (s) at (0.5,3.5);
\node at (s) [fill=black,circle,scale=0.1] {$s$};

\end{scope} %end of drawing grids

% signed distance
\draw[-latex,thick](4.8,-.2)node[above,scale=1.3]{$\phi_\Omega$}
to[out=-90,in=0] (4.1,-1.5);

% s
\draw[-latex,thick](-4,-.2)node[left,scale=1.3]{$\phi_\Omega(s)$}
to[out=0,in=90] (sphi);

%s
\draw[-latex,thick](-4,-3)node[left,scale=1.3]{$s$}
to[out=0,in=90] (s);
\end{tikzpicture}
\end{document}


• #1 Yan, March 9, 2012 at 4:29 p.m.

Newton-Raphson algorithm in TeX, wow... My nerdy side is flabbergasted in a good way. Incidentally, it shows how overly complicated the TeX syntax becomes once you start "abusing" its original purpose.

• #2 Josh, May 18, 2012 at 10:22 p.m.

Thank you for your kind comment Yan. I figured that learning how to write a loop would be a lot more time efficient than having the enter the numbers in 1 by 1!

Also, here is an updated bibtex for the paper containing the cousin of this figure, the one above was before publication:

@article{chang2012tracking, title={Tracking monotonically advancing boundaries in image sequences using graph cuts and recursive kernel shape priors}, author={Chang, J. and Chou, T. and Brennan, K.}, journal={Medical Imaging, IEEE Transactions on}, volume={13}, number={5}, pages={1008--1020}, year={2012}, publisher={IEEE} }

• #3 ChriSopht, June 4, 2012 at 4:37 p.m.

Hm, the upper left corner is sqrt(5^2+2^2) cells away from a cell which is 0.1 away from the grid. By the triangle inequality it can't be farer away than about 5.5. It appears as if you just computed the distance in y-direction 