Interpolating between multiple Points
<p>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 &quot;value&quot; at this point of the plane. Now I want to calculate the interpolated Point at some given coordinates.</p>
<p>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. <a href="https://i.stack.imgur.com/FoKbr.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/FoKbr.png" alt="sketch to my idea" /></a></p>
<p>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?</p>
<hr />
<p>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.</p>
<hr />
<p>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.</p>
<p>The Data is stored in a <code>HashMap&lt;Vector2f, Float&gt;</code> where <code>Vector2f</code> is a simple class consisting of 2 floats. There is nothing sorted.</p>