Slicing through a grid in a spiral motion, returning xMin, xMax, yMin, yMax for each slice

Question

My current Python code (below) slices up an image into n slices, and returns each slice's coordinates on a per row/column order.

Rather than start at xMin/yMin 1/1 and complete one row at a time, I wish to start in the middle of the image and spiral myself out, eventually completing all slices. How can this be achieved?

import math


slices = 11
imageWidth = 1024
imageHeight = 576
totalPixels = imageWidth * imageHeight
print 'Slices: ' + str(slices)

# Re-calculate slices
slices = int(slices/2)*2
print 'Re-calculated slices: ' + str(slices)
print 'Total pixels in image: ' + str(totalPixels)
print 'Maximum slices allowed: ' + str(totalPixels/4)

factor = math.sqrt( slices )
print 'Factor: ' + str(factor)

if (slices > totalPixels/4):
    print 'You cannot use more than ' + int(totalPixels/4) + ' slices!'
else:

    regionWidth = int(math.ceil(imageWidth / factor))
    regionHeight = int(math.ceil(imageHeight / factor))
    print 'Region size: ' + str(int(regionWidth)) + 'x' + str(int(regionHeight))
    print 'Region width: '  + str(regionWidth)
    print 'Region height: ' + str(regionHeight)

    imageWidthRounded = int( math.ceil(factor) * math.ceil( imageWidth / factor ) )
    restWidth = imageWidthRounded - imageWidth
    imageHeightRounded = int( math.ceil(factor) * math.ceil( imageHeight / factor ) )
    restHeight = imageHeightRounded - imageHeight
    print 'Rest width: ' + str(restWidth)
    print 'Rest height: ' + str(restHeight)

    factorRounded = int(math.ceil(factor))
    print 'Factor rounded: ' + str(factorRounded)


    xMin = 0
    xMax = 0
    yMin = 0
    yMax = 0


    rows = factorRounded
    columns = factorRounded
    print 'Total rows: ' + str(rows)
    print 'Total columns: ' + str(columns)


    for column in range(1, columns+1):
        xMin = 0
        xMax = 0
        if column == columns:
            print 'Col '+ str(column) + ' (last column) '
            yMin = (column*regionHeight + 1) - regionHeight
            yMax += (regionHeight - restHeight)

        else:
            print 'Col '+ str(column)
            yMin = (column*regionHeight + 1) - regionHeight
            yMax += regionHeight


        for row in range(1, rows+1):
            if row == rows:
                xMin = (row*regionWidth + 1) - regionWidth
                xMax += (regionWidth-restWidth)

                print 'Row ' + str(row) + ':  xMin=' +str(xMin) + '\t xMax=' + str(xMax) + '\t yMin=' + str(yMin) + '\t yMax=' + str(yMax) + ' (last row)'
            else:
                xMin = (row*regionWidth + 1) - regionWidth
                xMax += regionWidth

                print 'Row ' + str(row) + ':  xMin=' +str(xMin) + '\t xMax=' + str(xMax) + '\t yMin=' + str(yMin) + '\t yMax=' + str(yMax)

Answer 1

To start off with try enumerating some cases:

Case 1:

o

Return center value.

Case 2:

o o
o o

Return values in clockwise order from top left.

Case 3:

o o o
o o o
o o o

Return center, then return values in clockwise order from top left.

...

In general, we see that if the dimension of the grid is odd we need to return the center value first. After this we can keep track of the bounding corners for our current slice and expand these corners to the next level iteratively to process all slices. We can determine the total numbers of slices (and thus iterations) by the dimension of the grid.

Here's the function, implemented as a generator:

def spiral(m):
    length = len(m[0])
    last = length - 1
    mid = length // 2
    spirals_remaining = mid

    if length % 2 == 1:
        yield m[mid][mid]
        box = [(mid-1, mid-1), (mid-1, mid+1), (mid+1, mid+1), (mid+1, mid-1)]
    else:
        box = [(mid-1, mid-1), (mid-1, mid), (mid, mid), (mid, mid-1)]

    while spirals_remaining > 0:
        # yield spiral values clockwise from top left corner
        top = m[box[0][0]][slice(box[0][1], box[1][1])]
        for x in top:
            yield x
        right = [m[i][box[1][1]] for i in range(box[1][0], box[2][0])]
        for x in right:
            yield x
        bottom = m[box[2][0]][slice(box[2][1], box[3][1], -1)]
        for x in bottom:
            yield x
        left = [m[i][box[3][1]] for i in range(box[3][0], box[0][0], -1)]
        for x in left:
            yield x

        # update bounding box for next spiral
        box[0] = box[0][0] - 1, box[0][1] - 1
        box[1] = box[1][0] - 1, box[1][1] + 1
        box[2] = box[2][0] + 1, box[2][1] + 1
        box[3] = box[3][0] + 1, box[3][1] - 1
        spirals_remaining -= 1

Example output:

>>> m = [[1, 2, 3, 4], 
...      [5, 6, 7, 8], 
...      [9, 10, 11, 12], 
...      [13, 14, 15, 16]]
>>> list(spiral(m))
[6, 7, 11, 10, 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5]