Finding distance in a matrix in C

Question

I have a matrix of numbers and want to find the distance of each item from its farthest non-zero neighbour (in four directions). I came up with this idea

#include <stdlib.h>
#include <stdio.h>

int min(int a, int b, int c, int d)
{
    int e = a < b ? a : b;
    int f = c < d ? c : d;
    int r = e < f ? e : f;
    return r;
}

int main()
{

    int width = 50;
    int height = 50;
    int points[width][height];
    int distances[width][height][5]; // 0 left 1 right 2 bottom 3 top 4 min

    // adding some random values, zero and non-zero
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            points[x][y] = rand() % 100;
        }
    }

    // scanning in four direction to check if the previous neighbour exists
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if (points[x][y] > 0)
            {
                distances[x][y][0] = distances[x - 1][y][0] > 0 ? distances[x - 1][y][0] + 1 : 1;
            }
        }
        for (int x = width - 1; x >= 0; x--)
        {
            if (points[x][y] > 0)
            {
                distances[x][y][1] = distances[x + 1][y][1] > 0 ? distances[x + 1][y][1] + 1 : 1;
            }
        }
    }

    for (int x = 0; x < width; x++)
    {
        for (int y = 0; y < height; y++)
        {
            if (points[x][y] > 0)
            {
                distances[x][y][2] = distances[x][y - 1][2] > 0 ? distances[x][y - 1][2] + 1 : 1;
            }
        }
        for (int y = height - 1; y >= 0; y--)
        {
            if (points[x][y] > 0)
            {
                distances[x][y][3] = distances[x][y + 1][3] > 0 ? distances[x][y + 1][3] + 1 : 1;
            }
        }
    }

    // finding the minimum of four distances
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if (points[x][y] > 0)
            {
                distances[x][y][4] = min(distances[x][y][0], distances[x][y][1], distances[x][y][2], distances[x][y][3]);
                printf("%d %d %d %d %d %d %d \n", x, y, distances[x][y][0], distances[x][y][1], distances[x][y][2], distances[x][y][3], distances[x][y][4]);
            }
        }
    }

    return 0;
}

but it doesn't work as expected. Most likely, I have made a stupid mistake and have a blind eye for that to see.

One problem is that some of your array accesses are out of bounds. — 1201ProgramAlarm, Jul 03 '21 at 01:08
@1201ProgramAlarm this is exactly the problem with the results, but where is the out of bound elements? — Googlebot, Jul 03 '21 at 01:09
Loops that start at index 0, but access element `[x - 1]`, starting with element width-1 and accessing element `[x+1]`, etc. — 1201ProgramAlarm, Jul 03 '21 at 01:11
@1201ProgramAlarm this what I wanted to check if `[x-1]` exists or not. I assumed `distances[-1][y][0]` will be non-existence and we assign `1` to distances[0][y][0]. Apparently, this is not the intended behaviour in C. — Googlebot, Jul 03 '21 at 01:14
@Neil it's a matrix of 0 and 1. I used the notion of non-zero because I used `rand()%100`. The distance is calculated by counting. — Googlebot, Jul 03 '21 at 02:23
@Neil this is more details of the problem I try to solve: https://stackoverflow.com/questions/68238325/calculating-the-distance-of-items-from-non-empty-edges-in-a-matrix — Googlebot, Jul 03 '21 at 17:01
Thanks; that looks interesting. So you want to know the minimal distance from each non-zero square to another non-zero square? Is there a reasonable bound on the size of the matrix? Some pre-calculations might improve the search efficiency, _eg_ if the distance is a bounded metric, you can sort the distances before even looking at the matrix? — Neil, Jul 03 '21 at 22:11

score 2 · Accepted Answer · edited Jul 09 '21 at 10:48

2

At line 34:

if (points[x][y] > 0)
{
    distances[x][y][0] = distances[x - 1][y][0] > 0 ? distances[x - 1][y][0] + 1 : 1;
}

when x is zero, you are referencing up to 250 (50 * 5) words before the address of distances, which is an invalid thing to do.

edited Jul 09 '21 at 10:48

Dharman

30,962
25
85
135

answered Jul 03 '21 at 01:15

mevets

10,070
1
21
33

Finding distance in a matrix in C

1 Answers1