Point-in-polygon for a large number of points

Question

I'm wondering what may be the most efficient way of determining whether a large number of points (O(1 million) are inside or outside a collection (O(10)) of polygons? The latter are not necessarily convex, but do not have holes in them. At the moment I prune the number of points by comparing their positions to the bounding boxes, then use this crossing-number method on the remaining points. But is there perhaps a faster method?

Answer 1

There is an efficient matplotlib function for that: matplotlib.nxutils.points_inside_poly(). The algorithm is documented on this page.