1D nearest interpolation

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.
I came up with the following function, it seems simple and I don't know about its performance in extreme conditions!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}
You could do
1
2
3
4
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 }
Last edited on
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.
Last edited on
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:
1
2
3
4
5
6
// A
std::vector<double> y_new;
y_new.resize( x_new.size() );

// B
std::vector<double> y_new( x_new.size() );
If you are really looking for performance, then you need to abandon linear interpolation altogether. This interpolation is simple but inaccurate.
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?
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!
Topic archived. No new replies allowed.