Iterating through every pixel in concentric circles

Question

I am trying to iterate through every pixel coordinate, starting at (0, 0), in order to fuse two pixelated shapes at the closest offset where they don't overlap.

Until now, I was using concentric squares, which are really easy to do but can end up placing the grafted image further than it could be. I then implemented Bresenham's Circle Algorithm as follows :

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

However, this has the disadvantage of leaving some pixel offsets unchecked. All the solutions I have found for filling the holes propose tracing the entire line from 0,0 to the pixel, which would be extremely wasteful here.

How can I fix the holes, without revisiting any pixels ?

---

Here is an example showing said holes, this represents every circle or radius 1-9. Explored pixels are #, while unexplored pixels are . :

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

---

Update : Here is my current solution, which does fill the whole circle but is stores a lot more state than I would like :

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

This is the most balanced solution I have found so far in terms of memory and processing. It only remembers the previous circle, which lowers the redundancy rate (rate of pixels visited twice) from around 50% without any memory to around 1.5%

Shedd

Can you upload two images as a before & after expectation? Thanks. – Vladi

If there is no O(1) memory way with decent time-complexity to do this without revisiting or missing pixels, would you rather revisit some pixels, or miss some pixels? – Trapper

What happens, if you play with the radius generation step size? I mean above using int radius, use a float, and do the check for half steps. It will not solve the redundacy, but keeps the algorithm simple. What do you think? – Corroboree

With radius=8 your second solution still has some holes. Is the solution intended to be generic and work for any radius or is there a practical minimum radius that it it will be used with? Will minRadius ever be non-zero? – Tuberculate

Are you confident you implemented the algorithm correctly? – Tuberculate

@WillDaSilva Sorry for the long wait. I would rather revisit pixels than miss any – Shedd

@Tuberculate I have checked and it does seem my implementation of Bresenham's is correct. That is not the issue, Bresenham's was never intended to be space-filling, so it unsurprisingly isn't. – Shedd

Answer 1

Off the top of my head.....

Generate a set of coordinates once. While exploring, keep a set of coordinates visited. The difference between the sets will be the un-visited coordinates. Maybe keep track of the x and y extrema for comparison if you don't want to process pixels outside of the circle - maybe something like a dictionary: {each_row_visited:max_and_min_col_for that row,}.

---

I would prefer a solution that doesn't expand in memory as time progresses !

Instead of making progressively larger circles hoping to fill a disc:

• Use the Bresenham algorithm to determine the points with your desired radius

• find the min and max y value for each x (or vis versa)

• use those extrema to yield all points between the extrema

  from pprint import pprint from operator import itemgetter from itertools import groupby

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

This function modified from question in a different forum

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)

That should minimize the state. There is going to be some duplication/revisits when creating the disc from the circle - I didn't try to quantify that.

---

Result...

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)

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

Tuberculate

While this could probably work, I would prefer a solution that doesn't expand in memory as time progresses ! – Shedd