Guard
Quite often it becomes useful to load data into a 2D array. Sometimes things can go swrong and you can put things in the wromg place. Other times you simply want/need a border to make processing simple.
One thing you can do is to put guard cells around. You can add a row at front and at the bottom as well as a column at the beginning and end of each row.
0000000000000000000000000000 0445554325267989546336y68970 0435595923452475457957527690 0445554325267989546336y68970 0435595923452475457957527690 0445554325267989546336y68970 0435595923452475457957527690 0445554325267989546336y68970 0435595923452475457957527690 0000000000000000000000000000
I typically place a value in the guard are that will not naturally occur in the data (in this case 0 [-1 is often a good choice also]). At any point you can search the guard areas for any non-guard value (this tells you that you made a subscripting error).
If you are summing up points in a 3x3 filter and use 0 as the guard value, then you can always sum up 9 values without checking for edges (faster). You will need to know how many guard points you use if a division by cell count is needed.
Return to Top of Page
3x3 Filter
This is the normal way to pass 3x3 filter over a 2D array. This just works. It can be converted to 5x5 by changing initial and final values. Note that two loops are used making a non-trivial amount of overhead.
for (i=-1; 2>i; i++)
{ // for i
for (j=-1; 2>j; j++)
{ // for j
// if used to ignore non-positive data
if (0 < ary[x+i][y+j])
{ // add it up
total = total + ary[x+i][y+j];
} // add it up
} // for j
} // for i
Here is a neat way to process a 3x3 window across a 2D array using a single loop. i and j shift from loop control variables to x and y offset array indices.
int i[7] {-1, -1, -1, 0, 0, 1, 1, 1};
int j[7] {-1, 0, 1, -1, 1, -1, 0, 1};
/* assume we are processing ary[x][y] */
for (k=0; 8>k; k++)
{ // for k
// if used to ignore non-positive data
if (0 < ary[x+i[k]][y+j[k]])
{ // add it up
total = total + ary[x+i[k]][y+j[k]];
} // add it up
} // for k
Return to Top of Page
Spiral Search
Here is a way to implement spiraling through a 2D array Imagine an array that was 11 x 11 (0..10 are the indices) and that you are 5,5 (the exact center). The 4 points closest to (5,5) are (5,4), (5,6), (4,5) and (6,5) (left, right, down and up) The 4 next closest points are (4,4), (4,6), (6,6) and (6,4) -- the diagonal points are a little further away
F E D E F
G D C A 9 A C D G
D B 8 7 6 7 8 B D
F C 8 5 4 3 4 5 8 C F
E A 7 4 2 1 2 4 7 A E
D 9 6 3 1 0 1 3 6 9 D
E A 7 4 2 1 2 4 7 A E
F C 8 5 4 3 4 5 8 C F
D B 8 7 6 7 8 B D
G D C A 9 A C D G
F E D E F
id dist dist points
-- ------- ----- ----------------------------------------------------------
0 sqrt(0) 0 = 0,0
1 sqrt(1) 1 = 1,0 0,1 -1,0 0,-1
2 sqrt(2) 1.414 = 1,1 -1,1 -1,-1 1,-1
3 sqrt(4) 2 = 2,0 0,2 -2,0 0,-2
4 sqrt(5) 2.236 = 2,1 1,2 -1,2 -2,1 -2,-1 -1,-2 1,-2 2,-1
5 sqrt(8) 2.828 = 2,2 -2,2 -2,-2 2,-2
6 sqrt(9) 3 = 3,0 0,3 -3,0 -3,-3
7 sqrt(10) 3.162 = 3,1 1,3 -1,3 -3,1 -3,-1 -1,-3 1,-3 3,-1
8 sqrt(13) 3.606 = 3,2 2,3 -2,3 -3,2 -3,-2 -2,-3 2,-3 3,-2
9 sqrt(16) 4 = 4,0 0,4 -4,0 -4,-4
A sqrt(17) 4.123 = 4,1 1,4 -1,4 -4,1 -4,-1 -1,-4 1,-4 4,-1
B sqrt(18) 4.243 = 3,3 -3,3 -3,-3 3,-3
C sqrt(20) 4.472 = 4,2 2,4 -2,4 -4,2 -4,-2 -2,-4 2,-4 4,-2
D sqrt(25) 5 = 5,0 4,3 3,4 0,5 -3,4 -4,3 -5,0 -4,-3 -3,-4 0,-5 3,-4 4,-3
E sqrt(26) 5.099 = 5,1 1,5 -1,5 -5,1 -5,-1 -1,-5 1,-5 5,-1
F sqrt(29) 5.385 = 5,2 2,5 -2,5 -5,2 -5,-2 -2,-5 2,-5 5,-2
G sqrt(32) 5.657 = 4,4 -4,4 -4,-4 4,-4
As you can see, a spiral is a real pain in the you know what to implement. If you tried to do this programatically, the calculations would kill you. With offset arrays:
x[]={ 0, 1, 0,-1, 0, 1,-1,-1, 1, 2, 0,-2, 0, 2, 1,-1,-2,-2,-1, 1, 2 ...
y[]={ 0, 0, 1, 0,-1, 1, 1,-1,-1, 0, 2, 0,-2, 1, 2, 2, 1,-1,-2,-2,-1 ...
for (k=0; 17>k; k++)
{ // loop for each spot of the spiral
process ary[i+x[k][j+y[k]]
} // loop for each spot of the spiral
As you can see, a single loop is used that never does a single
distance computation. By counting matches, the loop could short
circuit early. Imagine trying to code a spiral search manually...