Skip to content

Add natural neighbor (Voronoi-based) interpolation #1153

@brendancol

Description

@brendancol

Motivation

The interpolation module currently has IDW, kriging, and spline, but is missing natural neighbor interpolation. This is one of gdal_grid's interpolation methods and is often preferred over IDW because it produces smoother surfaces without the "bullseye" artifacts that IDW tends to create around data points.

Proposed scope

  • Given scattered points (x, y, value), produce a gridded raster using Sibson's natural neighbor method.
  • The method works by constructing Voronoi diagrams: the interpolated value at a query point is a weighted average of nearby data points, where each weight is proportional to the area "stolen" from that point's Voronoi cell when the query point is inserted.
  • Should follow the same interface as the existing idw() and kriging() functions.

Implementation notes

The Voronoi computation is the expensive part. For the numpy path, scipy.spatial.Voronoi can be leveraged. The GPU path would need a custom Voronoi implementation or a different algorithmic approach.

Additional suggestion

Also worth considering: a simple moving-average gridding method (another gdal_grid mode) as a cheaper alternative for cases where the smoothness of natural neighbor isn't needed.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions