title: Python how to interpolate large point clouds of 2D data
body: <p>So let's say I have a point cloud of data in the form of 
      Z = f(X, Y)</p>
  
  <p>The problem is that I have millions of points, with data that is extremely fine in some (X,Y) regions and extremely sparse in other regions. </p>
  
  <p>Ideally the interpolated solution needs to be continuous, and as  smooth as possible. The application is for finite element analysis.  </p>
  
  <p>I've tried:</p>
  
  <ul>
  <li>Instead of interpolating I use a KDTree to average nearest nodes. This works very well for points in the fine region but not so well at sparse regions, because discontinuities in the result may arise.  </li>
  <li>scipy.interpolate.XXX - 2d functions run into memory error. scipy libraries aren't capable of interpolating large numbers of points. </li>
  </ul>
  
  <p>I'm thinking the best way is some sort of hacked up combination of KDTree average nearest nodes and then some sort of interpolation for far away points, but I'm thinking that interpolating millions of points ought to be solved problem... </p>
  
  <p>Anybody have any good ideas on what to do? </p>