2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

This algorithm works very well to check if a single point is inside a single polygon, but will be suboptimal for other situations. In particular, if you have many points inside a given polygon, you may want to borrow ideas from polygon rasterization. Information on the web is kind of scattered, but there are several more or less complete slide sets from college courses, see e.g. this. You would want to use a sweep line algorithm, where you first sort your polygon vertices by e.g. y coordinate, and then scan them in order, updating a list of polygon vertices that cross the current y-coordinate. To check if a point with y coordinate y0 is inside the polygon, you would compute the intersection points of the active vertices at that y coordinate, sort them by x-coordinate, and check whether your point x coordinate falls in an inside or outside segment.

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.

So basically, it is highly dependent on the exact characteristics of your points and polygons, but the answer may very well be: yes, there are better methods out there.

$\endgroup$
  • $\begingroup$ Hi Jaime! Thanks for this nice answer. I thought it might help you to know that in particular, I have to check if a single point is inside a polygon. I have to check this repeatedly however. Is this what you meant by: "if you have many points inside a given polygon, you may want to borrow ideas from polygon rasterization?" $\endgroup$ – user89 Aug 23 '14 at 22:20
  • $\begingroup$ If your polygon and point are different every time, then I don't think you can do much better than what skimage provides. If the polygon is the same for several points, then there may be better options, perhaps what I described. $\endgroup$ – Jaime Aug 24 '14 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.