I'm new to interpolations.
I'm looking for documentation to understand how inverse distance algorithm works and how to code it.
My intention is to code IDW algorithm in JavaScript to see if it is feasible in performance meaning.
Add a comment
|
2 Answers
Well, Wikipedia is the place to look at.
what you do is:
1) compute the distance between your location and the observations
2) define the weights as 1/distance^p
3) sum the weighted value of each observation
4) normalise the result by the sum of the weights
Note that IDW relies on one parameter(p), the power of the distance. The larger it is, the more infuence you give to the closest observation. the extreme value 0 and infinity yield a simple average and a thiessen polygonsation, respectively. The optimal parameter can be found based on cross-validation methods (but this add computational cost, of course).
Note also that you can limit the number of neighbours that are taken into account to remove the influence of far away points.
IDW is one of the fastest interpolation method, but not the one I prefer...
-
+1. However, the formula is the easy part. The hard parts are (1) efficiently selecting neighboring data (especially when implementing barriers) and (2) dealing with the exceptional cases such as when distances are zero or individual locations have multiple values. (Even many commercial packages, such as ArcGIS, don't get that correct or cannot even handle such situations.)– whuberCommented Mar 19, 2014 at 20:38
-
for 2, the way to deal with zero distances is to ignore other values if one distance is zero (infinite weight : IDW is an exact interpolator). Concerning 2 points at the same location, IDW will give them the same weight by design. For intelligent handling of this particular case, one should use kriging(the difference is that kriging will use the average value once, but IDW uses it twice)– radouxjuCommented Mar 19, 2014 at 21:10
-
On the contrary, IDW, when properly implemented, also averages repeated values at common locations. This drops directly out of the formula: no special treatment is necessary to handle this case. (Which is why it is baffling that some software cannot deal with it.) Kriging, on the other hand, usually does not use the average value (except when the variogram is a pure nugget). That is why Kriging requires a preliminary step to aggregate clusters of very close data points.– whuberCommented Mar 20, 2014 at 14:42
-
I agree that a proper way to process coincident points is important, and averaging is then the safest solution. However, by construction, IDW only accounts for the distance while kriging also account for the relative position of the observations. Kriging indeed "naturally" compensate for the effect of clustering, assigning more weight to the isolated points than to the points from a cluster. IDW does not, so you could have markedly different results if you have 2 coincident points or two "nearly coincident" points.– radouxjuCommented Mar 26, 2014 at 20:44
-
1for my last statement, what I tried to say is that you have different results if you take the average of the two coincident points (then considered as a single point if I understand your proposed implementation) compared with two nearly coincident points that are counted twice. I am not talking about discontinuties of the prediction near the points, but about the different global prediction that you could have depending on the decision to merge points within a given tolerance. With kriging this decision would have less consequences.– radouxjuCommented Mar 26, 2014 at 21:31
In addition to what radouxju said, I'd just add a couple links to useful things:
http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//00310000002m000000 http://www.ncgia.ucsb.edu/pubs/spherekit/inverse.html
If you're familiar with MATLAB, here's a method: http://www.mathworks.com/matlabcentral/fileexchange/24477-inverse-distance-weight
