Weighting (Terrain)

Sketch and Example

I will start with a small sketch I did to at least consistently name the parts of interest. We have three points named P₁, P₂ and P₃ and their heights named h₁, h₂ and h₃. We are interested in the height at point P which is d₁ from P₁, d₂ from P₂ and d₃ from P₃.

We further assume d₁ and d₂ to be of equal length and d₃ to be twice as long. So the weighted sum we have to come up with should weight P₁ and P₂ with the same value and give P₃ half as much weight. Expressed as fractions we want the relation of P₁:P₂:P₃ to be 2:2:1.

When we look at the distances we can see, that their inverse behaves like we want to, 1/1 : 1/1 : 1/2 (I ignored the common factor in the three distances), if we multiply by the common denominator 2 we get to the the ratio of 2:2:1 we were looking for.

So to find the height for the point P we calculate (2 h₁ + 2 h₂ + h₃) / 5. The 5 is just the sum of the factors to normalize the height.

Generalization

Now that we know what we have to calculate we can do the same in a general form. Assuming N points (don't forget, with N values the indices run from 0 to N-1) having influence and using the same naming scheme as above we can express the height as:

Now how do we get to the next height without storing all the heights and distances. We will have the height, as it makes sense to store it at every step because we then will need no post processing. The other components we have to find. So the next height, when we add another point with index N:

So the next value we can calculate by multiplying the old numerator by the new distance and add the product of the new height with the product of all the distances to get the new numerator. Similarly we get the new denominator by multiplying the old one with the new distance and adding the product of the old distances. So we obviously have to store the product of all the distances and either the old numerator or denominator, as we can calculate the other one when we have the old height value.

Remarks

Although the intended result seems simple enough and also the reasoning behind the result is logical, coming up with the incremental formula isn't easy. I didn't calculate it from the start properly and so wasted a lot of time trying to just write it down.