按单元格与中心单元格的距离对单元格进行排序

Question

有人问我，当时看来是一个天真的问题：

我们如何根据与预定义/预先计算的中心单元的距离对 2D 数组中的单元进行排序。

下面的表格显示了特定单元格与预定义中心单元格的距离（它们的值为 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：

Answer 2

更短很容易：

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