search

tylerjereddy / scipy

Scipy library main repository
http://scipy.org/scipylib/
BSD 3-Clause "New" or "Revised" License
1 stars 1 forks source link

Natural Neighbor aka. Voronoi Interpolation for Sphere #16

Closed fietew closed 4 years ago

fietew commented 8 years ago

Hi Tyler,

I was just wondering if and how the Spherical Voronoi could be extended to compute the natural neighbor interpolation (https://en.wikipedia.org/wiki/Natural_neighbor) weights for an ensemble of points on a spherical surface given a query point.

tylerjereddy commented 8 years ago

Yes, I think it should be possible. Note that you're posting this issue in an old fork of scipy which we don't really use -- the SphericalVoronoi code is now integrated into the scipy master branch -- and will be officially released with scipy 0.18 soon (so use the scipy master branch, not this fork, for the spherical Voronoi stuff).

As a rough outline of a possible approach:

  1. Calculate the spherical Voronoi diagram using scipy.spatial.SphericalVoronoi (the docs are here: http://scipy.github.io/devdocs/generated/scipy.spatial.SphericalVoronoi.html)
  2. Add your query point on the surface of the sphere and calculate the new spherical Voronoi diagram with N + 1 points.
  3. Identify the Voronoi cells that neighbour the query point in the second spherical Voronoi diagram (all Voronoi regions that share at least one vertex would be neighbours, for example).
  4. Calculate the spherical polygon surface areas for each of the neighbour Voronoi regions (see: https://github.com/scipy/scipy/issues/6069 ).
  5. Identify the Voronoi regions in the first spherical Voronoi diagram that correspond to the neighbours in the second diagram (they have the same input point).
  6. Calculate the spherical polygon surface areas for each of the Voronoi cells identified in step 5, as described at the link above.
  7. It should be clear that the areas from the first Voronoi diagram will be larger. When you subtract the areas of the second Voronoi diagram regions from the corresponding areas in the first, you'll get the amount of 'stolen area' in each neighbouring Voronoi cell. Divide the stolen area by the original area of the cell to get the weight. In formulaic form: weight = (area_Voronoi_cell_diagram_1 - area_Voronoi_cell_diagram_2) / area_Voronoi_cell_diagram_1

Of course, I'm only doing this off the top of my head. If you think this would be sufficiently useful in your field of work to justify integration into i.e., scipy.interpolate (http://docs.scipy.org/doc/scipy-0.17.0/reference/interpolate.html) then we should probably open an issue on the scipy repo proper. We would need some good unit tests and this code would depend on the area calculation issue above, and by extension producing nice plots of this stuff can still be tricky on a sphere (see: https://github.com/matplotlib/matplotlib/pull/6248 ).