CODEWITHSUNDEEP
javamathinterpolationpoint
Erik Brendel
Erik Brendel

Reputation: 714

Interpolating between multiple Points

I need some algorithm ideas here. I have a big set of data (~100k entries) of two-dimensional Points as objects with a third variable as the "value" at this point of the plane. Now I want to calculate the interpolated Point at some given coordinates.

My only idea so far would be to iterate over the whole dataset and collect a list of the 4 nearest Points to the one I want to calculate, and then to interpolate between them. sketch to my idea

How do I interpolate weighted (by the point's distance in this case) between multiple data? So that Points nearer to the cross are more present in the result?

Do you have any other ideas on how to get the interpolated value at a given coordinate in this case? It should be relatively exact (but does not have to be 100%) and should not take ages to calculate, since this has to be done some 10.000 times and I don't want the user to wait too long.

About the data: The Points are nearly in a grid, and the values of the 2dimensional Points are actually height values, so the values of two near points are also nearly equal.

The Data is stored in a HashMap<Vector2f, Float> where Vector2f is a simple class consisting of 2 floats. There is nothing sorted.

Upvotes: 1

Views: 5639

Answers (2)

user1803551
user1803551

Reputation: 13408

Looks like Bilinear interpolation. There are a few general algorithms and if you have constraints on your data you might be able to use them to simplify the algorithms. Since "the Points are nearly in a grid", I made the approximation that they are ("It should be relatively exact (but does not have to be 100%) and should not take ages to calculate").

Given

  1. 2 float x, y as the point you want to interpolate.
  2. 4 objects of type Vector2f named v1 to v4, and assuming the coordinates of each can be accessed as v1.x and v1.y and that they are approximately on a grid:
    v1.x == v3.x, v2.x == v4.x, v1.y == v2.y, v3.y == v4.y
  3. That the value of each Vector2f was retrieved as float h1 = map.get(v1) (h stands for "height"), then you could write something like this:

float n1 = h1 * (v2.x - x) * (v2.y - y);
float n2 = h2 * (x - v1.x) * (v2.y - y);
float n3 = h3 * (v2.x - x) * (y - v1.y);
float n4 = h4 * (x - v1.x) * (y - v1.y);
float den = (v2.x - v1.x) * (v2.y - v1.y);
float height = (n1 + n2 + n3 + n4) / den;

As a side note, you might also want to look into making your class strictfp.

Upvotes: 2

Artur Biesiadowski
Artur Biesiadowski

Reputation: 3698

This is non-obvious problem. It is a lot easier for 3 points, with 4 points you will get into situations which are ambigous. Imagine (for points surrounding your sample in square) ul and br corners having value 1, and other corners having value 5. It can be interpreted as valley with height 1 going through center, ridge with height 5 going there, or some kind of fancy spline saddle shape. If you add irregularity of grid into account, it becomes even more fun with closest 4 points being on same side of sample (so you cannot just choose 4 closest points, you need to find 4 bounding points).

For 3 point case, please check https://en.wikipedia.org/wiki/Barycentric_coordinate_system#Application:_Interpolation_on_a_triangular_unstructured_grid

For 4 point case on regular grid,you can use https://en.wikipedia.org/wiki/Bilinear_interpolation to generate kind of 'fair' interpolation.

For 4 points on irregular grid, you can look into solution like http://www.ahinson.com/algorithms_general/Sections/InterpolationRegression/InterpolationIrregularBilinear.pdf but be careful with finding proper bounding points (as I mentioned, finding closest ones won't work)

Upvotes: 3

Related Questions