title: How to get list of points inside a polygon in python?
body: <p>I searched a lot and cant find any practical answer to my question. I have a polygon. For example:</p>
  
  <pre><code>    [(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)]
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>I am searching for a Pythonic way of solving this problem.
  Thank you all.</p>