I have a SHP file that contains all counties in the USA. I also have roughly 100 million GPS locations. I need to tally the number of GPS locations per county.
A linear search through the counties for each coordinate is obviously a bad idea. I'm guessing I need some sort of spatial data structure that will prune candidate counties drastically and was hoping this was a common enough query that canned solutions were already available. In other words, I pass in SHP records for the counties and then query the resultant data structure for some unique identifier (FIPS code) of the county from a GPS coordinate (represented as some Point object).
My toolset is Python, shapely, fiona, etc.