Python中的多邊形柵格化

Question

如何在python中柵格化多邊形？例如我有這個多邊形：

[（20，13），（21，12），（20，12），（19，12），（21，13）]

這是一個邊框，我需要找到其中的所有點（瓷磚）。我怎樣才能做到這一點與python沒有任何外部包？ 謝謝。

Answer 1

快速路：

def raster(poly): 
    for index in range(len(poly) - 1): 
     t1 = poly[index] 
     t2 = poly[index + 1] 
     xdef = t1[0] - t2[0] 
     ydef = t1[1] - t2[1] 
     if abs(xdef) > 1: 
      lo = min(t1[0], t2[0]) 
      hi = max(t1[0], t2[0]) 
      j = lo 
      while(j <= hi): 
       new = (j, t1[1]) 
       poly.append(new) 
       j += 1 
     if abs(ydef) > 1: 
      lo = min(t1[1], t2[1]) 
      hi = max(t1[1], t2[1]) 
      j = lo 
      while(j <= hi): 
       new = (t1[0], j) 
       poly.append(new) 
       j += 1 
    return poly