Equidistant Points in a Matrix

Question

I have a matrix of floating point values. Relative to a given origin (x and y index, point "0"), I would like to obtain the indices of equidistant points, starting with the nearest points ("1") and up to a specific number ("12" in this animated example):

The distance is the slant range between a point and point 0. For example, point "4" has the distance sqrt(2^2+1^2) = sqrt(5) = 2.24.

Does anyone know a corresponding algorithm to obtain these indices in an effective way?

Answer 1

Rephrasing the question, you want to enumerate the points by increasing euclidean distance to the center.

Here are two answers on https://math.stackexchange.com to this problem how-to-enumerate-2d-integer-coordinates-ordered-by-euclidean-distance and algorithm-for-enumerating-grid-points-by-distance-from-given-point

Basically:

• use symmetry to consider only point with 0 <= x <= y;
• note that for a given x points will be enumerated with increasing y;
• use a priority queue to keep the next candidate for each vertical line.

With n the last index you generate, the time complexity will be O(n log n) and the space complexity O(sqrt(n)).

NB: to avoid floating point computation, consider the squared distance, which doesn't change the order of your points.

Here some python code implementing this idea:

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

and used for example in a small function to fill a grid

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 

and the result

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