Given an irregularly arranged collection of pixels (point samples), interpolate the value of a point between betwen them. This has probably already been solved.
Easiest is nearest-neighbor. There are adventures to be had with clever data structures and algorithms to find the nearest neighbor. The region nearest each pixel is a Voronoi cell. On a sphere manifold, this problem comes up in converting between HEALpix and Tegmark icosahedron.
Next easiest is to compute the Delaunay triangulation (interestingly, the dual of Voronoi) of the pixels, then use a plane constructed on each triangle to interpolate values.
What is the next order interpolation? Probably something closer to Voronoi again.
For a square of grid pixels, the famous ones are bilinear and bicubic interpolation.