Interpolate a discrete grid of dots
<p>I'm referencing <a href="http://stackoverflow.com/questions/5146025/python-scipy-2d-interpolation-non-uniform-data">this question</a> and <a href="http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.interpolate.griddata.html" rel="nofollow">this documentation</a> in trying to turn a set of points (the purple dots in the image below) into an interpolated grid.</p>

<p><a href="http://i.stack.imgur.com/Qv412.png" rel="nofollow"><img src="http://i.stack.imgur.com/Qv412.png" alt="enter image description here"></a></p>

<p>As you can see, the image has missing spots where dots <em>should</em> be. I'd like to figure out where those are.</p>

<pre><code>import numpy as np
from scipy import interpolate

CIRCLES_X = 25 # There should be 25 circles going across
CIRCLES_Y = 10 # There should be 10 circles going down

points = []
values = []
# Points range from 0-800 ish X, 0-300 ish Y 
for point in points:
    points.append([points.x, points.y])
    values.append(1) # Not sure what this should be

grid_x, grid_y = np.mgrid[0:CIRCLES_Y, 0:CIRCLES_X]
grid = interpolate.griddata(points, values, (grid_x, grid_y), method='linear')
print(grid)
</code></pre>

<p>Whenever I print out the result of the grid, I get <code>nan</code> for all of my values.</p>

<p>Where am I going wrong? Is my problem even the correct use case for <code>interpolate.grid</code>?</p>

<p>First, your uncertain points are mainly at an edge, so it's actually <a href="http://stackoverflow.com/questions/2745329/how-to-make-scipy-interpolate-give-an-extrapolated-result-beyond-the-input-range">extrapolation</a>. Second, interpolation methods built into <code>scipy</code> deal with continuous functions defined on the entire plane and approximate it as a polynomial. While yours is discrete (1 or 0), somewhat periodic rather than polynomial and only defined in a discrete "grid" of points.</p>

<p><strong>So you have to invent some algorithm to inter/extrapolate your specific kind of function. Whether you'll be able to reuse an existing one - from <code>scipy</code> or elsewhere - is up to you.</strong></p>

<ul>
<li><p>One possible way is to <em>replace</em> it with some function (continuous or not) defined everywhere, then calculate that approximation in the missing points - whether as one step as <code>scipy.interpolate</code> non-class functions do or as two separate steps.</p>

<ul>
<li><p>e.g. you can use a 3-D parabola with peaks in your dots and troughs exactly between them. Or just with ones in the dots and 0's in the blanks and hope the resulting approximation in the grid's points is good enough to give a meaningful result (random overswings are likely). Then you can use <a href="http://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.RegularGridInterpolator.html#scipy.interpolate.RegularGridInterpolator" rel="nofollow"><code>scipy.interpolate.RegularGridInterpolator</code></a> for both inter- and extrapolation.</p></li>
<li><p>or as a harmonic function - then what you're seeking is <a href="http://docs.scipy.org/doc/scipy/reference/fftpack.html" rel="nofollow">Fourier transformation</a></p></li>
</ul></li>
<li><p>Another possible way is to go straight for a discrete solution rather than try to shoehorn the continual mathanalysis' methods into your case: design a (probably entirely custom) algorithm that'll try to figure out the "shape" and "dimensions" of your "grids of dots" and then simply fill in the blanks. I'm not sure if it is possible to add it into the <code>scipy.interpolate</code>'s harness as a selectable algorithm in addition to the built-in ones.</p></li>
</ul>

<p>And last but not the least. <strong>You didn't specify whether the "missing" points are points where the value is unknown or are actual part of the data - i.e. are incorrect data.</strong> If it's the latter, simple interpolation is not applicable at all as it assumes that all the data are strictly correct. Then it's a related but different problem: you can approximate the data but then have to somehow "throw away irregularities" (higher order of smallness entities after some point).</p>

python numpy scipy interpolation