[SciPy-User] Interpolate based on three closest points

[denis]

On Apr 21, 4:04 pm, Tom Foutz <tom.fo... at gmail.com> wrote:
> Hi everybody,
> I have an irregular mesh of ~1e5 data points, with unreliable connection
> data.  I am trying to interpolate based on these points.  
...

Tom,
  instead of iterating to a triangle containing the point of interest,
you could always take say 6 neighbors (see below),
then average their 6 values, distance-weighted as Anne suggests.
It's a clear speed / accuracy tradeoff: there's some chance
that a point is not in the convex hull of its 6 nearest neighbors,
but even then you're using 6 values, not 3.

What's the probability that N random points around the origin
land in >= 3 of 4 quadrants in 2d, or >= 5 of 8 octants in 3d ?
My back-of-the-envelope estimate of this probability (unchecked) is

    ndim  N  prob one-sided ~ 2*ndim/2^N ?
    ------------------------------------
    2   6   6 %
    3   6   9 %
    3   7   5 %

==> taking 6 neighbors or so is seldom one-sided.  Experts correct
me ?

By the way, exactly-N-nearest interpolation may have discontinuities.
Consider N+1 points on a circle around the point of interest:
the result depends on which N you take. In practice, not a problem.

Also, RBF of N initial points sets up and solves an N x N linear
system
so is impractical for large N.  Furthermore the matrix can be ill-
conditioned.

cheers
  -- denis