To estimate an unknown point, it's required some sampling points around. The question is how to select the neighborhood sampling points? There are two approaches that can be implemented for selecting the neighborhood point, the first one is based on a specified radius from an unknown point and the second one is selecting a number or a minimum number of points around the unknown point. In this tutorial we will discuss both of them.
IDW Interpolation Algorithm Based on Block Radius Sampling PointThe flow chart in figure 1(click to enlarge) shows step by step approach to determine an estimated value at an unknown point. For this algorithm the radius (r), p-value and estimation/unknown coordinate point are defined first. Then the block area will be defined with minimum and maximum coordinate. The center of the block will be the unknown point coordinate (xz,yz). The maximum and minimum of the block coordinate will be calculated as follow:
|Figure 1. IDW Flowchart 1
If the condition returns True then the evaluated sampling point will be grouped and added in a selected point list.
Next step the algorithm will calculate the distance of each selected sampling point to the estimated point (center of the block). Each distance will be checked if it is larger than 0. If True/Yes, then the weight of the selected point will be calculated. Conversely, the weight will be 0. All the weight result will be stored in a list.
The weight list then will be checked if there is a 0 weight value exist. If the condition return True/Yes, then the estimated value will be the value on selected sampling point. Otherwise the algorithm will calculate estimated value by using IDW formula.
The code below is implementation of IDW algorithm with radius block approach.
IDW Interpolation based on Minimum Number of Sampling Point
|Figure 2. Flowchart 2
In figure 2(click to enlarge), can be seen the flowchart for the second algorithm. It can be observed from the figure that there are double loop exist in selecting sampling point stage. The first loop is to check if a sampling point is in a block, and the second loop is to check if the selected sampling point is equal or more than the defined number of point. If it returns True than the process will continue to calculate distance, weights, and determine IDW estimation value.
The code implementation for the second algorithm can be seen in the following code.
Is there any output difference between the two algorithm? We will see soon in the last part of this post.
IDW Algorithm Implementation in Python
Now it's time to implement those algorithms above. One example of the IDW function algorithm implementation can be found in a post about creating 3D terrain in Python. In the post I used the second approach which is estimated the height of interpolation point. In the post, 3D surface plot with Plotly library was used to construct 3D visualization of a terrain. But of course it can be switched to 2D using Plotly Heatmap or matplotlib pcolormesh.
Figure 3 and 4 shows the result of IDW interpolation using Plotly Heatmap. Figure 3 used the first algorithm with radius 50 m and p value 1.5. The other one used 5 minimum sampling point with the same p value. What happened with the result in figure 3? Why is it different with the other one, although they used exactly the same interpolation points?
It happened because for some points to be estimated, no sampling point can be found within radius 50 m. So we have to increase the radius to prevent this. On the other hand, it won't happen in the second approach, because the algorithm will do looping until it find a number of minimum sampling point for IDW interpolation.
|Figure 3. IDW interpolation result with 50 m radius
|Figure 4. IDW interpolation result with minimum 5 samping point