# Speedier alternative to “skimage.morphology._pnpoly import points_inside_poly”?

I am using scikit-image's points_inside_poly function, and in my code I am calling it enough times that it takes up about 50% of my running time (determined via profiling).

I now have two options before me: 1) reduce the number of calls I make to points_inside_poly and/or 2) find (or make?) a speedier version of points_inside_poly.

While I am exploring 1), a solution is not obvious to me at the moment so it will require more thought. In the mean time, I am wondering if there are any speeder alternatives for points_inside_poly?

What skimage's function does, is check whether a horizontal ray to the left of the point intersects each of the polygon sides. If the number of crossings is odd, it is inside, if it is even it is outside. skimage's implementation is also quite efficient: some time ago, as a learning exercise, I reimplemented skimage's points_inside_polygon as a numpy gufunc, see here, and I think it ran about 2x faster than skimage's implementation. Nothing to write home about.
The skimage algorithm, for $n$ points in a polygon with $m$ vertices, will be an $\mathcal{O}(mn)$ algorithm. The one I described right after would require sorting both the points and the vertices, so $\mathcal{O}(n\log n + m\log m)$, but after that you have work per point proportional to the number of sides crossing at that y-coordinate, which will be smaller than $m$ for most polygons.