Use a boolean "mask" array for array indexing

Question

I have a very big array with dimensions (nr,nc) row and cols. I iterate over this array to calculate the function "fun" from a constant entry of this array (px,py). The calculation for this function is only relevant in a constant area (distance d) around this point. So my goal is to speed up the code and only calculate in this circle around the point (px,py).

int i;
int j;
for(i=0; i<nr; i++){
    for(j=0; j<nc; j++){
        *(arr_stg+i*nc+j) = fun(i,j,px,py);
    }
}

I also have a function to calculate a boolean "mask" (I don't know if that's the right word for this). I calculate it with the euclidean distance around a sample point. So for a given distance, i.e. 4 I calculate this kind of mask-array:

0 0 0 0 1 0 0 0 0
0 0 0 1 1 1 0 0 0
0 0 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 0 0

The exact form (if it's a zero or a one) is not relevant here, should be working for any kind of this nxn-"masks".

My question is, how do I have to change the two for loops to iterate only over this mask around the given point in a way that I get a faster code then just calculate it for all i,j's of the big array and don't use the ones with a distance greater than the given one.

You can always use BFS or DFS algorithms from your (px, py) point. This way you will process only points inside the circle. And you won't even need to precalculate and save mask and iterate over the whole array. — Valerii Boldakov
– Valerii Boldakov, Commented Oct 17, 2019 at 10:14
With your mask, you can use a simple if statement. if(mask[i][j]) *(arr_stg+i*nc+j) = fun(i,j,px,py); — klutt
– klutt, Commented Oct 17, 2019 at 10:15
What is arr_stg definition ? nc ? px? py? iterate only over this mask - in what way or does it doesn't matter which point is the first? — KamilCuk
– KamilCuk, Commented Oct 17, 2019 at 10:15
If your mask is sparse (has only few 1's in relation to the number of 0's), it might be better to have a list of coordinate pairs over which to iterate or have a smaller mask with a bounding box. — M Oehm
– M Oehm, Commented Oct 17, 2019 at 10:17
instead of pre-calculating the mask array, you can pre-calculate the pairs of indexes (as a single-dimensional array) and then use them in a single loop to calculate the fun. — Serge
– Serge, Commented Oct 17, 2019 at 10:40

vgru · Accepted Answer · 2019-10-17 10:47:48Z

1

Generally, if you have a mask of size d centered around a point (xc, yc), you need to iterate through the ranges of:

(xc - d) <= x <= (xc + d)
(yc - d) <= y <= (yc + d)

Or, if you have a mask array MASK[2*d+1, 2*d+1], then you would simply end up with:

// iterate through MASK dimensions
for (var mi = 0; mi < 2 * d + 1; mi++)
   for (var mj = 0; mj < 2 * d + 1; mj++)
   {
        // move to the right location
        var x = xoffset + mi;
        var y = yoffset + mj;

        // do something with (x, y) and MASK[mi, mj]
   }

You need to make sure, however, that xoffset + mi and yoffset + mj does not exceed the bounds.

answered Oct 17, 2019 at 10:47

vgru

51.5k17 gold badges127 silver badges213 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Python_Trader Over a year ago

I think that you gave me the right idea here, but your code isn't exactly doing what I want or what you stated before. You are iterating over the mask but starting with the offset-point at (0,0) of the max and not the mid-point of the mask. I think mi and mj should start at -d and go up to d. Maybe that's the best solution. But I still would have a bit of an overhead because of the iterations trough the zeros of the mask. Maybe that's good enough.

vgru Over a year ago

Well, the range is centered around (xc, yc), but there are no negative indices in C arrays. My assumption was that the mask array is smaller than the actual array and contains just the mask, in which case you would need to offset it

Collectives™ on Stack Overflow

Use a boolean "mask" array for array indexing

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related