Asked By – Ruben Perez-Carrasco
I found two main methods to look if a point belongs inside a polygon. One is using the ray tracing method used here, which is the most recommended answer, the other is using matplotlib
path.contains_points (which seems a bit obscure to me). I will have to check lots of points continuously. Does anybody know if any of these two is more recommendable than the other or if there are even better third options?
I checked the two methods and matplotlib looks much faster.
from time import time import numpy as np import matplotlib.path as mpltPath # regular polygon for testing lenpoly = 100 polygon = [[np.sin(x)+0.5,np.cos(x)+0.5] for x in np.linspace(0,2*np.pi,lenpoly)[:-1]] # random points set of points to test N = 10000 points = np.random.rand(N,2) # Ray tracing def ray_tracing_method(x,y,poly): n = len(poly) inside = False p1x,p1y = poly for i in range(n+1): p2x,p2y = poly[i % n] if y > min(p1y,p2y): if y <= max(p1y,p2y): if x <= max(p1x,p2x): if p1y != p2y: xints = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x if p1x == p2x or x <= xints: inside = not inside p1x,p1y = p2x,p2y return inside start_time = time() inside1 = [ray_tracing_method(point, point, polygon) for point in points] print("Ray Tracing Elapsed time: " + str(time()-start_time)) # Matplotlib mplPath start_time = time() path = mpltPath.Path(polygon) inside2 = path.contains_points(points) print("Matplotlib contains_points Elapsed time: " + str(time()-start_time))
Ray Tracing Elapsed time: 0.441395998001 Matplotlib contains_points Elapsed time: 0.00994491577148
Same relative difference was obtained one using a triangle instead of the 100 sides polygon. I will also check shapely since it looks a package just devoted to these kind of problems
Now we will see solution for issue: What’s the fastest way of checking if a point is inside a polygon in python
You can consider shapely:
from shapely.geometry import Point from shapely.geometry.polygon import Polygon point = Point(0.5, 0.5) polygon = Polygon([(0, 0), (0, 1), (1, 1), (1, 0)]) print(polygon.contains(point))
From the methods you’ve mentioned I’ve only used the second,
path.contains_points, and it works fine. In any case depending on the precision you need for your test I would suggest creating a numpy bool grid with all nodes inside the polygon to be True (False if not). If you are going to make a test for a lot of points this might be faster (although notice this relies you are making a test within a “pixel” tolerance):
from matplotlib import path import matplotlib.pyplot as plt import numpy as np first = -3 size = (3-first)/100 xv,yv = np.meshgrid(np.linspace(-3,3,100),np.linspace(-3,3,100)) p = path.Path([(0,0), (0, 1), (1, 1), (1, 0)]) # square with legs length 1 and bottom left corner at the origin flags = p.contains_points(np.hstack((xv.flatten()[:,np.newaxis],yv.flatten()[:,np.newaxis]))) grid = np.zeros((101,101),dtype='bool') grid[((xv.flatten()-first)/size).astype('int'),((yv.flatten()-first)/size).astype('int')] = flags xi,yi = np.random.randint(-300,300,100)/100,np.random.randint(-300,300,100)/100 vflag = grid[((xi-first)/size).astype('int'),((yi-first)/size).astype('int')] plt.imshow(grid.T,origin='lower',interpolation='nearest',cmap='binary') plt.scatter(((xi-first)/size).astype('int'),((yi-first)/size).astype('int'),c=vflag,cmap='Greens',s=90) plt.show()
, the results is this:
This question is answered By – armatita
This answer is collected from stackoverflow and reviewed by FixPython community admins, is licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0