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)