1D nearest interpolation

[RezaAb]

Dear all,

I am trying to find a routine to interpolate a 1D vector based on NEAREST NEIGHBOR. For example, if I have the following vectors, looking for the vector "d" based on the values I have in "b" but for 1 through 20.

a = { 1, 5, 7, 10, 14, 18, 20};
b = { 0.2, 0.5, 0.7, 0.3, 0.6, 0.9, 0.1 };
c = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };

I tried several web pages, but could not find something valuable.

Thanks.

[RezaAb]

I came up with the following function, it seems simple and I don't know about its performance in extreme conditions!

std::vector<double> MyClass::interp1(std::vector<double> &x, std::vector<double> &y, std::vector<double> &x_new)
{
	std::vector<double> y_new;
	y_new.resize(x_new.size());
	int counter = 0;
	for (int i = 0; i < x_new.size(); i++) {
		double up_dist = x_new[i] - x[counter];
		double down_dist = x[counter + 1] - x_new[i];
		if (down_dist < up_dist) { y_new[i] = y[counter+1]; }
		else { y_new[i] = y[counter]; }

		if (x_new[i] >= x[counter+1]) { counter++; }
	}
	return y_new;
}

[helios]

You could do

std::vector<double> d(b.size());
size_t i = 0;
for (auto &element : d)
    element = c[floor(c.size() * b[i++] + 0.5)];

Given your example above, this code will produce a b d equal to {5, 11, 15, 7, 13, 19, 20 }

[lastchance]

It won't work. You always assume that x_new[i] lies between x[counter] and x[counter+1], but there is nothing to enforce that.

To take as an example, suppose x[] and y[] were the a and b vectors in your first post. Suppose then that the first value of x_new[] was 11. Then you would be looking for 11 between 1 and 5 ... and, rather uncomfortably, your code would find it! Wrongly, obviously.

There's also the possibility of exceeding array bounds with counter+1 in line 12.

Mathematically, you would remove ambiguities and discontinuities if you switched to linear interpolation rather than nearest neighbour.

EDIT: you may want to clarify what you are actually trying to do. Myself and @helios have interpreted your first post in very different ways, and I was trying to decipher it by looking at the second one.

[keskiverto]

There seems to be further assumptions:
* The 'a' is an ordered set.
* The 'b' has same size as 'a'. Nothing in your code ensures that.

Are the a and c double values? Your example shows integers.

The (a,b) looks like a lookup table. Why two separate vectors?
Perhaps: http://www.cplusplus.com/reference/map/map/equal_range/

Do the c and d form a table too?

Is there any need for the c to be ordered?


What is the difference between these:

// A
std::vector<double> y_new;
y_new.resize( x_new.size() );

// B
std::vector<double> y_new( x_new.size() );

[CroCo]

If you are really looking for performance, then you need to abandon linear interpolation altogether. This interpolation is simple but inaccurate.

[jonnin]

it is 100% accurate when dealing with (drum roll) ... lines :) however you can back-solve a line, get the function, and get the answer faster, so the performance note is correct. Its not bad for line-like functions (consider x^2n away from zero). Its very limited for anything curvy, of course. Calc tells us that functions with a dx always approximate a line when you get the points close enough together, so there are merits "zoomed in" on curves also.

Can the OP explain better what we are doing here?

[RezaAb]

Thank you all very much, using your suggestions, I improved my function and checked the results with the Matlab nearest interpolation for 1D vectors and got correct results. As I mentioned previously, it might be problematic for other situations but works well for my case!