Point-in-polygon for a large number of points

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, the开发者_Go百科n use this crossing-number method on the remaining points. But is there perhaps a faster method?

---

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

---

Assuming you have axis-aligned bounding boxes, you could sort the list of points by their x coordinate, find the places on the list points go inside or outside the bounding boxes by binary search and potentially discard a large number of points at once. Repeat for the y coordinate. Then continue as before with the remaining points. You could perform polygon triangulation to speed up the test within the bounding box.

Would perform best when area of the plane is much greater than the area of the polygons, and the polygons are reasonably compact (i.e. not long and thin, which may give you many false positives).

---

I'd probably use a Quadtree for fast rough test of "am I inside or outside of the polygon" to some level of precision that you determine when you generate the quadtree.

Each lookup is O(log n), which will be about as fast as you can get. For the points that lie within a cell of the quadtree that's marked as "contains an edge" then you'll have to do a traditional point-in-polygon test.