Piecewise linear continuation

The contour plotting problem is to find the zeros (contours) of ${\displaystyle f(x,y)=0\,}$ (${\displaystyle f(\cdot )\,}$ a smooth scalar valued function) in the square ${\displaystyle 0\leq x\leq 1,0\leq y\leq 1\,}$,

The square is divided into small triangles, usually by introducing points at the corners of a regular square mesh ${\displaystyle ih_{x}\leq x\leq (i+1)h_{x}\,}$, ${\displaystyle jh_{y}\leq y\leq (j+1)h_{y}\,}$, making a table of the values of ${\displaystyle f(x_{i},y_{j})\,}$ at each corner ${\displaystyle (i,j)\,}$, and then dividing each square into two triangles. The value of ${\displaystyle f(x_{i},y_{j})\,}$ at the corners of the triangle defines a unique Piecewise Linear interpolant ${\displaystyle lf(x,y)\,}$ to ${\displaystyle f(\cdot )\,}$ over each triangle. One way of writing this interpolant on the triangle with corners ${\displaystyle (x_{0},y_{0}),~(x_{1},y_{1}),~(x_{2},y_{2})\,}$ is as the set of equations

${\displaystyle (x,y)=(x_{0},y_{0})+(x_{1}-x_{0},y_{1}-y_{0})s+(x_{2}-x_{0},y_{2}-y_{0})t\,}$

${\displaystyle 0\leq s\,}$

${\displaystyle 0\leq t\,}$

${\displaystyle s+t\leq 1\,}$

${\displaystyle lf(x,y)=f(x_{0},y_{0})+(f(x_{1},y_{1})-f(x_{0},y_{0}))s+(f(x_{2},y_{2})-f(x_{0},y_{0}))t\,}$

The first four equations can be solved for ${\displaystyle (s,t)\,}$ (this maps the original triangle to a right unit triangle), then the remaining equation gives the interpolated value of ${\displaystyle f(\cdot )\,}$. Over the whole mesh of triangles, this piecewise linear interpolant is continuous.

The contour of the interpolant on an individual triangle is a line segment (it is an interval on the intersection of two planes). The equation for the line can be found, however the points where the line crosses the edges of the triangle are the endpoints of the line segment.

The contour of the piecewise linear interpolant is a set of curves made up of these line segments. Any point on the edge connecting ${\displaystyle (x_{0},y_{0})\,}$ and ${\displaystyle (x_{1},y_{1})\,}$ can be written as

${\displaystyle (x,y)=(x_{0},y_{0})+t(x_{1}-x_{0},y_{1}-y_{0}),\,}$

with ${\displaystyle t\,}$ in ${\displaystyle (0,1)\,}$, and the linear interpolant over the edge is

${\displaystyle f\sim f_{0}+t(f_{1}-f_{0})\,}$

So setting ${\displaystyle f=0\,}$

${\displaystyle t=-f_{0}/(f_{1}-f_{0})\,}$ and ${\displaystyle (x,y)=(x_{0},y_{0})-f_{0}*(x_{1}-x_{0},y_{1}-y_{0})/(f_{1}-f_{0})\,}$

Since this only depends on values on the edge, every triangle which shares this edge will produce the same point, so the contour will be continuous. Each triangle can be tested independently, and if all are checked the entire set of contour curves can be found.

Piecewise linear continuation is similar to contour plotting (Dobkin, Levy, Thurston and Wilks),[5] but in higher dimensions. The algorithm is based on the following results:

Lemma 1

If F(x) maps ${\displaystyle \mathbb {R} ^{n}}$ into ${\displaystyle \mathbb {R} ^{n-1}}$, there is a unique linear interpolant on an '(n-1)'-dimensional simplex which agrees with the function values at the vertices of the simplex.

An '(n-1)'-dimensional simplex has n vertices, and the function F assigns an 'n'-vector to each. The simplex is convex, and any point within the simplex is a convex combination of the vertices. That is:

If x is in the interior of an (n-1)-dimensional simplex with n vertices ${\displaystyle v_{i}}$, then there are positive scalars ${\displaystyle 0<\alpha _{i}}$ such that

${\displaystyle \mathbf {x} =\sum _{i}\alpha _{i}\mathbf {v} _{i}}$

${\displaystyle \sum _{i}\alpha _{i}=1.\,}$

If the vertices of the simplex are linearly independent the non-negative scalars ${\displaystyle \alpha }$ are unique for each point x, and are called the barycentric coordinates of x. They determine the value of the unique interpolant by the formula:

${\displaystyle LF=\sum _{i}\alpha _{i}F(\mathbf {v} _{i})}$

Lemma 3

There is a triangulation (the Coxeter-Freudenthal-Kuhn triangulation [1]) which is invariant under the pivot operation ${\displaystyle P_{v_{i}}(v_{0},v_{1},...,v_{n}):=(v_{0},v_{1},...,v_{i-1},{\tilde {v}}_{i},v_{i+1},...,v_{n})}$ where ${\displaystyle {\tilde {v}}_{i}=\left\{{\begin{array}{lcl}v_{1}+v_{n}-v_{0}&&i=0\\v_{i+1}+v_{i-1}-v_{i}&\qquad \qquad &0\\v_{n-1}+v_{0}-v_{n}&&i=n\\\end{array}}\right.}$