Suggested Feature : Spatial Hashing and Point Cloud Interpolation

[fluidnumerics-joe]

Proposed new feature or change:

While working to add support for unstructured grids in Parcels, we're at the stage of looking at methods for interpolation onto particle positions from the unstructured grid. The method we're looking at uses spatial hashing.

Essentially, spatial hashing works by overlaying a fictitious uniform structured grid over the unstructured grid. This fictitious uniform grid is defined simply by a uniform grid spacing, lower left corner lat/lon, and the number of grid points. A hash table is then constructed that relates the face id's in the unstructured grid to the hash indices (i,j) by determining which faces overlap the uniform grid faces.

When doing interpolation onto particle positions, the particle position (x,y) is used to calculate a hash index (i,j) which tells us which grid cell in the uniform grid it is within. From this, the hash table provides a lookup table to determine what faces in the unstructured grid to search within. As a result of the search method, we get the face id of the (x,y) location for the particle position and the barycentric coordinates within the face.

I understand that UXArray provides KDTree and BallTree search methods for this kind of lookup. For UXArray, we would be interested in having a "SpatialHashing" structure, similar to the KDTree and BallTree that helps facilitate the element search to align an (x,y) point with a face ID and barycentric coordinates for interpolation.

If this is something the UXArray team is interested in maintaining, I have code and the time to spend on integrating this into UXArray, if I could have support for code review upon a PR submission. Having this functionality in UXArray would help us bring unstructured grid support into Parcels.

[philipc2]

Hi @fluidnumerics-joe

This would be a great addition! I am more than happy to help with any reviews or to answer any questions.

I'd like to point a couple related items if you want a reference to some recent work:

• @aaronzedwick is working on a Point in Face implementation in Point In Face #1056 which would return which face index a given point is contained within. Pinging him if he would like to explain the algorithm he used further
• We are able to compute the (min, max) bounds of each face, which is accessible through Grid.face_bounds_lon and Grid.face_bounds_lat

[fluidnumerics-joe]

Awesome. For reference, here's a notebook that walks through grid search and interpolation onto particle positions

https://github.com/ELPHE-WW/unstructured-mesh-parcels-sandbox/blob/main/notebooks/UXArray-FESOM2-ParticlePushing.ipynb

• We are able to compute the (min, max) bounds of each face, which is accessible through Grid.face_bounds_lon and Grid.face_bounds_lat

I did find those quite useful :)