I need to speed up as much possible the lookup of which points fall into a generic polygon (over ~1000 vertices) for a country map (WGS84 lat/lon).
Is there any library (or examples) for CUDA? I could not find anything.
Are you dealing with just one polygon, or a set of polygons?
There is this relatively fast point in polygon test (with C code)
with an explanation of the algorithm here:
https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html
(oof, he really wrote the corresponding Fortran code 47 years ago - that’s in the
Jurassic Age of computing).
It is a sequential loop, but I think most it could be parallelized for parallel execution in CUDA (the final evaluation of the “c” variable would require a parallel reduction based on the XOR operator, assuming that the result of the if expression in the for loop has been evaluated in parallel on many CUDA threads. Alternatively simply counting how often the if clause returned true should work (using a plain atomic add). If the resulting sum is odd, return true as final result.
Also you could parallelize over multiple polygon tests that run simultaneously (assuming your territory consists of several polygons, e.g. continental US plus Hawaiian islands plus Alaska)
There may be some issues when using unprojected coordinates (WGS84 latitude and longitude) because a linear interpolation between lat/lon coordinates as done by the point in polygon test might will not necessarily produce straight lines when projected onto a plane (such a map projection into e.g. UTM coordinates).
Christian