<img src="https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/InterpolationStrip.png?raw=true"/>
# Fast Barnes Interpolation
This Python package provides an implementation of the formal algorithms for fast Barnes interpolation as presented in the corresponding [paper published in the GMD journal](https://gmd.copernicus.org/articles/16/1697/2023/gmd-16-1697-2023.pdf).
In addition to Barnes interpolation for 2-dimensional applications, this package now also supports Barnes interpolation of 1-dimensional and 3-dimensional data.
### Mathematical Background
Barnes interpolation is a method that is widely used in geospatial sciences like meteorology to remodel data values $f_k \in \mathbb{R}$ recorded at irregularly distributed points $\mathbf{x}_k \in \mathbb{R}^2$ into a representative analytical field $f(\mathbf{x}) \in \mathbb{R}$.
It is defined as
<img src="https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/BarnesInterpolDef.png?raw=true" width="196"/>
with Gaussian weights
<img src="https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/GaussianWeights.png?raw=true" width="186"/>
for a specific Gaussian width parameter $\sigma$.
Naive computation of Barnes interpolation leads to an algorithmic complexity of $\mathcal{O}(N \cdot W \cdot H)$, where $N$ is the number of sample points and $W \times H$ the size of the underlying grid.
As shown in the paper, for sufficiently large $n$ (in general in the range from 3 to 6) a good approximation of Barnes interpolation with a reduced complexity $\mathcal{O}(N + W \cdot H)$ can be obtained by the convolutional expression
<img src="https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/BarnesInterpolConvolExpr.png?raw=true" width="364"/>
where $\delta_{\mathbf{x}_k}$ is the Dirac impulse function at location $\mathbf{x}_k$ and $r_n(.)$ an elementary rectangular function of a specific length that depends on $\sigma$ and $n$.
### Example with a Speed-up Factor of more than 1000
The example below is taken from the paper and shows a comparison of the naive Barnes interpolation with the fast Barnes interpolation for $N = 3490$ sample points on a grid with $2400 \times 1200$ points.
The test was conducted on a computer with a customary 2.6 GHz Intel i7-6600U processor with two cores (of minor importance since the code is written in sequential manner).
The recorded execution times for the pure interpolation tasks were
- 280.764 s for the naive Barnes interpolation with a 3-fold nested for-loop over $W$, $H$ and $N$
- 0.247 s for the fast Barnes interpolation with a 4-fold convolution
The detail views of the isoline visualizations of the respective Barnes interpolation results agree to a very high degree:
<img src="https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/NaiveBarnesDetail.png?raw=true"> <img src="https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/ConvBarnesDetail.png?raw=true">
The first image depicts the isoline visualization for the naive approach, the second image that for the convolutional, fast approach.
### Further Links
- [Minimal Working Examples](https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/MinimalWorkingExamples_Doc.md)
To find out how to use the code.
- [Release Notes](https://github.com/MeteoSwiss/fast-barnes-py/blob/main/RELEASE-NOTES.md)
Summary of the recent changes.
Raw data
{
"_id": null,
"home_page": "https://github.com/MeteoSwiss/fast-barnes-py/",
"name": "fast-barnes-py",
"maintainer": null,
"docs_url": null,
"requires_python": "<3.13,>=3.9",
"maintainer_email": null,
"keywords": "python, interpolation, gridding, inverse distance weighting, fast algorithms, Gaussian, convolution",
"author": "Bruno Z\u00fcrcher",
"author_email": "bruno.zuercher@meteoswiss.ch",
"download_url": "https://files.pythonhosted.org/packages/6b/50/4838910ad1c27865d8d14ca9d6722135cecd491320ba9912889408b7b009/fast-barnes-py-2.0.0.tar.gz",
"platform": null,
"description": "<img src=\"https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/InterpolationStrip.png?raw=true\"/>\r\n\r\n# Fast Barnes Interpolation\r\n\r\nThis Python package provides an implementation of the formal algorithms for fast Barnes interpolation as presented in the corresponding [paper published in the GMD journal](https://gmd.copernicus.org/articles/16/1697/2023/gmd-16-1697-2023.pdf).\r\n\r\nIn addition to Barnes interpolation for 2-dimensional applications, this package now also supports Barnes interpolation of 1-dimensional and 3-dimensional data.\r\n\r\n \r\n\r\n### Mathematical Background\r\n\r\nBarnes interpolation is a method that is widely used in geospatial sciences like meteorology to remodel data values $f_k \\in \\mathbb{R}$ recorded at irregularly distributed points $\\mathbf{x}_k \\in \\mathbb{R}^2$ into a representative analytical field $f(\\mathbf{x}) \\in \\mathbb{R}$.\r\nIt is defined as\r\n\r\n<img src=\"https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/BarnesInterpolDef.png?raw=true\" width=\"196\"/>\r\n\r\nwith Gaussian weights\r\n\r\n<img src=\"https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/GaussianWeights.png?raw=true\" width=\"186\"/>\r\n\r\nfor a specific Gaussian width parameter $\\sigma$.\r\n\r\nNaive computation of Barnes interpolation leads to an algorithmic complexity of $\\mathcal{O}(N \\cdot W \\cdot H)$, where $N$ is the number of sample points and $W \\times H$ the size of the underlying grid. \r\nAs shown in the paper, for sufficiently large $n$ (in general in the range from 3 to 6) a good approximation of Barnes interpolation with a reduced complexity $\\mathcal{O}(N + W \\cdot H)$ can be obtained by the convolutional expression\r\n\r\n<img src=\"https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/BarnesInterpolConvolExpr.png?raw=true\" width=\"364\"/>\r\n\r\nwhere $\\delta_{\\mathbf{x}_k}$ is the Dirac impulse function at location $\\mathbf{x}_k$ and $r_n(.)$ an elementary rectangular function of a specific length that depends on $\\sigma$ and $n$.\r\n\r\n \r\n\r\n### Example with a Speed-up Factor of more than 1000\r\n\r\nThe example below is taken from the paper and shows a comparison of the naive Barnes interpolation with the fast Barnes interpolation for $N = 3490$ sample points on a grid with $2400 \\times 1200$ points.\r\nThe test was conducted on a computer with a customary 2.6 GHz Intel i7-6600U processor with two cores (of minor importance since the code is written in sequential manner).\r\n\r\nThe recorded execution times for the pure interpolation tasks were\r\n- 280.764 s for the naive Barnes interpolation with a 3-fold nested for-loop over $W$, $H$ and $N$\r\n- 0.247 s for the fast Barnes interpolation with a 4-fold convolution \r\n\r\nThe detail views of the isoline visualizations of the respective Barnes interpolation results agree to a very high degree:\r\n\r\n<img src=\"https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/NaiveBarnesDetail.png?raw=true\"> <img src=\"https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/images/ConvBarnesDetail.png?raw=true\">\r\n\r\nThe first image depicts the isoline visualization for the naive approach, the second image that for the convolutional, fast approach.\r\n\r\n \r\n\r\n### Further Links\r\n\r\n- [Minimal Working Examples](https://github.com/MeteoSwiss/fast-barnes-py/blob/main/doc/MinimalWorkingExamples_Doc.md) \r\nTo find out how to use the code.\r\n- [Release Notes](https://github.com/MeteoSwiss/fast-barnes-py/blob/main/RELEASE-NOTES.md) \r\nSummary of the recent changes.\r\n",
"bugtrack_url": null,
"license": "BSD 3-Clause License",
"summary": "Fast Barnes Interpolation",
"version": "2.0.0",
"project_urls": {
"Homepage": "https://github.com/MeteoSwiss/fast-barnes-py/"
},
"split_keywords": [
"python",
" interpolation",
" gridding",
" inverse distance weighting",
" fast algorithms",
" gaussian",
" convolution"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "858cf03af9394bc4730bfea67e5d42147b7fb892b10de76caf6c2298edfbf359",
"md5": "c34f38f6603ddbb76048cb7af7b11af0",
"sha256": "b5204f44bf33bf64a423c0ea5d514c6513dd0263c77aaff244a1754fa87f1111"
},
"downloads": -1,
"filename": "fast_barnes_py-2.0.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "c34f38f6603ddbb76048cb7af7b11af0",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": "<3.13,>=3.9",
"size": 19820,
"upload_time": "2024-12-06T11:46:54",
"upload_time_iso_8601": "2024-12-06T11:46:54.884128Z",
"url": "https://files.pythonhosted.org/packages/85/8c/f03af9394bc4730bfea67e5d42147b7fb892b10de76caf6c2298edfbf359/fast_barnes_py-2.0.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "6b504838910ad1c27865d8d14ca9d6722135cecd491320ba9912889408b7b009",
"md5": "ce16784bfc449af82248a94ea9c911ad",
"sha256": "c73afaabb93898af4918f765aa181a269b07a46c71d603be85dbe8102bafd99f"
},
"downloads": -1,
"filename": "fast-barnes-py-2.0.0.tar.gz",
"has_sig": false,
"md5_digest": "ce16784bfc449af82248a94ea9c911ad",
"packagetype": "sdist",
"python_version": "source",
"requires_python": "<3.13,>=3.9",
"size": 17551,
"upload_time": "2024-12-06T11:46:56",
"upload_time_iso_8601": "2024-12-06T11:46:56.671894Z",
"url": "https://files.pythonhosted.org/packages/6b/50/4838910ad1c27865d8d14ca9d6722135cecd491320ba9912889408b7b009/fast-barnes-py-2.0.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-12-06 11:46:56",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "MeteoSwiss",
"github_project": "fast-barnes-py",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"requirements": [
{
"name": "numpy",
"specs": []
},
{
"name": "scipy",
"specs": []
},
{
"name": "numba",
"specs": []
},
{
"name": "matplotlib",
"specs": []
},
{
"name": "basemap",
"specs": []
},
{
"name": "Pillow",
"specs": []
}
],
"lcname": "fast-barnes-py"
}
JSON
