"""
nearest.py
Nearest-neighbour HEALPix resampler built on top of KNeighborsResampler.
Strategy
--------
1. Run the standard KNN (Npt neighbours per source sample) — this gives
``hi (N, Npt)`` (cell indices per source) and ``d_m (N, Npt)`` (distances).
2. Compute Gaussian weights w[n,j] = exp(-2 d²/σ²).
3. For each HEALPix cell k, keep only the source n that maximises w → hi_k (K,).
This is a single ``scatter_reduce('amax')`` pass — O(N·Npt), no sparse matrix.
4. ``resample`` : hval[:, k] = val[:, hi_k[k]] (direct index)
``invert`` : val[:, n] = mean of hval[:, k] ∀k s.t. hi_k[k]==n (scatter-mean)
When ``out_cell_ids`` is provided
----------------------------------
``healpix_weighted_nearest`` already intersects the KNN result with ``out_cell_ids``,
but cells beyond ``ring_search_max`` rings may be absent. After the KNN step,
missing cells are filled from their nearest sample, found with a KD-tree.
"""
from __future__ import annotations
from typing import Optional
import healpix_geo
import numpy as np
import torch
from scipy.spatial import cKDTree
from healpix_resample.base import ResampleResults, T_Array
from healpix_resample.knn import KNeighborsResampler, _lonlat_to_xyz
# ─────────────────────────────────────────────────────────────────────────────
# Helper: scatter-mean
# ─────────────────────────────────────────────────────────────────────────────
def _scatter_mean(src: torch.Tensor, idx: torch.Tensor, T: int) -> torch.Tensor:
"""out[:, t] = mean of src[:, s] where idx[s] == t. Shape (B, S) → (B, T)."""
B = src.shape[0]
out = torch.zeros(B, T, device=src.device, dtype=src.dtype)
out.scatter_add_(1, idx.unsqueeze(0).expand(B, -1), src)
count = torch.bincount(idx, minlength=T).to(src.dtype).clamp(min=1)
out /= count.unsqueeze(0)
return out
# ─────────────────────────────────────────────────────────────────────────────
# NearestResampler
# ─────────────────────────────────────────────────────────────────────────────
[docs]
class NearestResampler(KNeighborsResampler):
"""Nearest-neighbour HEALPix resampler — no sparse matrices.
Uses ``Npt`` KNN neighbours (default 9) to robustly find the nearest source
for every HEALPix cell, even when the output grid is finer than the input.
Parameters
----------
Npt : int
Number of HEALPix neighbours per source sample used by the KNN.
Larger values cover more cells at the cost of more memory during
construction. Default 9 is a good trade-off for most use cases.
max_distance_m : float or None
Only used with ``out_cell_ids``. A requested cell that the KNN rings
did not reach is filled with its nearest sample only if that sample
lies within ``max_distance_m`` metres of the cell centre; otherwise
the cell is left out of the result, like the cells the interpolating
resamplers cannot compute. ``None`` (default) fills every requested
cell, however far its nearest sample is.
search : {"knn", "kdtree"}
How the nearest sample of each cell is found. ``"knn"`` (default):
through the ``Npt`` nearest cells of every sample (the KNN links of
``KNeighborsResampler``), the cells they miss from a KD-tree.
``"kdtree"`` (with ``out_cell_ids`` only): every requested cell takes
its nearest sample from a KD-tree of the samples, directly: the same
sample (the KNN path keeps, per cell, the linked sample of largest
Gaussian weight, i.e. the nearest), several times faster on dense
inputs, and no KNN links (``neighbours``) to search or keep. Samples
exactly as near as each other may be picked differently. On a CUDA
device (nested cells), the search runs on the GPU from HEALPix
buckets of the samples (``_nearest_source_buckets``): the
same samples as the KD-tree, ties apart.
``max_distance_m`` then applies to every requested cell (the KNN
path applies it only to the cells its rings did not reach).
All other parameters are forwarded to ``KNeighborsResampler``.
"""
[docs]
def __init__(self, *args, Npt: int = 9, max_distance_m: Optional[float] = None,
search: str = "knn", **kwargs):
if max_distance_m is not None and not max_distance_m > 0:
raise ValueError(f"max_distance_m must be None or positive, got {max_distance_m!r}.")
if search not in ("knn", "kdtree"):
raise ValueError(f"search must be 'knn' or 'kdtree', got {search!r}.")
self.max_distance_m = max_distance_m
if search == "kdtree":
self._init_kdtree(*args, Npt=Npt, **kwargs)
return
# Ensure ring_search_max >= ring_search_init(Npt) so the KNN search
# loop in healpix_weighted_nearest actually executes.
#
# healpix_weighted_nearest computes:
# r_min = ceil((sqrt(Npt) - 1) / 2)
# ring_search_init = max(1, r_min + 1)
#
# KNeighborsResampler default is ring_search_max=2, which is too small
# for Npt >= 16 (needs ring_search_init=3). We auto-correct here only
# when the caller has not supplied ring_search_max explicitly.
if "ring_search_max" not in kwargs:
import math as _math
r_min = int(_math.ceil((_math.sqrt(Npt) - 1.0) / 2.0))
ring_search_init_needed = max(1, r_min + 1)
# +2 margin so the loop has room to grow and find Npt candidates
kwargs["ring_search_max"] = ring_search_init_needed + 2
# super().__init__ calls self.comp_matrix() at the end — our override
# will be called there, building hi_k instead of sparse M/MT.
super().__init__(*args, Npt=Npt, **kwargs)
# If out_cell_ids was requested, fill any cells the KNN rings missed.
if self.out_cell_ids is not None:
self._fill_missing_out_cells()
# Geometry buffers only needed during construction — free them.
for attr in ("xyz_samples", "xyz_cells"):
if hasattr(self, attr):
delattr(self, attr)
if self.device.type == "cuda":
torch.cuda.empty_cache()
def _init_kdtree(self, *args, **kwargs) -> None:
"""``search="kdtree"``: the requested cells and the nearest sample of
each, from a KD-tree of the samples (no KNN links, no operator)."""
import inspect
bound = inspect.signature(KNeighborsResampler.__init__).bind(self, *args, **kwargs)
bound.apply_defaults()
a = bound.arguments
if a["out_cell_ids"] is None:
raise ValueError("search='kdtree' needs out_cell_ids (the cells to resample onto).")
self.level, self.Npt = int(a["level"]), int(a["Npt"])
self.nest, self.radius = bool(a["nest"]), float(a["radius"])
self.ellipsoid, self.dtype = str(a["ellipsoid"]), a["dtype"]
device = a["device"]
self.device = torch.device(device if device is not None else "cpu")
self.verbose, self.group_by = a["verbose"], False
self.out_cell_ids = a["out_cell_ids"]
self.threshold = float(a["threshold"])
self.neighbours = None
lon = torch.as_tensor(a["lon_deg"]).to(dtype=torch.float64).reshape(-1)
lat = torch.as_tensor(a["lat_deg"]).to(dtype=torch.float64).reshape(-1)
self.N = int(lon.numel())
out = torch.as_tensor(self.out_cell_ids).to(torch.long).reshape(-1)
cells = torch.unique(out) # ascending
if self.N == 0 or cells.numel() == 0:
self.cell_ids = cells[:0].to(self.device)
self.hi_k = torch.empty((0,), dtype=torch.long, device=self.device)
self.K = 0
return
hp = healpix_geo.nested if self.nest else healpix_geo.ring
lon_c, lat_c = hp.healpix_to_lonlat(cells.numpy().astype(np.uint64), self.level,
ellipsoid=self.ellipsoid)
xyz_cells = _lonlat_to_xyz(
torch.deg2rad(torch.as_tensor(np.asarray(lon_c), dtype=torch.float64)),
torch.deg2rad(torch.as_tensor(np.asarray(lat_c), dtype=torch.float64)),
)
xyz_samples = _lonlat_to_xyz(torch.deg2rad(lon), torch.deg2rad(lat))
if self.device.type == "cuda" and self.nest:
hi, dot = self._nearest_source_buckets(
cells, self.level, lon, lat, xyz_cells, xyz_samples,
ellipsoid=self.ellipsoid, device=self.device)
else:
hi, dot = self._nearest_source(xyz_cells, xyz_samples)
if self.max_distance_m is not None:
near = self.radius * torch.acos(dot.clamp(-1.0, 1.0)) <= self.max_distance_m
cells, hi = cells[near], hi[near]
self.cell_ids = cells.to(self.device)
self.hi_k = hi.to(self.device)
self.K = int(self.cell_ids.numel())
# ── comp_matrix: scatter_reduce instead of sparse M / MT ─────────────────
def comp_matrix(self) -> None:
"""Build hi_k (K,) — nearest source index per HEALPix cell.
Algorithm
---------
1. Compute Gaussian weights w[n,j] from the KNN distances d_m[n,j].
2. Flatten (N, Npt) → (N*Npt,) pairs (source_n, cell_k, weight).
3. scatter_reduce('amax') over cell_k → max weight per cell O(N·Npt).
4. Keep the winner per cell (deduplicate ties with stable sort).
Result: ``self.hi_k`` (K,) long — index into [0..N-1] for each cell.
"""
# w[n,j] = exp(-2 d²/σ²) ─ same formula as KNeighborsResampler
w = torch.exp(
(-2.0) * (self.d_m * self.d_m) / (self.sigma_m * self.sigma_m)
) # (N, Npt)
flat_hi = self.hi.reshape(-1) # (N*Npt,)
flat_w = w.reshape(-1) # (N*Npt,)
flat_n = (
torch.arange(self.N, device=self.device, dtype=torch.long)
.unsqueeze(1).expand(self.N, self.Npt).reshape(-1)
) # (N*Npt,)
del w
# Discard invalid links (hi == -1 means no cell was found)
valid = flat_hi >= 0
flat_hi_v = flat_hi[valid]
flat_w_v = flat_w[valid]
flat_n_v = flat_n[valid]
del flat_hi, flat_w, flat_n
# the links to the cells tied with a sample's Npt-th nearest one
if self.tie_rows.numel():
flat_hi_v = torch.cat([flat_hi_v, self.tie_hi])
flat_w_v = torch.cat([flat_w_v, torch.exp(
(-2.0) * (self.tie_d * self.tie_d) / (self.sigma_m * self.sigma_m))])
flat_n_v = torch.cat([flat_n_v, self.tie_rows])
# ── Max weight per cell ────────────────────────────────────────────
max_w = torch.full(
(self.K,), float("-inf"), device=self.device, dtype=flat_w_v.dtype
)
max_w.scatter_reduce_(
0, flat_hi_v, flat_w_v, reduce="amax", include_self=True
)
# ── Keep winner pairs (weight == max for their cell) ──────────────
is_winner = flat_w_v >= max_w[flat_hi_v]
del max_w, flat_w_v
win_cell = flat_hi_v[is_winner]
win_src = flat_n_v[is_winner]
del flat_hi_v, flat_n_v, is_winner
# ── Deduplicate ties: stable sort by cell, first occurrence wins ──
ord_w = torch.argsort(win_cell, stable=True)
win_cell = win_cell[ord_w]
win_src = win_src[ord_w]
del ord_w
is_first = torch.ones(len(win_cell), dtype=torch.bool, device=self.device)
is_first[1:] = win_cell[1:] != win_cell[:-1]
# ── Write result: hi_k[k] = nearest source index for cell k ───────
# -1 means no source reached the cell (shouldn't happen for cells that
# passed the threshold, but kept as a defensive sentinel).
hi_k = torch.full((self.K,), -1, dtype=torch.long, device=self.device)
hi_k[win_cell[is_first]] = win_src[is_first]
del win_cell, win_src, is_first
self.hi_k = hi_k # (K,)
# ── Fill cells from out_cell_ids missed by the KNN rings ─────────────────
def _fill_missing_out_cells(self) -> None:
"""Extend cell_ids / hi_k to cover every cell in out_cell_ids.
Cells in ``out_cell_ids`` not returned by ``healpix_weighted_nearest``
(i.e., beyond ``ring_search_max`` rings of any source) get their
nearest source from a KD-tree of ``self.xyz_samples``.
"""
out_t = self.out_cell_ids
if not isinstance(out_t, torch.Tensor):
out_t = torch.as_tensor(out_t)
out_t = out_t.to(device=self.device, dtype=torch.long).reshape(-1)
# ── Find missing cells ─────────────────────────────────────────────
cell_sorted, _ = torch.sort(self.cell_ids)
out_sorted, _ = torch.sort(out_t)
if self.K == 0:
# no requested cell passed the KNN threshold: all of them are missing
missing = out_sorted
else:
pos = torch.searchsorted(cell_sorted, out_sorted).clamp(0, self.K - 1)
present = cell_sorted[pos] == out_sorted
missing = out_sorted[~present] # (M,)
if missing.numel() == 0:
return
if self.N == 0:
# no sample to fill them from: they stay out of the result, like
# the cells the interpolating resamplers cannot compute (#79)
return
if self.verbose:
print(
f"[NearestResampler] {missing.numel():,} out_cell_ids not covered "
f"by KNN rings → nearest sample from a KD-tree"
)
# ── xyz of missing cell centres ────────────────────────────────────
miss_np = missing.cpu().numpy().astype(np.uint64)
if self.nest:
lon_c_deg, lat_c_deg = healpix_geo.nested.healpix_to_lonlat(
miss_np, self.level, ellipsoid=self.ellipsoid
)
else:
lon_c_deg, lat_c_deg = healpix_geo.ring.healpix_to_lonlat(
miss_np, self.level, ellipsoid=self.ellipsoid
)
src_dtype = self.xyz_samples.dtype
xyz_miss = _lonlat_to_xyz(
torch.deg2rad(torch.as_tensor(lon_c_deg, device=self.device, dtype=src_dtype)),
torch.deg2rad(torch.as_tensor(lat_c_deg, device=self.device, dtype=src_dtype)),
) # (M, 3)
# ── Nearest source per missing cell — chunked, O(chunk × N) memory ─
hi_miss, dot_miss = self._nearest_source(xyz_miss, self.xyz_samples) # (M,), (M,)
del xyz_miss
# ── Leave out the cells whose nearest sample is too far (#75) ─────
if self.max_distance_m is not None:
dist_miss = self.radius * torch.acos(dot_miss.clamp(-1.0, 1.0))
near = dist_miss <= self.max_distance_m
if self.verbose:
print(
f"[NearestResampler] {int((~near).sum()):,} of them left out: "
f"nearest sample farther than max_distance_m={self.max_distance_m:g} m"
)
missing, hi_miss = missing[near], hi_miss[near]
if missing.numel() == 0:
return
# ── Extend cell_ids and hi_k, then re-sort to match out_cell_ids ──
self.cell_ids = torch.cat([self.cell_ids, missing])
self.hi_k = torch.cat([self.hi_k, hi_miss])
self.K = int(self.cell_ids.numel())
order = torch.argsort(self.cell_ids)
self.cell_ids = self.cell_ids[order]
self.hi_k = self.hi_k[order]
@staticmethod
def _nearest_source(
xyz_query: torch.Tensor, # (Q, 3)
xyz_src: torch.Tensor, # (N, 3)
) -> tuple[torch.Tensor, torch.Tensor]:
"""Nearest source per query point, from a KD-tree of the sources.
Returns hi (Q,) — index of the nearest source for each query cell —
and the matching dot product (Q,), the cosine of the angular
distance. On the unit sphere the chord ``c`` grows with the angle, so
the nearest source by chord is the one of largest dot product, and
``dot = 1 - c**2 / 2``. O((N + Q) log N), where comparing every query
to every source took hours for a chunk with millions of cells and
samples (chunks at the edge of a satellite swath).
"""
src = xyz_src.detach().cpu().numpy().astype(np.float64)
query = xyz_query.detach().cpu().numpy().astype(np.float64)
chord, hi = cKDTree(src).query(query, k=1)
dot = 1.0 - 0.5 * chord * chord
return (
torch.as_tensor(hi, dtype=torch.long, device=xyz_src.device),
torch.as_tensor(dot, dtype=xyz_src.dtype, device=xyz_src.device),
)
@staticmethod
def _nearest_source_buckets(
cells: torch.Tensor, # (Q,) nested ids at ``level``, ascending
level: int,
lon_deg: torch.Tensor, # (N,) samples
lat_deg: torch.Tensor,
xyz_query: torch.Tensor, # (Q, 3) centres of ``cells``
xyz_src: torch.Tensor, # (N, 3)
*,
ellipsoid: str,
device: torch.device,
delta: int = 2,
batch: int = 1 << 18,
max_pairs: int = 1 << 24,
) -> tuple[torch.Tensor, torch.Tensor]:
""":meth:`_nearest_source` on ``device`` (a GPU), for nested cells.
The samples go into HEALPix buckets ``delta`` levels coarser than the
cells. Each cell compares the samples of its bucket and of the 8
around it, with the KD-tree's float64 squared chord
``(dx*dx + dy*dy) + dz*dz``, and keeps the nearest (the smallest sample
index among equal distances). Any sample outside these 9 buckets is
at least about one bucket width away; a cell whose nearest candidate
is not closer than 0.4 of the nominal bucket width (or that has no
candidate, e.g. outside the swath) takes its nearest sample from the
KD-tree instead. So the picks are the KD-tree's, ties apart.
A batch compares at most ``max_pairs`` candidate pairs (about 0.4 GB
of float64 differences for the default) and holds at least 1024
cells: when a bucket holds more samples than that allows (cells much
coarser than the samples), the whole search goes to the KD-tree.
Returns hi (Q,) and the dot product (Q,), on the CPU, like
:meth:`_nearest_source`.
"""
import math
dev = torch.device(device)
bl = level - delta
q_bucket = cells.to(dev, torch.long) >> (2 * delta)
s_bucket = torch.as_tensor(healpix_geo.nested.lonlat_to_healpix(
lon_deg.numpy(), lat_deg.numpy(), bl, ellipsoid=ellipsoid).astype(np.int64)).to(dev)
ub, q_inv = torch.unique(q_bucket, return_inverse=True)
nb = torch.as_tensor(healpix_geo.nested.kth_neighbourhood(
ub.cpu().numpy().astype(np.uint64), bl, 1).astype(np.int64)).to(dev) # (U, 9), -1 invalid
sb, order = torch.sort(s_bucket, stable=True)
start = torch.searchsorted(sb, nb.clamp(min=0))
count = torch.searchsorted(sb, nb.clamp(min=0), right=True) - start
count[nb < 0] = 0
del q_bucket, s_bucket, ub, nb, sb
mmax = int(count.max()) if count.numel() else 0
if 1024 * 9 * mmax > max_pairs:
# too many samples per bucket for a batch of 1024 cells
hi, dot = NearestResampler._nearest_source(xyz_query.cpu(), xyz_src.cpu())
return hi.cpu(), dot.cpu()
xq, xs = xyz_query.to(dev, torch.float64), xyz_src.to(dev, torch.float64)
Q = xq.shape[0]
hi = torch.full((Q,), -1, dtype=torch.long, device=dev)
best = torch.full((Q,), math.inf, dtype=torch.float64, device=dev)
if mmax:
# at most max_pairs candidate pairs per batch
batch = max(1024, min(batch, max_pairs // (9 * mmax)))
ar = torch.arange(mmax, device=dev)
none = torch.iinfo(torch.long).max
for b0 in range(0, Q, batch):
b1 = min(Q, b0 + batch)
u = q_inv[b0:b1]
pos = start[u][:, :, None] + ar # (B, 9, m)
ok = (ar < count[u][:, :, None]).reshape(b1 - b0, -1)
cand = order[pos.clamp(max=order.numel() - 1)].reshape(b1 - b0, -1)
d = xs[cand] - xq[b0:b1, None, :]
d2 = (d[..., 0] * d[..., 0] + d[..., 1] * d[..., 1]) + d[..., 2] * d[..., 2]
d2 = torch.where(ok, d2, torch.full_like(d2, math.inf))
m = d2.min(dim=1).values
pick = torch.where((d2 == m[:, None]) & ok, cand, torch.full_like(cand, none))
hi[b0:b1] = pick.min(dim=1).values
best[b0:b1] = m
chord = best.sqrt()
guard = 0.4 * math.sqrt(4 * math.pi / (12 * 4**bl))
unsure = ~(chord < guard)
hi, chord = hi.cpu(), chord.cpu()
if bool(unsure.any()):
uq = unsure.nonzero().reshape(-1).cpu()
c2, h2 = cKDTree(xyz_src.cpu().numpy().astype(np.float64)).query(
xyz_query[uq].cpu().numpy().astype(np.float64), k=1)
hi[uq] = torch.as_tensor(h2, dtype=torch.long)
chord[uq] = torch.as_tensor(c2, dtype=torch.float64)
dot = 1.0 - 0.5 * chord * chord
return hi, dot.to(xyz_src.dtype)
# ── resample ─────────────────────────────────────────────────────────────
@torch.no_grad()
def resample(self, val: T_Array, **_kwargs) -> ResampleResults:
"""Source samples → HEALPix cells.
hval[:, k] = val[:, hi_k[k]] — direct index, zero allocation overhead.
"""
y = val if isinstance(val, torch.Tensor) else torch.as_tensor(val)
y = y.to(self.device, dtype=self.dtype)
squeezed = y.ndim == 1
if squeezed:
y = y.unsqueeze(0) # (1, N)
# Clamp -1 sentinels (defensive; should not occur after _fill_missing)
safe_hi = self.hi_k.clamp(min=0)
hval = y[:, safe_hi] # (B, K)
cell_ids = self.cell_ids
if squeezed:
hval = hval.squeeze(0)
if not isinstance(val, torch.Tensor):
hval = hval.cpu().numpy()
cell_ids = cell_ids.cpu().numpy()
return ResampleResults(cell_data=hval, cell_ids=cell_ids)
# ── invert ───────────────────────────────────────────────────────────────
@torch.no_grad()
def invert(self, hval: T_Array) -> T_Array:
"""HEALPix cells → source samples.
val[:, n] = mean of hval[:, k] for all k s.t. hi_k[k] == n.
(scatter-mean; multiple cells can share the same nearest source)
"""
y = hval if isinstance(hval, torch.Tensor) else torch.as_tensor(hval)
y = y.to(self.device, dtype=self.dtype)
squeezed = y.ndim == 1
if squeezed:
y = y.unsqueeze(0) # (1, K)
safe_hi = self.hi_k.clamp(min=0)
res = _scatter_mean(y, safe_hi, self.N) # (B, N)
if squeezed:
res = res.squeeze(0)
if not isinstance(hval, torch.Tensor):
res = res.cpu().numpy()
return res