Algorithm to find all diagonal point of a given point

Question

How to write an algorithm to find all diagonal point of a given point?

Such as:

00 01 02 03 04 05
10 11 12 13 14 15
20 21 22 23 24 25
30 31 32 33 34 35
40 41 42 43 44 45
50 51 52 53 54 55

When selected a point 34, how do I find the neighboring diagonal points? (01,12,23,45,25,43,52)

00(01)02 03 04 05
10 11(12)13 14 15
20 21 22(23)24(25)
30 31 32 33  X 35
40 41 42(43)44(45)
50 51(52)53 54 55

Since I'm not stating the programming language I use, I would more prefer pseudocode or instructions.

Ps: I don't want direct code giveaway as I'm trying to learn to code by following pseudocode or instructions.

Answer 1

Let's say your point is on (a, b). A given (c, d) point is on the same diagonal if exists an i integer, so that

a + i = c and b + i = d or a + i = c and b - i = d

since the distance is i, you can do the following:

for i <- 0, n - 1
    if i <> a then
        if (b - i) >= 0 and (b - i) < n then (i, b - i) is on the diagonal
        if (b + i) >= 0 and (b + i) < n then (i, b + i) is on the diagonal
    end if
end for

Answer 2

Brute force solution

Write some simple for loop over the whole grid. Any points on the diagonal have a slope of one with the starting point

Assuming a zero indexed N x N box and x increases left to right and y increases top to bottom

values = list()
location = (3,4)

for y in 0 ..N-1:
    for x in 0..N-1:
        if (x, y) == location:
            continue 
        slope = abs(y-location(0))/abs(x-location(1))
        if slope == 1:
            list.add( (y, x) ) 

More optimal solution

Start from the location coordinate, then fan outwards, increasing and /or decreasing both of the x, y points at the same time. The tricky part of that method is to not break the loop when one direction hits a boundary

Answer 3

I wrote an implementation for this accepted answer (https://stackoverflow.com/a/45896595/1566372) in C#

public IEnumerable<(int i, int j)> GetDiagonalPoints(int a, int b, int n)
        {
            /*
             for i <- 0, n - 1
                if i <> a then
                    dist = Abs(i - a)
                    if (b - dist) >= 0 and (b - dist) < n then (i, b - dist) is on the diagonal
                    if (b + dist) >= 0 and (b + dist) < n then (i, b + dist) is on the diagonal
                end if
            end for
             */
            for (int i = 0; i < n; i++)
            {
                if (i != a)
                {
                    var dist = Math.Abs(i - a);
                    if ((b - dist) >= 0 && (b - dist) < n) yield return (i, b - dist);
                    if ((b + dist) < n) yield return (i, b + dist);
                }
            }
        }

Answer 4

It's easier to me to write the code itself rather than a pseudocode...

N is the size of the zero-based matrix.

public static void diagonal(int N, int x, int y) {

    int max = Collections.max(Arrays.asList(x, y, N - x, N - y));
    for (int i = 1; i < max; i++) {
        addIfValid(N, x + i, y + i);
        addIfValid(N, x + i, y - i);
        addIfValid(N, x - i, y + i);
        addIfValid(N, x - i, y - i);
    }
}

private static void addIfValid(int N, int i, int j) {
    if (i >= 0 && i < N && j >= 0 && j < N) {
        // collect the results in a list or process them in any way
        System.out.println(i + ":" + j);
    }
}

Answer 5

As guided by Lajos Arpad answer, I made some changes to suit my needs.

//point_given = (3,3)
//matrix = 5*4
/*
00 01 02 03
10 11 12 13
20 21 22 23
30 31 32 33
40 41 42 43
*/
x = 3 // x of given point
y = 3 // y of given point
N = 5 //row
M = 4 //col

//use row to iterate only
for i = 0 to N, i+1
    //no diagonal point on same row of given point
    if i <> x
        //to check if y in bound of matrix col for the left and right diagonal
        //used abs(x-i) to know how much value to add to y col
        //e.g. 1 row up of x means the diagonal point y is 1 col left and 1 col right to given y
        if((y-abs(x-i))>=0) then (i,y-abs(x-i)) is a diagonal point on left
        endif
        if((y+abs(x-i))<M) then (i,y+abs(x-i)) is a diagonal point on right
        endif
    endif
endfor

Answer 6

I wrote a Python solution based @Rady solution: https://stackoverflow.com/a/63219124/14726555

I also added code to draw diagonals of any size so it is easier to see why this solution works and how it is useful for generating diagonals.

def diag_iter(row, col, n):
    for i in range(n):
        if i != row:
            dist = abs(i - row)
            if 0 <= col - dist < n:
                yield (i, col - dist)
            if col + dist < n:
                yield (i, col + dist)

def print_diag(row, col, n):
    board = [['_'] * n for _ in range(n)]
    board[row][col] = 'X'
    for diag_row, diag_col in diag_iter(row, col, n):
        board[diag_row][diag_col] = "X"
    print(f"Board of size {n} with diagional starting at ({row}, {col})")
    for row in board:
        print(row)

print_diag(1, 1, 5)
print_diag(2, 2, 5)
print_diag(3, 4, 5)
print_diag(0, 3, 5)
"""
Board of size 5 with diagional starting at (1, 1)
['X', '_', 'X', '_', '_']
['_', 'X', '_', '_', '_']
['X', '_', 'X', '_', '_']
['_', '_', '_', 'X', '_']
['_', '_', '_', '_', 'X']
Board of size 5 with diagional starting at (2, 2)
['X', '_', '_', '_', 'X']
['_', 'X', '_', 'X', '_']
['_', '_', 'X', '_', '_']
['_', 'X', '_', 'X', '_']
['X', '_', '_', '_', 'X']
Board of size 5 with diagional starting at (3, 4)
['_', 'X', '_', '_', '_']
['_', '_', 'X', '_', '_']
['_', '_', '_', 'X', '_']
['_', '_', '_', '_', 'X']
['_', '_', '_', 'X', '_']
Board of size 5 with diagional starting at (0, 3)
['_', '_', '_', 'X', '_']
['_', '_', 'X', '_', 'X']
['_', 'X', '_', '_', '_']
['X', '_', '_', '_', '_']
['_', '_', '_', '_', '_']
"""