[DISCUSSION]: A More User Friendly Quadtree Class

[isVoid]

Is this a new feature, an improvement, or a change to existing functionality?

Improvement

How would you describe the priority of this feature request

Low (would be nice)

Please provide a clear description of problem you would like to solve.

Today, cuspatial's support for quadtree is mainly encapsulated in these APIs:

• quadtree_on_points in indexing.py
• join_quadtree_and_bounding_boxes in join.py
• quadtree_point_in_polygon in join.py
• quadtree_point_to_nearest_linestring in join.py

These APIs mainly serves two use cases:

1. quadtree based point in polygon tests
2. quadtree based point to nearest linestring tests

In current release, to perform a PiP test, a user would do the following:

keys_to_points, quadtree = quadtree_on_points(points, **params)
bboxes = join_quadtree_and_bounding_boxes(quadtree, **params)
result = quadtree_point_in_polygon(bboxes, quadtree, keys_to_points, points, polygons)
real_point_indices = result.point_index.take(keys_to_points)

Further downstream dataframe opeartion could stem out from these spatial operations such as spatial join. For a GIS user, to achieve a spatial join with these operations today would require calling the above APIs in sequence, passing the result from one API to another, often needing to track the use of parameters. The burden of maintaining the consistency of the quadtree usage becomes a user burden, albeit it's unnecessary.

The result from the last API also requires further interpretation. For example, the return of quadtree_point_in_polygon require remapping the point_index column with the point_indices argument. Besides, the polygon index refers to parts index if the input is made of a multipolygon.

It would be helpful to use a custom class Point_Quadtree to hide some of the implementation detail to the user, as well as persisting the structure of point quadtrees across different set of polygon calls. Node rapids has made some effort on that end:
https://github.com/rapidsai/node/blob/7a330e31ebe1badc325c995c855cf3d375a1ea9d/modules/cuspatial/src/quadtree.ts#L65

With such introduction, I would imagine:

quadtree = Point_Quadtree(points, **params)  # Builds quadtree, caches points and parameters
point_indices = quadtree.point_in_polygon(polygons, **poi_params)  # Computes bounding boxes of PoI, performs PiP test, returns remapped point indices

Describe any alternatives you have considered

No response

Additional context

No response

[harrism]

I've had similar thoughts. Why limit this to Python? What about a more usable C++ API?

[isVoid]

I've had similar thoughts. Why limit this to Python? What about a more usable C++ API?

That's also a good idea. Just want to make sure the encapsulation doesn't hide the flexibility of the current quadtree functions. I'd like to request some comments from @trxcllnt since noderapids depends on C++ API.

[trxcllnt]

I considered having a quadtree class in C++, but decided against it due to differences in ownership semantics between C++ and Python/JS.

If we had an owning point_quadtree class in C++, we'd need a non-owning point_quadtree_view class, and Python/JS would have to build their own versions of the point_quadtree class on top of that.

That's just duplicating work, so unless we're trying to expose a nice C++ API for other C++ library consumers, I don't think it's strictly necessary to have a point_quadtree in C++.