遍历同心圆中的每个像素

Question

我正试图从(0，0(开始迭代每个像素坐标，以便在不重叠的最近偏移处融合两个像素化形状。

到目前为止，我一直在使用同心正方形，这确实很容易做到，但最终可能会将移植的图像放置得比实际更远。然后，我实现了Bresenham的圆算法，如下所示：

def generate_offsets(maxRadius : int):
"""Generate x and y coordinates in concentric circles around the origin
Uses Bresenham's Circle Drawing Algorithm
"""

for radius in range(maxRadius):
x = 0
y = radius
d = 3 - (2 * radius)
while x < y:

yield x, y
yield y, x
yield y, -x
yield x, -y
yield -x, -y
yield -y, -x
yield -y, x
yield -x, y

if d < 0:
d += (4 * x) + 6
else:
d += (4 * (x-y)) + 10
y -= 1

x += 1

然而，这样做的缺点是不检查某些像素偏移。我发现的所有填充孔洞的解决方案都建议从0,0到像素追踪整条线，这在这里是非常浪费的。

如何在不重新访问任何像素的情况下修复孔？

---

这是一个显示所述孔的示例，它表示每个圆或半径1-9。探索的像素为#，而未探索的像素则为.:

....................
....................
........#####.......
......#########.....
.....###########....
....#..#######..#...
...##..#.###.#..##..
...####.#####.####..
..####.#.###.#.####.
..#######.#.#######.
..########.########.
..#######.#.#######.
..####.#.###.#.####.
...####.#####.####..
...##..#.###.#..##..
....#..#######..#...
.....###########....
......#########.....
........#####.......
....................

---

更新：这是我目前的解决方案，它确实填满了整个圆圈，但存储的状态比我想要的多得多：

import itertools
def generate_offsets(minRadius : int = 0, maxRadius : int = 3_750_000):
"""Generate x and z coordinates in concentric circles around the origin
Uses Bresenham's Circle Drawing Algorithm
"""
def yield_points(x, y):

yield x, y
yield x, -y
yield -x, -y
yield -x, y

if x != y:
yield y, x
yield y, -x
yield -y, -x
yield -y, x

def yield_circle(radius, previousCircle):
x = 0
y = radius
d = 3 - (2 * radius)
while x < y:

for point in yield_points(x, y):
if point not in previousCircle:
yield point

if d < 0:
d += (4 * x) + 6
else:
d += (4 * (x-y)) + 10
for point in itertools.chain(yield_points(x + 1, y), yield_points(x, y - 1)):
if point not in previousCircle:
yield point
y -= 1

x += 1

previousCircle = [(0,0)]
for radius in range(minRadius, maxRadius):

circle = set()
for point in yield_circle(radius, previousCircle):
if point not in circle:
yield point
circle.add(point)

previousCircle = circle

这是迄今为止我在内存和处理方面找到的最平衡的解决方案。它只记得前一个圆圈，这将冗余率(访问两次的像素率(从没有任何内存的50%左右降低到1.5%左右

Answer 1

在我的脑海中

生成一次坐标集。探索时，保留一组访问过的坐标。集合之间的差异将是未访问的坐标。如果你不想处理圆圈之外的像素，也许可以跟踪x和y极值进行比较——也许像字典一样：{each_row_visited:max_and_min_col_for that row,}。

---

我更喜欢一个不会随着时间的推移而在内存中扩展的解决方案！

不是制作越来越大的圆圈来填充光盘：

• 使用Bresenham算法确定具有所需半径的点

• 找到每个x的最小和最大y值(反之亦然(

• 使用这些极值产生极值之间的所有点

  从pprint导入pprintfrom运算符import-itemgetter按从itertools导入组

  X=itemgetter(0(Y=itemgetter(1(

此函数根据不同论坛中的问题进行了修改

def circle(radius):
'''Yield (x,y) points of a disc

Uses Bresenham complete circle algorithm
'''
# init vars
switch = 3 - (2 * radius)
# points --> {x:(minY,maxY),...}
points = set()
x = 0
y = radius
# first quarter/octant starts clockwise at 12 o'clock
while x <= y:
# first quarter first octant
points.add((x,-y))
# first quarter 2nd octant
points.add((y,-x))
# second quarter 3rd octant
points.add((y,x))
# second quarter 4.octant
points.add((x,y))
# third quarter 5.octant
points.add((-x,y))
# third quarter 6.octant
points.add((-y,x))
# fourth quarter 7.octant
points.add((-y,-x))
# fourth quarter 8.octant
points.add((-x,-y))
if switch < 0:
switch = switch + (4 * x) + 6
else:
switch = switch + (4 * (x - y)) + 10
y = y - 1
x = x + 1
circle = sorted(points)
for x,points in groupby(circle,key=X):
points = list(points)
miny = Y(points[0])
maxy = Y(points[-1])
for y in range(miny,maxy+1):
yield (x,y)

这应该会使状态最小化。当从圆圈中创建光盘时，会有一些重复/重新访问——我没有试图量化这一点。

---

结果。。。

def display(points,radius):
''' point: sequence of (x,y) tuples, radius: int
'''
not_visited, visited = '-','█'

# sort on y
points = sorted(points,key=Y)
nrows = ncols = radius * 2 + 1 + 2
empty_row = [not_visited for _ in range(ncols)]    # ['-','-',...]

# grid has an empty frame around the circle
grid = [empty_row[:] for _ in range(nrows)]   # list of lists
# iterate over visited points and substitute symbols
for (x,y) in points:
# add one for the empty row on top and colun on left
# add offset to address negative coordinates
y = y + radius + 1
x = x + radius + 1
grid[y][x] = visited
grid = 'n'.join(' '.join(row) for row in grid)
print(grid)
return grid
for r in (3,8):
points = circle(r)  # generator/iterator
grid = display(points,r)

- - - - - - - - -
- - - █ █ █ - - -
- - █ █ █ █ █ - -
- █ █ █ █ █ █ █ -
- █ █ █ █ █ █ █ -
- █ █ █ █ █ █ █ -
- - █ █ █ █ █ - -
- - - █ █ █ - - -
- - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - █ █ █ █ █ - - - - - - -
- - - - - █ █ █ █ █ █ █ █ █ - - - - -
- - - - █ █ █ █ █ █ █ █ █ █ █ - - - -
- - - █ █ █ █ █ █ █ █ █ █ █ █ █ - - -
- - █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ - -
- - █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ - -
- █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ -
- █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ -
- █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ -
- █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ -
- █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ -
- - █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ - -
- - █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ - -
- - - █ █ █ █ █ █ █ █ █ █ █ █ █ - - -
- - - - █ █ █ █ █ █ █ █ █ █ █ - - - -
- - - - - █ █ █ █ █ █ █ █ █ - - - - -
- - - - - - - █ █ █ █ █ - - - - - - -
- - - - - - - - - - - - - - - - - - -