Нарезка сетки по спиральному движению, возвращение xMin, xMax, yMin, yMax для каждого фрагмента

Question

Мой текущий код Python (ниже) разрезает изображение на n фрагментов и возвращает каждую координату среза в строке/порядок столбцов.

Вместо того, чтобы начинать с xMin/yMin 1/1 и заканчивать одну строку за раз, я хочу начать посередине изображения и выкручивать себя, в итоге заканчивая все фрагменты. Как это можно достичь?

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

Чтобы начать с попытки перечислить некоторые случаи:

Случай 1: значение

o 

Return центр.

Случай 2:

o o 
o o 

Возвращаемые значения по часовой стрелке от верхнего левого.

Случай 3:

o o o 
o o o 
o o o 

Return центр, а затем возвращать значения по часовой стрелке от верхнего левого.

...

В целом, мы видим, что если размерность сетки нечетные мы должны вернуть центральное значение первым. После этого мы можем отслеживать ограничивающие углы для нашего текущего фрагмента и расширять эти углы до следующего уровня итеративно для обработки всех фрагментов. Мы можем определить общее количество срезов (и, следовательно, итераций) по размерности сетки.

Вот функция, реализованная в виде 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 

Пример вывода:

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