For an online project that’s almost completed, we’re polling real-time data from thirty-something weather stations to determine the weather at any given location in the Netherlands. Now that we’ve started beta testing, we concluded that our calculation to interpolate the weather was really, really bad, so I needed to come up with some last-minute thinking. Turns out I had to cough up my third grade math teachings and work the numbers for 36 hours, only to realize that it was a damn hard topic and I should have thought of this earlier in the process.
Thirty points are spread over a fairly spacious area. Pick a random point D within or close to that area, find the nearest three points A, B and C and interpolate the relative distances to a weight distribution list (a, b and c), that we can use to multiply the actual weather values: A.wind * a + B.wind * b + C.wind * c. That way we can make a good estimate of what the weather must be like at point D. Sounds simple, right? I thought so too, but found it was a lot harder than I assumed. I hope I can spare someone the trouble of going through all this, by explaining what I did.
The first thing to clarify is that if you have the weighing parameters for a given point in space, you can weigh any numerical data. For my project I need to weigh weather data (radiation, wind, heat, etc.), but for figuring out what algorithm to take, I used colors. They’re easy to compute and the visual result will instantly tell you if you’re on to something. So I started out writing a little test that would allow me to draw colored triangles:
As you can see, the fourth point called “D” shows the interpolated value both in color and numbers, and if you let that point wander through every location in the area, you can draw a pretty picture like this this:
The algorithm measures the distance of D to the nearest point on the line opposite of A, which is BC and stores it as the weight of point A. You do this three times and then normalize the values by dividing them through the total of the three distances. You then have three weight values that total 1, or 100%, and you can use them to multiply the original values. This alone is not enough. Because this method will only calculate correctly if the point you’re dealing with is within the borders of the triangle! I was so happy to see the insides of the triangle all pretty and smooth, but I felt pretty stupid when everything outside of the triangle went horribly wrong. The solution is to find out on what side of each line point D is. If it’s on the same side as the corner you’re weighing, the weight is valid. If it’s on the other side of the line, you should set it’s value to zero and stretch the remaining weights to become 100%. That way you get a nice and clean interpolation, whether you’re inside or outside the triangle.
If someone could have told me this, it would have saved me some 30 hours in the last week before going live with the project, but hey, I feel a lot smarter now that I’ve figured it out myself! Here’s an interactive demo:
The resulting images might look familiar to you, if you’ve ever dealt with 3D visualization techniques, because it is called Gouraud Shading. I’m not sure if I’m using the exact same method, because all reference sites that talk about Gouraud are a bit too elaborate for my use. I don’t have a 3D coordinate space, I don’t have lighting, I’m not even working towards a visual result. I just want to calculate the weather!
It took me several wrong approaches before I finally got this one up here, but the solution is still not optimal. For the example of three points, my last method nailed it. But I don’t just have three points, I have thirty! In 3D applications, all points that are used for shading, are always within the triangles of the mesh. But for my application, I neither have a mesh, nor can I stay within the triangles that the weather stations define. Together with automatic sorting of the three nearest points, this introduces a margin of error, as you can see in this image. I have tested it and because the measured weather data is already smoothed out by mother nature, this presents no big issues.
However, if there’s someone out there that knows a better solution to my problem, please share!
Pingback: epologee.com blog » Blog Archive » Nuon Solar Race Holland
Hi, cool shading method! I should however add that this is not an exactly linear inerpolation as was probably your intent. I implemented a similar problem with a 3D plane:
With the 3 triangle points, you can simply a mathematical function z(x,y). x,y are your pixels and z is the color.
You calculate 3 planes (one for each color), which gives you a 100% exact linear interpolation.
Also this might probably be even faster, as I think your distance calculation involves several square roots?
Anyway, you definitely came up with a cool method. But if you need an accurate linear interpolation in the future, this is the math you forgot
Oh I forgot to paste the link that has the (very easy) calculations: http://www.ems-i.com/smshelp/Data_Module/Interpolation/Linear_Interpolationsms.htm
The “elevation” z, which is mentioned, is is the grayscale color component. Make a new plane for each color.
Awesome comment, thanks Huffman! I’ll be sure to try it out on the weighted triangles. I still need the above method for points outside of the triangles though, since it’s easy to get outside of the mesh if you’re on a map with limited data points.
I’m working with quite similar project. I am creating depth map from control point soap. Points are not in order, they have x,y and depth, and i need to create nice and smooth map out of them.
Instead of getting three of the closest point, i am finding the closest points which products a tringle which encloses the point of interest. That’s not the same than using just three closest point.
It removes most of the errors that can be seen in your picture.
If i can’t find the enclosing triangle, the point is stated as ‘unknown’. But in your case, if you want to calculate areas outside the ‘polygon’, you can simply use the two of the closest point and interpolate between them. As there is no enclosing triangle, there is no need to use three values in interpolating, two is enough. You gain nothing by using three.
I can post the code which finds the triangle, if you want it.
That sounds like a valuable addition, mdmx! I tried out code to find the enclosing triangle, but still found that there were area’s that would ‘break’ the smooth transitions. Would like to see your solution!
i don’t know if this site is still actively monitored but, if you haven’t already completely solved your problem, you might want to check into Voronoi/Delaunay duals. i have used the technique in several graph-theoretic applications for determining multi-lineal interpolation of centroids between sets of points in various informational spaces. another option would be to look at Bezier splines to maintain smooth interpolation … fwiw
Hi Ktb, thanks for the suggestion. Voronoi/Delauney would have been a better fit indeed. The project is long over though, but it’s a good reference. Thx.