[FEA] Support GIS functions

[wmalpica]

[Edit: this issue was moved from cuDF]

I wish cudf would provide support for GIS type functions. I am not sure if GIS type functions belong in cudf, or if they belong in their own separate library, but it makes sense that at the very least they should be very compatible with the rest of the functionality provided by cudf.

I would like to see functions like:

• [x] point-in-polygon
• [ ] nearest points from a constant radius
• [ ] perimeter
• [ ] area
• [ ] convex hull
• [ ] bounding box
• [ ] and more

I think these sort of functions/features would address the needs of GIS data analytics and open up even more uses for cudf and rapidsai.

[thomcom]

What's the root library that we're adding these functions to? Create a new one like cuGeo?

[kkraus14]

Moving this issue to the new cuSpatial library at https://github.com/rapidsai/cuspatial

[wkelongws]

@williamBlazing In the newly released library "cuspatial" we have point-in-polygon and many other GIS functionality implemented and more will be coming in the future.

[github-actions[bot]]

This issue has been marked stale due to no recent activity in the past 30d. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be marked rotten if there is no activity in the next 60d.

[github-actions[bot]]

This issue has been marked rotten due to no recent activity in the past 90d. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed.

[InonS]

Anything happening here? If not, can anyone propose a different GPU-accelerated Convex Hull Python API?

[zhangjianting]

It is unclear whether you need Convex Hull code for 3D data or arbitrary dimensional data. It is also unclear the sizes of the problem that you are interested in GPU acceleration. If it is for 3D points, there are a few studies in the past 10 years or so (e.g., CudaHull or gHull). However, I am not sure whether the source code is available. Given the nature of the problem, I am not positive that you can expect significant speedups on GPUs for practical problem sizes.

[zhangjianting]

For additional features in your list, perimeter/area/bounding box are embarrassingly parallelizable on both CPUs and GPUs. Computing bounding boxes for polygons has been implemented at https://github.com/rapidsai/cuspatial/blob/branch-22.02/cpp/src/spatial/polygon_bounding_box.cu as part of quadtree-indexed point-in-polygon spatial join. The Python API is at https://github.com/rapidsai/cuspatial/blob/branch-22.02/python/cuspatial/cuspatial/core/gis.py. We do not have real use cases that require perimeter/area computation on GPUs as they are sufficiently fast on CPUs using open source packages for real world polygons with reasonable numbers of shapes and vertices. Please file a feature request if you have such real world use cases and we can prioritize it.

[zhangjianting]

It is unclear to me what you meant by "nearest points from a constant radius". If you need all points that fall within circles, it is again embarrassingly parallelizable and it should be sufficiently fast on CPUs when the numbers of points/circles is relatively small. Otherwise, quadtree index could be applied to speed it up. We can adapt quadtree-indexed point-in-polygon based spatial join for this purpose easily. Alternatively, one can use a polygon to approximate a circle and then use quadtree-indexed point-in-polygon spatial join which is ready-to-use (although unnecessary overheads are introduced).
Please do file a feature request if your applications use this function regularly and your point data sets are sufficiently large to benefit from GPU acceleration. As a side note, cuSpatial currently has point-to-polyline nearest neighbor query support which associate a point with a polyline ID that is closest to the point. Just thought it might be related. See https://github.com/rapidsai/cuspatial/blob/branch-22.02/cpp/src/join/quadtree_point_to_nearest_polyline.cu and https://github.com/rapidsai/cuspatial/blob/branch-22.02/python/cuspatial/cuspatial/core/spatial_join.py

[github-actions[bot]]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[github-actions[bot]]

This issue has been labeled inactive-90d due to no recent activity in the past 90 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed.