Re: Integrating scattered data

[David Bateman]

Jordi Gutiérrez Hermoso wrote:
> On 21/08/07, Rupert Swarbrick <address@hidden> wrote:
>> Being marginally more helpful, I notice that Octave forge has code for
>> Delaunay triangulations, which might do what you need - if the surface
>> isn't too steep, I suspect you could triangulate and then sum the areas
>> under the triangles?
> 
> Yes, I mentioned the Delaunay triangulation in my original post, which
> gives a linearly good approximation to the actual integral. I was
> wondering if a quadratic approximation was feasible with current
> Octave functions or if I'd have to write such a function myself.
> 
> Oh, and my surface is integrable, which means it's almost continuous.
> ;-) It's probably also as smooth as you could want it, but it's very
> wavy. It is, in fact, a solution of the nonlinear shallow water wave
> equations, without shocks.
> 
> - Jordi G. H.

Gee this takes me back, I did pretty much this is my thesis. Essentially
if you want better than linear interpolation with your triangulation
you'll need to define additional abscissae for each patch defining the
curvature of the surface. For quadratic interpolation convenient
abscissae are on the edges of the patch. Chopping an reworking the
relevant bit of my thesis.

Each  triangular patch  $T_n$ can  then  be considered as the image of
a 1-1 mapping  ${\bf m_n}$ from a standard patch $\wp$.  Thus  $\wp$ is
the  parameterisation domain for $T_{n}$. The standard patch is given by

\begin{equation}
\wp = \{ (s,t) \mid 0 \leq s,t,s+t \leq 1 \}
\end{equation}

We consider   the  remapping from  a  curved   triangle to  a standard
triangle as an interpolation using a piecewise quadratic interpolation
function.   Each patch   on  the   surface   will use   a    different
interpolation function  which depends only  on some control points for
the  patch.  The  definition  of this interpolation   function is that
proposed by Atkinson~\cite{Atkinson88,Atkinson94}.  We now introduce 6
quadratic basis functions $\{ l_{j},j=1 \dots 6 \}$

\begin{equation}
  \begin{array}{lcllcllcl}
     l_{1}(s,t) &=& u(2u-1),&l_{2}(s,t) &=& t(2t-1),&l_{3}(s,t) &=&
s(2s-1) \\
     l_{4}(s,t) &=& 4tu,    &l_{5}(s,t) &=& 4st,    &l_{6}(s,t) &=& 4su
  \end{array}
\end{equation}

where  $u=1-s-t$ and $(s,t) \in \wp$.  We now introduce  the points in
$\wp$

\begin{equation}
  \begin{array}{lcllcllcl}
      q_{1} & = & (0,0)  \ & q_{2} & = & (0,1)  \  & q_{3} & = & (1,0)  \\
      q_{4} & = & (0,.5) \ & q_{5} & = & (.5,.5) \ & q_{6} & = & (.5,0)
  \end{array}
\end{equation}

These 6 points have the property that

\begin{equation}
l_{j}(q_{i}) = \delta_{ij}, \ i,j = 1, \cdots ,6
\end{equation}

Hence the $l_{j}$ are  quadratic basis functions for interpolation  at
the  points at $q_{i}$. The  relationship between $\wp$ and $T_{n}$ is
shown  in   the attached figure.  The  arbitrary  mapping  function
$m_{n}$ can be represented  by an  interpolation over these  quadratic
basis functions as

\begin{equation}
  \tilde{m}_{n}(s,t) = \sum_{j=1}^{6} V_{nj} l_{j}(s,t)
\end{equation}

where the  $V_{nj}$  are the control  points   on the shaped  triangle
$T_{n}$. These points $V_{n1}$, $V_{n2}$ and $V_{n3}$ are the vertices
on the shaped patch, and the other three points fall at the mid-points
of the shaped edges.

The surface area of the quadratically curved triangularly patched
surface is then

\begin{equation}
\int\!\!\int_{T_{n}} 1 . dS =
\int\!\!\int_{\wp}
\left | \frac{\partial \tilde{m}_{n}(s,t)}{\partial s} \times
 \frac{\partial \tilde{m}_{n}(s,t)}{\partial t} \right | dS
\end{equation}

Applying the quadratic interpolation to the Jacobian in the integral gives

\begin{equation}
 {\left | \frac{\partial {m}_{n}(s,t)}{\partial s} \times
  \frac{\partial m_{n}(s,t)}{\partial t} \right | }
 = \sum_{j=1}^{6}
 {\left | \frac{\partial {m}_{n}(q_{j})}{\partial s} \times
 \frac{\partial m_{n}(q_{j})}{\partial t} \right | } l_{j}(s,t)
\end{equation}


@manual{Atkinson88,
  title =        {User's guide to a boundary element package for solving
integral equations on piecewise smooth surfaces},
  author =       {K. E. Atkinson},
  organization = {University of Iowa},
  year =         {1988},
  note =         {ftp://ftp.math.uiowa.edu/pub/atkinson/bie.package},
}

@article{Atkinson90,
   author = {K. E. Atkinson and G. Chandler},
   title = {Boundary integral equation methods for solving Laplace's
equation with non-linear boundary conditions: The smooth boundary case},
   journal = {Mathematics of Computation},
   year = {1990},
   month = Oct,
   volume = {55},
   number = {192},
   pages = {451--472}
}

@article{Atkinson94,
   author = {K. E. Atkinson},
   title = {The numerical solution of a non-linear boundary integral
equation on smooth surfaces},
   journal = {Ima journal of numerical analysis},
   year = {1994},
   month = Oct,
   volume = {14},
   number = {4},
   pages = {461--483}
}

I hope that's enough info to help :-)

Cheers
David

remap.eps
Description: PostScript document