Упорядочение ячеек по их расстоянию от центральной ячейки

Question

Мне кто-то спросил меня, что в то время казалось достаточно невинным вопросом:

Как упорядочить ячейки в двумерном массиве по их расстоянию от предварительно определенных / предварительно вычисленных центральных ячеек.

Вот таблица, показывающая, как далеко конкретная ячейка находится от предопределенных центральных ячеек (в них есть значения 0).Значение n означает, что это n ячеек от центра:

+----+----+----+----+----+----+----+----+
| 4  | 4  | 3  | 3  | 3  | 3  | 4  | 4  |
+----+----+----+----+----+----+----+----+
| 4  | 3  | 2  | 2  | 2  | 2  | 3  | 4  |
+----+----+----+----+----+----+----+----+
| 3  | 2  | 1  | 1  | 1  | 1  | 2  | 3  |
+----+----+----+----+----+----+----+----+
| 3  | 2  | 1  | 0  | 0  | 1  | 2  | 3  |
+----+----+----+----+----+----+----+----+
| 3  | 2  | 1  | 0  | 0  | 1  | 2  | 3  |
+----+----+----+----+----+----+----+----+
| 3  | 2  | 1  | 1  | 1  | 1  | 2  | 3  |
+----+----+----+----+----+----+----+----+
| 4  | 3  | 2  | 2  | 2  | 2  | 3  | 4  |
+----+----+----+----+----+----+----+----+
| 4  | 4  | 3  | 3  | 3  | 3  | 4  | 4  |
+----+----+----+----+----+----+----+----+

Я решил проблему путем вычисления расстояния по прямой линии между (x1, y1) и (x2, y2) в евклидовом пространстве и сортировкиони использовали метод старой школы «Украсить-Сортировать-Украсить».

Вот чем я закончил:

import math
boardMaxRow = 8
boardMaxCol = 8
thatAbsurdLargeValue = ( 1 + boardMaxRow + boardMaxCol )
centerCells = ( ( 3, 3 ), ( 3, 4 ), ( 4, 3 ), ( 4, 4 ) )
cellsOrderedFromTheCenter = {}

for row in xrange( boardMaxRow ):
    for col in xrange( boardMaxCol ):
        minDistanceFromCenter = thatAbsurdLargeValue
        for ( centerX, centerY ) in centerCells:
            # straight line distance between ( x1, y1 ) and ( x2, y2 ) in an Euclidean space
            distanceFromCenter = int( 0.5 + math.sqrt( ( row - centerX ) ** 2 + ( col - centerY ) ** 2 ) )
            minDistanceFromCenter = min( minDistanceFromCenter, distanceFromCenter )
        cellsOrderedFromTheCenter[ ( row, col ) ] = minDistanceFromCenter

board = [ keyValue for keyValue in cellsOrderedFromTheCenter.items() ]

import operator

# sort the board in ascending order of distance from the center
board.sort( key = operator.itemgetter( 1 ) )
boardWithCellsOrderedFromTheCenter = [ key for ( key , Value ) in board ]
print boardWithCellsOrderedFromTheCenter

Вывод:

[(3, 3), (4, 4), (4, 3), (3, 4), (5, 4), (2, 5), (2, 2), (5, 3), (3, 2), (4, 5), (5, 5), (2, 3), (4, 2), (3, 5), (5, 2), (2, 4), (1, 3), (6, 4), (5, 6), (2, 6), (5, 1), (1, 2), (6, 3), (1, 5), (3, 6), (4, 1), (1, 4), (2, 1), (6, 5), (4, 6), (3, 1), (6, 2), (7, 3), (4, 7), (3, 0), (1, 6), (3, 7), (0, 3), (7, 2), (4, 0), (2, 0), (5, 7), (1, 1), (2, 7), (6, 6), (5, 0), (0, 4), (7, 5), (6, 1), (0, 2), (7, 4), (0, 5), (0, 7), (6, 7), (7, 6), (7, 7), (0, 0), (7, 1), (6, 0), (1, 0), (0, 1), (7, 0), (0, 6), (1, 7)]

IЯ поражен тем, сколько кода я получил там для такой тривиальной проблемы.

Мой вопрос: могу ли я сделать это быстрее и / или короче (используйте меньше временных / функциональных вызовов)?

Answer 1

Короче легко:

coordinates = [(x,y) for y in range(boardMaxRow) 
                     for x in range(boardMaxCol)]

def dist(A,B):
    a,b = A
    c,d = B
    # real euklidian distance without rounding
    return (a-c)**2+(b-d)**2 

print list(sorted(coordinates, 
    key=lambda x: min(dist(x,c) for c in centerCells)))

Answer 2

Чтобы сделать его короче (и использовать немного другую метрику):

>>> rows, cols, centerx, centery = 6, 6, 2.5, 2.5
>>> [p[1:] for p in sorted((((x - centerx) ** 2 + (y - centery) ** 2, x, y)
...                         for x in xrange(rows) for y in xrange(cols)))]
[(2, 2), (2, 3), (3, 2), (3, 3), (1, 2), (1, 3), 
 (2, 1), (2, 4), (3, 1), (3, 4), (4, 2), (4, 3), 
 (1, 1), (1, 4), (4, 1), (4, 4), (0, 2), (0, 3),
 (2, 0), (2, 5), (3, 0), (3, 5), (5, 2), (5, 3), 
 (0, 1), (0, 4), (1, 0), (1, 5), (4, 0), (4, 5),
 (5, 1), (5, 4), (0, 0), (0, 5), (5, 0), (5, 5)]

Чтобы сделать это быстрее:

• Не берите квадратные корни (как в моем коде выше): сортировка по квадрату расстояния так же хороша, как и сортировка по расстоянию, а брать квадратные корни относительно медленно не нужно.
• Использование 8-позиционной симметрии: отсортируйте один октант и скопируйте его 8 раз.

---

В комментариях PoorLuzer спрашивает: «Я также не понял, почему вы инициализируете centerx, centery = 2.5, 2.5». Я надеюсь, что эта цифра проясняет:

PoorLuzer также задается вопросом, почему наши метрики отличаются, учитывая, что мы оба используем евклидову формулу расстояния. Ну, моя метрика принимает расстояние от центра каждого квадрата до центра всей сетки. Например, для этих 8 ячеек расстояние от центра составляет √2,5 = около 1,58:

Принимая во внимание, что PoorLuzer берет евклидово расстояние до ближайшего из четырех центральных квадратов (и округляет его до целого числа). Для тех же 8 ячеек PoorLuzer назначает расстояние 1: