訂購細胞由中心細胞（S）

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的距離：

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