A fast high-precision geospatial grid interpolation algorithm
TL;DR
An interpolation framework that couples a Gaussian-weighted quadratic surface fitting kernel with KD-Tree neighbor search and CPU multithreading and achieves lower errors than three conventional methods.
Abstract
High-resolution geospatial grid generation requires interpolation methods that are accurate but still practical for large datasets. This paper presents an interpolation framework that couples a Gaussian-weighted quadratic surface fitting kernel with KD-Tree neighbor search and CPU multithreading. The fitting kernel is used to represent local non-linear variation, whereas the Gaussian weights reduce the influence of distant samples. To reduce the cost of repeated neighborhood queries and independent target-cell calculations, the implementation builds a shared KD-Tree index and assigns non-overlapping target-cell blocks to worker threads. In experiments using EGM2008 gravity anomaly data, the proposed framework achieved lower errors than three conventional methods (Moving Surface Fitting, Natural Neighbor Interpolation, and Spline Interpolation), with reductions in Mean Absolute Error (MAE) and Root Mean Square Error (RMSE) of up to 63.6% and 61.2%, respectively. The fitting-model evaluation produced a coefficient of determination (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R^2$$\end{document}) of 0.998611. The optimized implementation reduced the runtime from 240 s to 10 s while keeping the reported accuracy metrics unchanged. These results indicate that the proposed combination of local surface fitting, spatial indexing, and parallel execution is effective for the tested high-resolution grid interpolation task.