idw
v0.0.2
Published
Interpolation of irregular data in any number of dimensions using inverse distance weighting (IDW). The module offers flexibility through multiple modifiable components.
Downloads
230
Maintainers
Readme
idw is a JavaScript package for flexible interpolation of any-dimensional data using inverse distance weighting (IDW). It includes functionality for generating tileable noise functions.
This readme contains examples of use, an API reference and an attempt to explain how the package works.
Installation
The package is available on npm:
npm install idw
Examples of use
One-dimensional function:
In the one-dimensional case, the positions are specified as an array of numbers:
const { IDW } = require("idw");
const idw = new IDW({
positions: [0, 0.3, 0.6, 0.8, 1],
values: [2, 1.3, -0.3, -0.5, 2]
});
// Interpolate at 100 regularly spaced positions between 0 and 1
const x = Array(100).fill().map((_, i) => i / 99);
const values = x.map(p => idw.evaluate(p, 2));
console.log(values); // Outputs array of 100 values [v₁, v₂,...]
The second parameter in idw.evaluate
is the power used when computing the weights.
Here's a comparison using the setup above, with the value of the power above each plot and original data shown as red points:
Two-dimensional function
Now, the positions are represented as an array of arrays:
const data = {
positions: [
[0.1, 0.3],
[0.6, 0.5],
[0.2, 0.8],
[0.9, 0.1]
],
values: [0, 0.33, 0.67, 1]
}
Using the data above, we set up an IDW with tileable edges in the square [0, 1] × [0, 1]. It measures distance using the Manhattan/taxicab distance.
const { IDW } = require("idw");
const options = {
periodicExtent: [[0, 1], [0, 1]]
}
const idw = new IDW(data, options);
idw.useTaxicabDistance();
// Interpolate at 100 random positions
const positions = Array(100).fill().map(() => [Math.random(), Math.random()]);
const values = positions.map(p => idw.evaluate(p, 3));
console.log(values); // Outputs array of values [v1, v2,...]
Here's how the function looks on a 1000 × 1000 grid over [-0.5, 1.5] × [0, 1], with the positions indicated by their index in red:
The black square indiates periodicExtent
.
Three-dimensional function
For the three-dimensional example, we'll use the generateNoiseIDW
function to generate an IDW
object with 20 random positions and values.
The positions are sampled from [-1, 1] × [-1, 1] × [0, 1], and the function is tileable/periodic along the z-dimension.
The RNG is specified using a seed value of 1.
const { generateNoiseIDW } = require("idw");
let idw = generateNoiseIDW({
n: 20,
dimensions: 3,
extent: [[-1, 1], [-1, 1], [0, 1]],
periodic: [false, false, true]
}, 1);
// Interpolate at 100 random positions inside [-1, 1] × [-1, 1] × [0, 1]
const positions = Array(100).fill().map(() => [-1 + 2*Math.random(), -1 + 2*Math.random(), Math.random()]);
const values = positions.map(p => idw.evaluate(p, 5));
console.log(values); // Outputs array of values [v1, v2,...]
The animation below shows the noise function as the z-coordinate increases from 0 to 1. Since the function is periodic along the z-dimension, it leads to a perfect loop!
API
IDW class/prototype
Constructor
new IDW(data[, options])
- data :
- positions : The positions of the interpolation data. In the one-dimensional case, this is an array of values (
[x₁, x₂,...]
). Otherwise, it's an an array of arrays ([[x₁, y₁,...], [x₂, y₂,...], ...]
). Required. - values : An array of values, in the same order as the associated positions. Required.
- positions : The positions of the interpolation data. In the one-dimensional case, this is an array of values (
- options :
- periodicExtent : Specifies the extent of periodicity, if tileability is desired. Expected to be an object mapping dimension to extent, e.g.
{ 0: [-1, 1], 1: [0, 1] }
for the rectangle [-1, 1] × [0, 1]. Defaults to undefined. (Explanation) - innerDistFunction : The "inner distance function" used when computing the distance between two positions. (Explanation)
- outerDistFunction : The "outer distance function" used when computing the distance between two positions. (Explanation)
- weightFunction : Function that transforms the values of the weights before computing the weighted average. Expected input is a number between 0 and 1. (Explanation)
- denominatorOffset : Constant that is added to the denominator when computing the weights (
w = 1/(distanceᵖ + denominatorOffset)
). Defaults to 0.
- periodicExtent : Specifies the extent of periodicity, if tileability is desired. Expected to be an object mapping dimension to extent, e.g.
const { IDW } = require("idw");
const idw = new IDW({
positions: [0, 0.25, 0.5, 0.75, 1],
values: [0.1, 0.2, 0.3, 0.4, 0.5]
});
const data = {
positions: [
[0, 0.4],
[0.5, 0.2],
[0.3, 0.9],
],
values: [-0.5, 1.3, 0.4]
}
const options = {
periodicExtent: { 0: [0, 1] }, // Tileable only along x-axis
innerDistFunction: d => Math.exp(d*d) - 1,
outerDistFunction: arr => Math.log(IDW.sum(arr) + 1),
weightFunction: w => (1 + Math.sin(4*Math.PI*w)) / 2
}
const idw = new IDW(data, options);
idw.evaluate(position, power = 2)
Computes the interpolated value at a specified position.
position
is either a number (1D) or an array of same dimension as the elements of positions
in the input data (>=2D).
power
is the power parameter.
// 1D: Interpolates value at 0.6
const value = idw.evaluate(0.6);
// 2D: Interpolates value at [0.2, 0.5], using p = 3
const value = idw.evaluate([0.2, 0.5], 3);
idw.setDistanceFunctions(innerDistFunction, outerDistFunction)
Sets the innerDistFunction
and outerDistFunction
parameters that determine a custom distance function (see explanation).
// Example: Euclidean distance
idw.setDistanceFunctions((d, i) => d*d, arr => Math.sqrt(IDW.sum(arr));
idw.useEuclideanDistance()
Sets distance functions to compute distance using Euclidean distance. This is the default setup.
idw.useEuclideanDistance();
idw.useTaxicabDistance()
Sets distance functions to compute distance using taxicab/Manhattan distance.
idw.useTaxicabDistance();
idw.useChessboardDistance()
Sets distance functions to compute distance using chessboard/Chebyshev distance.
idw.useChessboardDistance();
idw.useMinkowskiDistance(p)
Sets distance functions to compute distance using Minkowski distance.
p
is the power parameter.
// Equivalent to taxicab distance
idw.useMinkowskiDistance(1);
idw.setWeightFunction(weightFunction)
Sets the weightFunction
parameter (see explanation).
idw.setWeightFunction(w => w*w);
idw.setDenominatorOffset(denominatorOffset)
Sets the denominatorOffset
parameter, a constant that is added to the denominator when computing weights.
idw.setDenominatorOffset(1e-5);
idw.setPeriodicSmoothing(smoothing)
Using a periodic extent can sometimes lead to strange artifacts in the interpolation function, which can be mitigated by smoothing the distance function.
This method sets the amount of smoothing to use.
smoothing
must be between 0 and 1, the default value is 0.1.
idw.setPeriodicSmoothing(0.2);
idw.getData()
Returns the data (object containing positions
and values
) that was passed to the constructor.
const { positions, values } = idw.getData();
generateNoiseIDW(options[, rng])
Generates and returns a noise function by creating an IDW object with randomly generated positions and values.
- options :
- n : The number of random positions and values to generate for the IDW object, cannot be less than 2. Required.
- dimensions : The dimensionality of the noise function, must be an integer not less than 1. Required.
- minValue : The minimum value for the randomly generated values. Defaults to 0.
- maxValue : The maximum value for the randomly generated values. Defaults to 1.
- valueFunction : Optional function that determines the values based on the generated positions. Defaults to undefined.
- extent : The extent from which to sample the positions. Defaults to "volume" bounded between -1 and 1 along each axis (e.g. the square [-1, 1] × [-1, 1] when
dimensions = 2
) - periodic : Specifies whether the noise function should be periodic/tileable, either a single boolean or an array of booleans with one value per dimension. Defaults to false.
- rng : The random number generator to use. The RNG is responsible for generating the random positions. If
valueFunction
is not specified, it will generate the random values as well. Either an RNG function, or an integer seed value. Defaults toMath.random
.
By default, the random values are guaranteed to have minimum and maximum values equal to minValue
and maxValue
, respectively.
If valueFunction
is specified, the values for minValue
and maxValue
are ignored.
const { generateNoiseIDW } = require("idw");
const idw = generateNoiseIDW({
n: 10,
dimensions: 2,
minValue: -1,
maxValue: 1,
extent: [[-1, 1], [-2, 2]]
}, 123);
console.log(idw.getData()); // The random positions and values generated for the IDW
console.log(idw.evaluate([0, 0])); // Get interpolated value at [0, 0]
const idw = generateNoiseIDW({
n: 5,
dimensions: 3,
valueFunction: p => p[0] + p[1] + p[2] // Value is determined by sum of coordinates
}, 123);
console.log(idw.evaluate([-0.3, 0.5, 0])); // Get interpolated value at [-0.3, 0.5, 0]
How (nearly) everything works
Inverse distance weighting is a method for interpolating data consisting of pairs of positions and values. It interpolates by computing a weighted average of the supplied values, placing a higher amount of weight on those near the position of interest.
Consider, for example, the data consisting of two-dimensional positions p₁ = [0, 0]
and p₂ = [1, 1]
with corresponding values v₁ = 0
and v₂ = 1
, and let p = [0.25, 0.4]
be the position that we want to interpolate.
The distances are d₁ = distance(p, p1) = √((0 - 0.25)² + (0 - 0.4)²) = 0.472
and d₂ = distance(p, p2) = 0.960
, leading to weights w₁ = 1 / d₁ = 2.112
and w₂ = 1 / d₂ = 1.041
.
The interpolated value is then the weighted average v = (w₁*v₁ + w₂*v₂) / (w₁ + w₂) = 0.330
.
The power parameter
In practice, the weights are usually computed as w = 1 / dᵖ
, where the parameter p
is a positive number.
The 1D example compares interpolation with different values for p
, and gives some useful intuition.
Using a small value leads to a function that has spikes at the data positions.
As it increases, the function becomes smoother, and eventually flattens out to nearest-neighbor interpolation.
In idw
, the parameter p
is specified in the evaluate
method (see the API description).
Predefined distance functions
The example above measures the distance using the Euclidean distance (i.e. the length of the straight line connecting the positions):
distance([x₁, y₁,...], [x₂, y₂,...]) = √((x₂ - x₁)² + (y₂ - y₁)² + ...)
where ...
indicates additional coordinates in three or more dimensions.
In addition to this, idw
offers three predefined distance functions:
Taxicab/Manhattan distance (useTaxicabDistance()
):
distance([x₁, y₁,...], [x₂, y₂,...]) = |x₂ - x₁| + |y₂ - y₁| + ...
Chebyshev/chessboard distance (useChessboardDistance()
):
distance([x₁, y₁,...], [x₂, y₂,...]) = max(|x₂ - x₁|, |y₂ - y₁|,...)
Minkowski distance (useMinkowskiDistance(p)
):
distance([x₁, y₁,...], [x₂, y₂,...]) = ((x₂ - x₁)ᵖ + (y₂ - y₁)ᵖ + ...)¹ᐟᵖ
Euclidean distance is the default.
Custom distance functions
idw
also allows the user to define their own distance functions through the innerDistFunction
and outerDistFunction
parameters.
To understand how this works, first notice that every distance function above can be expressed as
distance([x₁, y₁,...], [x₂, y₂,...]) = outerDistFunction([innerDistFunction(x2 - x1), innerDistFunction(y2 - y1),...])
.
Euclidean distance, for example, is
innerDistFunction = d => d*d
outerDistFunction = arr => Math.sqrt(IDW.sum(arr))
where the function IDW.sum
takes in an array and computes the sum of its elements.
In addition to the coordinate difference, innerDistFunction
is also passed the coordinate index (0 for x, 1 for y and so on).
This makes it possible to create complex distance functions:
innerDistFunction = (d, i) => i === 0 ? d*d : Math.abs(d);
Specifying custom values for innerDistFunction
and outerDistFunction
can lead to very interesting and unpredictable results.
Tileable functions
The optional parameter periodicExtent
can be used to create tileable interpolation functions.
The image below demonstrates the situation where periodicExtent = [[0, 2], [0, 1]]
.
In this case, the rectangle "wraps around", so that the opposite edges are connected, or "glued together".
To better understand how this affects the function, let's compute the distance between the cyan ([0.2, 0.1]
) and pink ([1.8, 0.8]
) points.
As always, there's the length of the straight line connecting the points, indicated by a solid blue line.
Its length is √((1.8 - 0.2)² + (0.8 - 0.1)²) = 1.75
.
However, there's a second straight path connecting the points: moving along the solid brown line, which first crosses the right edge over to the left side, and then from the top to the bottom.
The distance travelled along this path is √((0.2 + 0.2)² + (0.2 + 0.1)²) = 0.5
, which is also the distance between the points.
When a function has a periodicExtent
specified, it becomes tileable, meaning that it repeats smoothly across the boundaries.
The two-dimensional example demonstrates this.
Note: It's possible to create functions that are tileable along some boundaries, but not others (see the API documentation).
When tileable interpolation functions are evaluated outside periodicExtent
, the value at the equivalent position inside periodicExtent
is returned.
In the example above, the position [2.1, 1.2]
is equivalent to [0.1, 0.2]
.
Weight function
The weightFunction
parameter gives the user another way to modify the behavior of the interpolation function, by transforming the values of the weights before the weighted average is computed.
With data consisting of position-value pairs (pᵢ, vᵢ)
, the following steps are performed internally:
- Compute the weight values:
wᵢ = 1 / distance(pᵢ, position)ᵖ
- Compute the sum of the weights, and divide each weight by the sum:
wᵢ = wᵢ / sum
- Apply weight function to weights:
wᵢ = weightFunction(wᵢ)
- Compute and return weighted average of values:
(w₁*v₁ + w₂*v₂ + ...) / (w₁ + w₂ + ...)
As long as the initial weight values are positive, the inputs to the weight function will always be between 0 and 1.