遍历同心圆中的每个像素

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

从我的头顶掉下来......

\n

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

\n\n

\n

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

\n

\n

而不是制作逐渐变大的圆圈希望填满圆盘：

\n

\n

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

  \n
\n

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

  \n
\n

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

  \n

  from pprint import pprint\nfrom operator import itemgetter\nfrom itertools import groupby

  \n

  X = itemgetter(0)\nY = itemgetter(1)

  \n
\n

\n

此功能根据不同论坛中的问题修改

\n

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

\n

这应该最大限度地减少国家。当从圆圈创建光盘时，将会有一些重复/重新访问 - 我没有尝试量化这一点。

\n\n

结果...

\n

def display(points,radius):\n    \'\'\' point: sequence of (x,y) tuples, radius: int\n    \'\'\'\n    not_visited, visited = \'-\',\'\xe2\x96\x88\'\n    \n    # sort on y\n    points = sorted(points,key=Y)\n\n    nrows = ncols = radius * 2 + 1 + 2\n\n    empty_row = [not_visited for _ in range(ncols)]    # [\'-\',\'-\',...]\n   \n    # grid has an empty frame around the circle\n    grid = [empty_row[:] for _ in range(nrows)]   # list of lists\n    # iterate over visited points and substitute symbols\n    for (x,y) in points:\n        # add one for the empty row on top and colun on left\n        # add offset to address negative coordinates\n        y = y + radius + 1\n        x = x + radius + 1\n        grid[y][x] = visited\n\n    grid = \'\\n\'.join(\' \'.join(row) for row in grid)\n\n    print(grid)\n    return grid\n\nfor r in (3,8):\n    points = circle(r)  # generator/iterator\n    grid = display(points,r)\n

\n

- - - - - - - - -\n- - - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - - -\n- - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - -\n- \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 -\n- \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 -\n- \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 -\n- - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - -\n- - - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - - -\n- - - - - - - - -\n- - - - - - - - - - - - - - - - - - -\n- - - - - - - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - - - - - - -\n- - - - - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - - - - -\n- - - - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - - - -\n- - - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - - -\n- - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - -\n- - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - -\n- \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 -\n- \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 -\n- \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 -\n- \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 -\n- \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 -\n- - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - -\n- - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - -\n- - - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - - -\n- - - - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - - - -\n- - - - - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - - - - -\n- - - - - - - \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 \xe2\x96\x88 - - - - - - -\n- - - - - - - - - - - - - - - - - - -\n

\n