python - 按与中心单元格的距离对单元格排序

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

对于如此琐碎的问题，我对在那里输入了多少代码感到惊讶。

我的问题是：我可以使其更快或更短（使用更少的临时函数/函数调用）吗？

Answer 1

使其更短（并使用略有不同的指标）：

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