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)
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]