Python在網格上繪製填充的「圓」

Question

您可以提供一種在任意位置和半徑的網格中繪製圓形（ish）形狀的高效算法嗎？

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . o O o . . . . . . . . . . . . . . . . . . . . 
. . . . O O O O O . . . . . . . . . . . . . . . . . . . 
. . . o O O O O O o . . . . . . . . . . . . . . . . . . 
. . . O O O O O O O . . . . . . . . . . o O o . . . . . 
. . . o O O O O O o . . . . . . . . . o O O O o . . . . 
. . . . O O O O O . . . . . . . . . . O O O O O . . . . 
. . . . . o O o . . . . . . . . . . . o O O O o . . . . 
. . . . . . . . . . . . . . . . . . . . o O o . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 

我用這個進行尋路。它是更精細解析的圖形領域的較低分辨率抽象。這些形狀可以作爲避免的塊。

請記住，我希望能夠使用它來快速索引塊所在的二維數組。

score = self.map[x][y] 

所以， 「畫出」 圈子將是類似的設定值可以阻止：

self.map[x][y] = PATH_COST_PROX1 

繪製現場看起來是這樣的：

def printme(self): 
    """ Print the map to stdout in ASCII.""" 
    for y in reversed(range(self.ymax)): 
     for x in range(self.xmax): 
      if self.map[x][y] >= PATH_COST_PROX0: 
       print 'O', 
      elif self.map[x][y] >= PATH_COST_PROX1: 
       print 'o', 
      else: 
       print '.', 
     print '' 

編輯：這是我原來的（可恥的）企圖。我在網格上手工製作了圓圈，並且只記錄了每次增加半徑後添加的點數。這不是一個可怕的想法，但接受的答案更加優雅。

COVER_MAP = [ 
    [(0,0)], 
    [(0,1),(1,0),(0,-1),(-1,0)], 
    [(1,1),(1,-1),(-1,-1),(-1,1)], 
    [(0,2),(2,0),(0,-2),(-2,0)], 
    [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)], 
    [(0,3),(2,2),(3,0),(2,-2),(0,-3),(-2,-2),(-3,0),(-2,2)], 
    [(1,3),(3,1),(3,-1),(1,-3),(-1,-3),(-3,-1),(-3,1),(-1,3)] 
] 

def set_blocked(self, p, radius): 
    """ 
    Set the blocked state of a coordinate. Takes an integer value that 
    represents the cost of the block 
    """ 
    #radius = radius * 2 
    if radius > len(COVER_MAP)-1: 
     radius=len(COVER_MAP)-1 
    #print "point:",p," radius:",radius 
    (cx,cy) = p 
    for i in range(len(COVER_MAP)): 
     for j in range(len(COVER_MAP[i])): 
      (rx,ry) = COVER_MAP[i][j] 
      x = cx + rx 
      y = cy + ry 
      if x >= 0 and x < self.xmax and y >= 0 and y < self.ymax: 
       if i < radius: 
        self.map[x][y] = PATH_COST_PROX0 
       elif i == radius: 
        self.map[x][y] = PATH_COST_PROX1 
       elif i == radius + 1: 
        self.map[x][y] = PATH_COST_PROX2 
       elif i == radius + 2: 
        self.map[x][y] = PATH_COST_PROX3 
       elif i == radius + 3: 
        self.map[x][y] = PATH_COST_PROX4 

煤礦確實有能夠使周圍原來的圈子，這東西的記憶算法下面沒有，但可以適用於提供減少成本的模糊環的優勢。

Answer 1

我懷疑這樣做的最快方法使用memoization（不要與「記憶」相混淆）。以下是生成半徑爲20像素的光盤的示例。如果您想要圓形或中空圓盤而不是填充光盤，則需要爲它們指定寬度，並在if語句中包含x_sq + y_sq >= (k_r_sq - width)。根據time.time（）（如果你有python 3.3或更高版本，你可以使用time.perf_counter（）），這需要我3微秒來加載每個光盤的座標集，但是這並不考慮任何您可能想要在該光盤上進行計算。

希望這會有所幫助。

import time 
max_radius = 20  

i0 = time.time() 
class DiscTemplate: 
    def __init__(self, max_r): 
     self.memos = [] 
     for k_r in range(1, max_r + 1): 
      k_r_sq = k_r ** 2 
      self.memos.append([]) 
      for x in range(-max_r, max_r + 1): 
       x_sq = x ** 2 
       for y in range(-max_r, max_r + 1): 
        y_sq = y ** 2 
        if x_sq + y_sq <= k_r_sq: 
         self.memos[k_r - 1].append((x,y)) 

     self.max_r = max_r 

    def get_disc(self, r): 
     return self.memos[r - 1] 
test = DiscTemplate(20) 
i1 = time.time() 

print("time to make class:", i1 - i0) 

t0 = time.time() 
disc = test.get_disc(2) 
t1 = time.time() 

print("time to produce disc:", t1 - t0) 
print("Disc coordinates: \n", disc) 

Answer 2

我會嘗試這樣的事：

1. 查找要繪製圓的外接矩形：

   top_left = (cx + radius*cos(3*pi/4), cy + radius*sin(3*pi/4)) # (cx, cy) center of the circle 
   width, height = 2*radius, 2*radius 
   

2. 對於這個矩形的每一個點測試距離中心並設置相應的字符，如果該距離小於半徑

編輯：numpy

以下代碼將爲您提供圓圈中的點。在這裏你沒有Python中的任何循環，所以效率將是最大的。

import numpy as np 

#precomputed (depends on the dimensions of your grid) 
x = np.arange(50) # x values 
y = np.arange(50) # y values 
xx, yy = np.meshgrid(x, y) # combine both vectors 

# for this particular circle 
cx, cy, r = 10, 10, 5 

condition = (xx-cx)**2 + (yy-cy)**2 <= r**2 
points = xx[condition] + 1j*yy[condition] # list of points in the circle (stored as complex)