Triangles, interpolation and the math I forgot

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!