Suggestion: vtk/pyvista for spatial indexing

[Huite]

Just a suggestion: I spent a fair amount of time setting up the spatial index and querying in https://github.com/Deltares/numba_celltree for specific logic (overlaps, intersections, etc.).
VTK and pyvista might be a worthwhile alternative:

# Each cell begins with the number of points in the cell and then the points
# composing the cell
counts = (face_node_connectivity != FILL).sum(axis=1)
cells2d = np.column_stack((counts, grid.face_node_connectivity))

mesh = pv.UnstructuredGrid(
    cells2d[cells2d != -1],
    np.full(grid.n_face, CellType.TRIANGLE),
    np.column_stack((node_x, node_y, np.zeros(grid.n_node))),
)

indices = mesh.find_containing_cell(np.array([[150_000.0, 463_000.0, 0.0]]))

Essentially all the queries you'd like are available:

mesh.find_cells_within_bounds
mesh.find_cells_along_line
mesh.find_cells_within_bounds
mesh.find_closest_cell
mesh.find_closest_point
mesh.find_containing_cell

It might not solve everything since I'm not sure yet what VTK supports in terms of non-Cartesian coordinates, but this makes 3D topologies very straightforward to support as well!

[Huite]

Bit more digging: performance might be a concern.
pyvista accepts numpy arrays, but this mostly calls Python for loops to unvectorized vtk methods, which is a bit disappointing.

Ideally, you'd use compiled parallel for loops (like Cython or Numba prange).

I think pyvista also reinitialized the locator every query, but this can be avoided by using the vtk locator directly.

[philipc2]

Hi @Huite

Thanks for sharing this! This does seem very relevant to a lot of the work that we've been putting together.

Although, I am a little hesitant in how applicable this would be to our specific use case of spherical unstructured grids. We've been working with @hongyuchen1030 to implement many of the routines above directly on the unit sphere.

We achieve mesh.find_cells_within_bounds and mesh.find_cells_along_line by pre-computing a spherical bounding box for each of our faces and use that for our queries. There is some overhead in initially computing the bounding box, but we've drastically reduced it by using Numba.

The bounds are currently stored as an array, however I could imagine there are more efficient ways to organize the bounds that would reduce our query time (@hongyuchen1030 if I remember correctly, I think this is something you presented or showcased before

@aaronzedwick is currently working on a Point in Polygon implementation in #1056

We have an approximate version of mesh.find_closest_cell and mesh.find_closest_point that works well-enough built around a BallTree, though this is something we'd like to improve moving forward with a more robust implementation.

Ideally, you'd use compiled parallel for loops (like Cython or Numba prange).

This is what we've been leaning towards (Numba) for some time now, and it's been very successful.

I spent a fair amount of time setting up the spatial index and querying in https://github.com/Deltares/numba_celltree

I've glanced over this before and the implementation looks great. I could see this being useful, though my same concerns above regarding spherical geometry apply.

We could however possibly utilize these packages if we chose to project our grid to 2D using something like a sterographic projection, though that also introduces some new difficulties.

[Huite]

Ah I see, I had seen some methods for spherical geometries (the Gaussian quadrature methods, etc.), but hadn't realized the explicit focus so much.

I suppose you have come across this?
https://github.com/benbovy/spherely

This spatial index might also be relevant, if I understand correctly: https://github.com/benbovy/pys2index

In terms of inspiration, R has the simple features package which seems to enable both GEOS (Cartesian) and S2geometry (spherical). It's obviously much more akin to geopandas in terms of functionality and setup, but there's almost certainly interesting things in there, see: https://r-spatial.github.io/sf/articles/sf7.html

[hongyuchen1030]

Thanks a lot for the detailed information, @Huite! I spent the past week carefully researching the packages you mentioned.

Insights on numba_celltree

• The numba_celltree package includes a cell tree building algorithm that aligns well with our interests and could be highly useful.
• We are considering direct integration of numba_celltree into the Uxarray project to store our building bounds.
  @philipc2, we can explore this further once the zonal average is merged.
• Although the package is primarily designed for 2D surfaces, we believe we can adapt it to our needs with minimal effort.

Feedback on spherely and S2Geometry

• Regarding spherely and S2Geometry:
  • These libraries have excellent code structure designs that we can definitely learn from.
  • However, from an algorithmic standpoint, Uxarray adopts a more suitable approach for ensuring both accuracy and speed.
  • Given this, we likely won’t integrate S2Geometry-related products into Uxarray.

Thanks again for sharing these resources—it’s been invaluable for our ongoing work!

[Huite]

Hopefully goes without saying, but: Feel free to open issues or PRs on numba_celltree!

I personally intend to still extend numba celltree capabilities to Cartesian 3D. I'm curious to hear what your use case requires. It might be as simple as "oversizing" your bounding boxes such that they are fully contained in an axis-aligned bounding box (AABB)? Then the actual point-in-polygon test does the actual non-cartesian geometry handling.

[hongyuchen1030]

Hopefully goes without saying, but: Feel free to open issues or PRs on numba_celltree!

I personally intend to still extend numba celltree capabilities to Cartesian 3D. I'm curious to hear what your use case requires. It might be as simple as "oversizing" your bounding boxes such that they are fully contained in an axis-aligned bounding box (AABB)? Then the actual point-in-polygon test does the actual non-cartesian geometry handling.

We have our own algorithm to obtain our bounding boxes that bound the maximum and minimum longitude and latitude, and then we store this bounding information in the cell tree. So the cell tree will only store "two dimension" intervals for longitude and latitude separately.

This step is just from quickly retrieve the candidate faces. The point-in-polygon test will use the cartesian geometry handling on candidate faces