How to get list of points inside a polygon in python?

Question

I searched a lot and cant find any practical answer to my question. I have a polygon. For example:

    [(86, 52), (85, 52), (81, 53), (80, 52), (79, 48), (81, 49), (86, 53),      (85, 51), (82, 54), (84, 54), (83, 49), (81, 52), (80, 50), (81, 48),      (85, 50), (86, 54), (85, 54), (80, 48), (79, 50), (85, 49), (80, 51),      (85, 53), (82, 49), (83, 54), (82, 53), (84, 49), (79, 49)] 

I want to get a list of all the points inside this border polygon. I heard alot about polygon triangulation techniques or linear/flood/intersection/... filling algorithms. but i cant really come up with an efficient way of implementing this. This poly is small, imagine a polygon with 1 billion points. I am now using PIL draw polygon to fill the poly with red color and loop inside it to find red points. This is a horribly slow technique:

def render(poly, z):     xs = [i[0] for i in poly]     ys = [i[1] for i in poly]     minx, maxx = min(xs), max(xs)     miny, maxy = min(ys), max(ys)     X = maxx - minx + 1     Y = maxy - miny + 1     newPoly = [(x - minx, y - miny) for (x, y) in polygons]     i = Image.new("RGB", (X, Y))     draw = ImageDraw.Draw(i)     draw.polygon(newPoly, fill="red")     # i.show()     tiles = list()     w, h = i.size     print w, h     for x in range(w):         for y in range(h):             data = i.getpixel((x, y))             if data != (0, 0, 0):                 tiles.append((x + minx, y + miny))      return tiles 

I am searching for a Pythonic way of solving this problem. Thank you all.

Answer 1

I suggest to use matplotlib contains_points()

from matplotlib.path import Path  tupVerts=[(86, 52), (85, 52), (81, 53), (80, 52), (79, 48), (81, 49), (86, 53),  (85, 51), (82, 54), (84, 54), (83, 49), (81, 52), (80, 50), (81, 48),  (85, 50), (86, 54), (85, 54), (80, 48), (79, 50), (85, 49), (80, 51),  (85, 53), (82, 49), (83, 54), (82, 53), (84, 49), (79, 49)]   x, y = np.meshgrid(np.arange(300), np.arange(300)) # make a canvas with coordinates x, y = x.flatten(), y.flatten() points = np.vstack((x,y)).T   p = Path(tupVerts) # make a polygon grid = p.contains_points(points) mask = grid.reshape(300,300) # now you have a mask with points inside a polygon