UXArray - Spatial Hashing Implementation

[fluidnumerics-joe]

Work on merging the work in UXArray to support spatial hashing. This is documented in the issue UXARRAY/uxarray#1126

Once implemented in UXArray, we can then sketch out how the spatial hashing will be implemented in Parcels v4 Field interpolator for uxarray.dataset's

[fluidnumerics-joe]

The UXArray team is currently working on bringing in a new method to determine if a point is inside a face ( See PR # UXARRAY/uxarray#1056 ). It will be beneficial for us to wait for this functionality to become available in uxarray and then contribute the hash search framework based on this method. Since UXArray supports more general unstructured element types, we would gain significantly more flexibility with this approach.

In Parcels, we would then look at specifically implementing the barycentric coordinate calculation once a particle has been found within a single element. I'll need to think a bit more on how this would fit within the Interpolator protocol we're thinking of.

[fluidnumerics-joe]

For an example on how we can modify the UXArray.Grid class, see this notebook in the sandbox repo.

For the moment, I'll push forward with doing a type extension of the uxarray.Grid, similar to what I've demo'd in the sandbox repo within parcels for the new proposed Field class (see #1850 ).

Once UXARRAY/uxarray#1056 is resolved, we'll push forward with adding the HashGrid in UXArray with the ultimate goal of supporting this search behavior as a uxarray.Grid method.

[fluidnumerics-joe]

Pushing ahead with this one on a fork of UXArray. The search method provided in UXARRAY/uxarray#1056 does not return optional barycentric coordinates, which we may want.

I've instead opted to put in local helper routines (in UXArray) that compute the barycentric coordinates for an arbitrary convex polygon with N>=3 vertices. This allows me to put together the query method (mimic'ing the KDTree and BallTree API) to perform our spatial hash search.

First draft has been pushed to a fork here: FluidNumerics/uxarray@89542c9

I'll start working on a notebook that uses this version of UXArray and modifications to Parcels FieldSet and Field classes (similar to main...v/mvp-dependency-discovery) to explore how this and the KDTree and BallTree search methods can each be used as part of the interpolation process.