nearest neighbor mapping of 1D index for 2D array into a smaller 2D array

Question

This is in C.

I have two 2D arrays, ArrayA and ArrayB, that sample the same space. B samples a different attribute than ArrayA less frequently than ArrayA, so it is smaller than A.

Just to try to define some variables: ArrayA: SizeAX by SizeAY, indexed by indexA for a position posAX, posAY ArrayB: SizeBX by SizeAY, indexed by indexB for a position posBX, posBY

ArrayA and ArrayB are pointers to the start of the array, where the row of X's is stored first, then Y is incremented, and the next row of X's is stored (Y=1)

So I need to set indexB from a given indexA, such that it is a nearest neighbor sample, to associate with indexA's value.

Here's where I am (correct any errors please! Note that I am starting at index 0): If ArrayA is 9x9 and ArrayB is 3x3: (posX,posY) posA 0,0; indexA = 0 posB 0,0; indexB = 0

posA 8,0; indexA = 8 (end of first row) posB 2,0; indexB = 2

posA 0,1; indexA = 9 posB 0,0; indexB = 0 (still closer to the bottom point)

posA 0,3; indexA = 27 posB 0,1; indexB = 3

posA 8,8; indexA = 80 (last point) posB 2,2; indexB = 8

so far I have: indexA = posAX + (posAY * SizeAX)

what I've tried (and of course failed): indexB = (int) (indexA * (SizeBX * SizeBY / (SizeAX * SizeAY)) + 0.5) // Only appears to work for the first row and last value.. but this clearly doesn't work - but I am curious as to how exactly it maps the two together, but I'll look into that after I fix it..

I didn't have access to posAY or posAX, just indexA, but I should be able to break it down using mod and remainder, right? or is there a more efficient faster way? A

I also tried this:

indexB = (posAY * SizeBY / SizeAY) * SizeBY + (posAX * SizeBX / SizeAX)

I think the problem is that I need to round the X and Y indexes separate then use SizeBX and SizeBY afterwards?

An extra caveat is that ArrayA and ArrayB come from larger data set that both sample a larger space. Since the rectangle is arbitrary, either ArrayA or ArrayB could have the point closest to the bounds of the rectangle, leading to other issues as to which way the nearest neighbor is really grabbing. I am not sure about how to address this, either.

Answer 1

What you essentially mean is that you have two grids with different spacing covering the same area and given an index of a gridpoint in one of them you want to find the closest one in the second. Like this:

int posBX = (int)floorf((float(posAX) / float(sizeAX - 1)) * float(sizeBX - 1) + 0.5f);
int posBY = (int)floorf((float(posAY) / float(sizeAY - 1)) * float(sizeBY - 1) + 0.5f);
int indexB = posBX + posBY * sizeBX;

To get posAX and posAY from indexA:

posAX = indexA % sizeAX;
posAY = indexA / sizeAX;

To do bilinear interpolation:

float bx = (float(posAX) / float(sizeAX - 1)) * float(sizeBX - 1);
float by = (float(posAY) / float(sizeAY - 1)) * float(sizeBY - 1);
int x = min(int(floorf(bx)), sizeBX - 2); //x + 1 must be <= sizeBX - 1
int y = min(int(floorf(by)), sizeBY - 2); //y + 1 must be <= sizeBY - 1
float s = bx - float(x);
float t = by - float(y);
float v[4];
v[0] = arrayB[x + y * sizeBX];
v[1] = arrayB[x + 1 + y * sizeBX];
v[2] = arrayB[x + (y + 1) * sizeBX];
v[3] = arrayB[x + 1 + (y + 1) * sizeBX];
float result = (v[0] * (1.0f - s) + v[1] * s) * (1.0f - t) +
               (v[2] * (1.0f - s) + v[3] * s) * t;

Answer 2

Those are some revolting names you've chosen, but at least they're defined.

I think you want to go through (x,y) in [0...1]x[0...1] real coordinate space; that is, the lower right of A should grab the value from the lower right of B, and likewise for mid-upper-left, etc. This means that you should think of the outside edges of points in your array as the 0-width point samples values at the edges of the [0...1]x[0...1] box; i.e. if you have a 3x3 array, there's one point at (0.5,0.5) and the rest are along an edge.

I'll assume your 2d B array has real values in it, so that it makes sense to interpolate; because the arrays are of different sizes

Here's the scheme for going from a

indexA -> (posAX,posAY) -> (x,y) -> (fracBX,fracBY) ->(by nearest neighbor interpolation) value from ArrayB

Important: (fracBX,fracBY) are real-valued coordinates in the box [0...SizeBX-1]x[0...SizeBY-1].

Let's take it one step at a time. Assuming I understood you, values are in memory in left->right, top->bottom (english reading) order, just like standard C arrays. Then:

unsigned posAX=indexA%SizeAX;
unsigned posAY=indexA/SizeAX;

Now, let's map to (x,y):

double x=posAX/(SizeAX-1.0); // we get double division when we subtract by 1.0
double y=posAY/(SizeAY-1.0);

Now, to (fracBX,fracBY), where 0<=fracBX<=SizeBX and 0<=fracBY<=SizeBY:

double fracBX=x*(SizeBX-1);
double fracBY=y*(SizeBY-1);

Now, to interpolate between the (up to 4) nearest integral points in the B array:

unsigned intBX=(unsigned)fracBX;
double aBX=fracBX-intBX;
unsigned intBY=(unsigned)fracBY;
double aBY=fracBY-intBY;
double *bv=ArrayB+(intBX*sizeBY)+intBY;
#define INTERP(alpha,v1,v2) ((1-alpha)*v1+alpha*v2)
#define INTERPI(alpha,i1,i2) (alpha>0 ? INTERP(alpha,bv[i1],bv[i2] : bv[i1])
double v0=INTERPI(aBX,0,1);
double value=fracBY>0 ? INTERP(aBY,v0,INTERPI(aBX,sizeBY,sizeBY+1)) : v0;

value is your answer. The checks for the fractional positions aBX and aBY being 0 are needed to prevent accessing values off the end of the array (which can cause a segfault even though the values are ignored by multiplying by 0). Or you can simplify things by allocating 1 more row/column than you need.

bv[0] is the ArrayB[intBX][intBY], bv[1] is one to the right, bv[sizeBY] is one down, and bv[sizeBY+1] is one down and to the right. (aBX,aBY) is another point in [0...1]x[0...1], but this time bounded by those four adjacent points in ArrayB.