행렬의 등거리 점

질문을 다시 표현하면 중심까지의 유클리드 거리를 늘려 점을 열거하려고합니다.

다음은 https://math.stackexchange.com 에서이 문제 에 대한 두 가지 답변입니다. how-to-enumerate-2d-integer-coordinates-order-by-euclidean-distance 및 algorithm-for-enumerating-grid-points-by-distance -주어진 지점에서

원래:

• 대칭을 사용하여 점만 고려하십시오 0 <= x <= y.
• 주어진 x포인트에 대해 증가함에 따라 열거됩니다 y.
• 우선 순위 대기열을 사용하여 각 수직선에 대한 다음 후보를 유지합니다.

으로 n당신이 생성 마지막 인덱스, 시간 복잡도가 될 것입니다 O(n log n)및 공간의 복잡성 O(sqrt(n)).

주의 : 부동 소수점 계산을 피하려면 점의 순서를 변경하지 않는 제곱 거리를 고려하십시오.

이 아이디어를 구현하는 파이썬 코드는 다음과 같습니다.

import heapq

def yield_all_quadrant(x, y): 
    s = set([(x, y), (-x, y), (x, -y), (-x, -y),
             (y, x), (-y, x), (y, -x), (-y, -x)]) 
    for u, v in sorted(s): 
        yield u, v

def indices(X, Y):
    q = [(0, 0, 0)]
    d_current = 0
    index = 0
    while True:
        d, x, y = heapq.heappop(q)
        if d > d_current:
            index += 1
            d_current = d
        for u, v in yield_all_quadrant(x, y):
            yield (X + u,Y + v), index
        if not y:
            heapq.heappush(q, (d + 2*x + 1, (x+1), 0))
        if y < x:
            heapq.heappush(q, (d + 2*y + 1, x, y+1))

예를 들어 작은 함수에서 그리드를 채우는 데 사용됩니다.

import itertools 
def fill_grid(size, center): 
    grid = [[0]*size for _ in range(size)] 
    def clip(e): 
        coord, index = e 
        return all(0 <= c < size for c in coord) 
    for (x,y), i in itertools.islice(filter(clip, indices(*center)), 0, size**2): 
        grid[x][y] = i 
    return grid 

그리고 결과

print('\n'.join(' '.join('%2d'%i for i in gi) for gi in fill_grid(20, (8,8))))

54 48 43 39 35 33 31 30 29 30 31 33 35 39 43 48 54 59 67 74
48 42 38 34 30 27 26 24 23 24 26 27 30 34 38 42 48 55 62 69
43 38 32 28 25 22 20 19 18 19 20 22 25 28 32 38 43 50 56 64
39 34 28 24 21 17 15 14 13 14 15 17 21 24 28 34 39 46 53 60
35 30 25 21 16 13 12 10  9 10 12 13 16 21 25 30 35 41 49 57
33 27 22 17 13 11  8  7  6  7  8 11 13 17 22 27 33 40 47 55
31 26 20 15 12  8  5  4  3  4  5  8 12 15 20 26 31 38 45 53
30 24 19 14 10  7  4  2  1  2  4  7 10 14 19 24 30 37 44 52
29 23 18 13  9  6  3  1  0  1  3  6  9 13 18 23 29 36 43 51
30 24 19 14 10  7  4  2  1  2  4  7 10 14 19 24 30 37 44 52
31 26 20 15 12  8  5  4  3  4  5  8 12 15 20 26 31 38 45 53
33 27 22 17 13 11  8  7  6  7  8 11 13 17 22 27 33 40 47 55
35 30 25 21 16 13 12 10  9 10 12 13 16 21 25 30 35 41 49 57
39 34 28 24 21 17 15 14 13 14 15 17 21 24 28 34 39 46 53 60
43 38 32 28 25 22 20 19 18 19 20 22 25 28 32 38 43 50 56 64
48 42 38 34 30 27 26 24 23 24 26 27 30 34 38 42 48 55 62 69
54 48 43 39 35 33 31 30 29 30 31 33 35 39 43 48 54 59 67 74
59 55 50 46 41 40 38 37 36 37 38 40 41 46 50 55 59 66 73 80
67 62 56 53 49 47 45 44 43 44 45 47 49 53 56 62 67 73 79 85
74 69 64 60 57 55 53 52 51 52 53 55 57 60 64 69 74 80 85 93