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.
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