Point in Polygon quadtree version

[Schubert-Tom]

Hi there,

I am working on a project where I want to do efficient point in polygon checks. I have one big polygon which I slice down in multiple small polygons at the beginning of my program.

After that the set of polygons stays constant but I get new random set of points all the time and have to check as fast as possible which of those points are within which polygon of the set.

For starting I just used the normal point_in_polygon function. I saw that there is some spatial indexing with quadtrees available but as of my understanding the quadtree is build for a set of points in a bounding box. After that this quadtree can be used with the quadtree version of the point in polygons function to check the position of those points relative to some polygons.

I was wondering if there is a possibility to build spatial indexing for the set auf polygons which stays constant and therefore speed up the inside polygonscheck by simply keeping the indexed tree of the Polygons in gpu memory?

Is there support for such a use case?
Can somebody recommend an approach for such a problem?

Thanks a lot in advance!

P.S
Each polygon (10 in total have ~70 points and the set of random points has around 250 points

[trxcllnt]

Hi @Schubert-Tom,

At the moment, cuSpatial only includes the point quadtree. However, this operation is quite fast, so I wouldn't expect this to be a bottleneck for your use-case. @zhangjianting's paper states an indexing rate of ~850M points/second on an RTX 2080 TI, and that should be the lower-bound when using cuSpatial with RMM and on newer hardware.

I suggest pre-computing the polygon bounding boxes once (with polygon_bounding_boxes), then run quadtree_on_points, join_quadtree_and_bounding_boxes, and quadtree_point_in_polygon for each new set of points. You can see the relative cost of each of these routines in my comment here. Of the three, the final point_in_polygon call should dominate the total run time, not the tree build.

That said, your inputs are quite small for GPUs/cuSpatial. There is a constant non-zero overhead (a few ms) to calling GPU functions, and I suspect that's going to take the most time. This cost is negligible compared to running the equivalent CPU operation on big data, but it is noticeable on small data.

Feel free to keep using cuSpatial if that's in your performance budget (or you expect to have larger input sizes later), but if not, it may be worth looking into the geopandas or gdal point-in-polygon routines.

Cheers!

edit: Jianting shared an expermental RTree implementation (my fork here) that I think is what you were asking about. IIRC we opted against including it, as it would require more research and work to make it production-ready. Though if you're comfortable with C++ and CUDA, feel free to dive in!

[pwrliang]

Hi @Schubert-Tom , for such a small set of polygons, I wouldn't recommend using the GPU, as the CPU-GPU communication overhead might outweigh the benefits. However, if you're interested, we have a new research project called LibRTS, which accelerates PIP queries using RT cores. Instead of indexing the points, LibRTS builds an index over the bounding boxes of the polygons, making it extremely efficient when dealing with a large number of points and polygons.

Here are some relevant links:

• Spatial index using RT cores: GitHub Repository
• Demo of PIP query acceleration: Demo Code
• Paper: Publication

Let me know if you have any questions!