Connectivity

AbstractImageConvention

How a ball query treats a periodic direction: NearestImage or AllImages.

Singleton types, like a stencil. The traversal branches on this per candidate; as a type the branch and the coordinate expression behind it resolve at compile time, and the walk allocates nothing.

AbstractReach

Which of the cells within ball a query returns: Unrestricted, every one of them, or Connected, those reachable from the seed without leaving the ball.

A type, like AbstractImageConvention. The two are different sets computed by different algorithms, so the choice is visible in the call and fixed at compile time.

AllImages()

Visit every image of a cell that lands inside the ball, each carrying its own displacement — the set a periodic convolution sums over. See fold_within.

CSRConnectivity{VN,VP}

Sparse neighbor list: node i owns nbrs[ptr[i]:ptr[i+1]-1]. The two buffers are typed independently, and their element type is any Integer, so a large mesh can hold Int32 indices (half the memory and bandwidth of Int64, and the width GPU kernels want).

Connected()
Connected(stencil)

The cells within ball reachable from the seed through cells that are themselves within ball and active: the connected component of the ball that contains the seed. A graph query — it expands along adjacency and prunes at the ball's edge — so it is a subset of Unrestricted. The two agree whenever the ball is connected under the adjacency, which a maskless Cartesian StructuredGrid always is: each index step moves monotonically in one coordinate, so a staircase path to a cell never leaves that cell's own distance. Connected is strictly smaller wherever a mask or a boundary separates two parts of the ball.

Adjacency has to be named, since only a node set carries its own: with no argument, direction-1 adjacency (Stencils.Axial(1)) on the index-space architectures and the stored neighbour lists on an UnstructuredGrid. Connected(stencil) sets it explicitly for the former, and is an error for the latter, which has no index space for a stencil to mean anything in.

This is not a cheaper way to compute Unrestricted. Take cells P (the seed), Q and R, adjacent only as P–Q–R, with d(P,Q) = 1.2r and d(P,R) = 0.8r. A walk outward from P that drops any cell farther than r stops at Q and never reaches R, though R is inside the ball. Such a walk computes Connected; the ball is a different set, reached only by a spatial query.

ConnectedScratch{T}

The buffers a Connected query needs: the ball's cells and their distances, the visited flags, the breadth-first order, the queue, and the candidate buffer the ball pass itself takes.

One per task, exactly as ball_scratch is — every buffer is written per query, so two tasks cannot share a set. Build one with connected_scratch and pass it as scratch. A query given no scratch borrows one from a per-task pool for its duration and returns it, so repeated queries on one task allocate once; naming your own pins the buffers to a lifetime you control.

FormulaNeighborSeq{GR,K}

Lazy neighbour sequence of one cell of a layout whose adjacency is arithmetic.

Holds the tuple Grids.formula_neighbors returned, so iterating it touches no heap: the counterpart of StencilNeighbors and MeshNeighbors for the third kind of adjacency.

IndexTopology(size, periodic, mask)
IndexTopology(grid)

Extent, wrapping and activity per dimension — the whole of what a neighbor computation reads. Coordinates, cell measure and geometry never enter one, so a sampling hands this over directly, with no grid (axes, dense measure, full mask) built to be read once and dropped. A curvilinear grid is the N = 2 case of the same algorithm.

mask === nothing means every cell is active, and costs no storage and no load.

MeshNeighbors{GR}

Lazy neighbour sequence of one node of a stored-incidence layout: iterating it walks the node's CSR block and yields each active neighbour.

The counterpart of StencilNeighbors: a traversal over every node allocates nothing.

MetricTopology(grid; index = nothing)

What a distance query reads that depends on the grid alone: the tightest per-direction step bound, which sizes the search window, the coordinate span, and a spatial index where the layout has no separable axes to bound with. IndexTopology is its counterpart for a stencil query.

Constructing one is O(1) on a rectilinear grid, so passing topology to a query is optional. The index is worth hoisting: building a k-d tree for a single query costs more than the scan it replaces, so it is left out by default. foreach_within and mapreduce_within hoist one for a sweep, and indexed builds one explicitly.

Grid types are immutable and the Adapt extension reconstructs them field by field for a device, so this is a separate value and never a cache field on the grid.

NearestImage()

Visit each cell at most once, at its nearest image. The neighbour-set convention, and the default.

StencilNeighbors{G,N,S}

Lazy neighbor sequence of one cell of an index-topology grid: iterating it walks the stencil offsets and yields the linear index of each in-range, active neighbor.

Nothing is stored, so a traversal that visits every cell allocates nothing at all. Use neighbors! to write into a caller-supplied buffer, or collect this to materialize it.

Unrestricted()

Every cell whose centre lies within ball. The default, and a purely spatial query: with a spatial index it costs O(log n + m) and never consults adjacency.

Note that the result is a ball, not a connected patch — with a mask, or a concave domain, it can contain cells that are near the seed in space but reachable from it only by leaving the ball.

_buffered_candidates(index) -> Bool

Whether an index has to materialize a candidate list to be queried.

A cell list folds its bins directly and a bare scan has nothing to buffer, so both answer a query with no per-task storage, and a sweep over them runs per index, on a device included. A tree deduplicates the periodic images it searches over, so it needs a buffer, and its sweep needs chunks to give each task one.

_csr_from_candidates(emit!, n, maxdeg) -> CSRConnectivity

Build CSR for n nodes whose degree is bounded by maxdeg. emit!(buf, lo, i) writes node i's candidate neighbors into buf[lo+1 : lo+maxdeg] and returns how many it wrote; duplicates, self and out-of-range entries are removed here. emit! must touch only its own slice, and it is called twice per node — once to count the row, once to fill it — so it must be a pure function of i.

Count, scan, fill. The scratch is one maxdeg buffer per task, and both node passes write only slots their own node owns, so both parallelize under a threaded backend.

Host backends only: a work-item-per-node form needs maxdeg slots per item, an n · maxdeg scratch, and a device backend raises here. The grid layouts reach the same graph through build_connectivity on Grids.FormulaNeighbors, which is device-resident end to end.

_csr_from_undirected_edges(nnodes, edges) -> CSRConnectivity

Build CSR from an undirected edge list, by counting degrees first and then filling each node's slot range directly — no intermediate per-node vectors, and no reallocation while filling.

_csr_total(deg, n, backend) -> Int

The CSR's edge count, sum(deg), reduced wherever the counting pass ran.

A builder takes _index_type(max(n + 1, total)) from it and calls its filling pass through a branch that fixes the type at each call site. Vector{I} for an I the compiler cannot see is a dynamic call whose buffers are typed abstractly for the whole of that pass.

Exact face-neighbor under offset (di,dj) for the gnomonic cubed sphere matching SphericalSampling._cubed_face_to_xyz / cubed_sphere_points!.

Panel interiors stay on-face. Crossing an edge uses cube face adjacency with index maps derived by matching cube XYZ along shared edges. Diagonal (corner) exits return (0,0,0) — no unique adjacent face.

_fold_healpix_neighbors(f, acc, nside, ipix0) -> acc

Thread acc = f(acc, ipix) over the RING-scheme topological neighbours of 0-based pixel ipix0, in the order SW, W, NW, N, NE, E, SE, S, skipping the ones that do not exist at the eight singular pixels.

The walk itself, so the buffer form and the tuple form share one copy of the arithmetic. The accumulator is threaded as a value, so the tuple form builds its result on the stack.

_ico_neighbor_ids(id, ν) -> (NTuple{6,Int}, n)

A geodesic vertex's neighbours: the six barycentric lattice steps, taken on every face the vertex sits on and resolved back to global ids.

A vertex on a macro-edge or at a corner sits on several faces, and the steps along a shared edge land on the same vertex from each of them, so the duplicates are dropped. What survives is five neighbours at a corner and six everywhere else.

Arithmetic in (id, ν) alone, so the grid layout and the sampling's own build_connectivity read the same adjacency from it.

_icosahedral_dual_areas(geometry, verts, triangles, nvert) -> Vector

Exact spherical-Voronoi dual-cell areas from the mesh's own triangulation — no convex hull, no optional dependency.

Each triangle is divided among its three vertices by the three arcs from its circumcenter O to its edge midpoints. Those arcs are the perpendicular bisectors of the edges — O is equidistant from all three vertices and each midpoint is equidistant from its two — so vertex a's share is the spherical quadrilateral (a, M_ab, O, M_ca), exactly its Voronoi cell restricted to that triangle. The three shares tile the triangle, so accumulating over all 20ν² triangles tiles the sphere and the areas sum to 4πR² identically. Ordering the cells' corners is never needed, so there is no per-vertex sortperm and no incident-triangle list.

_index_type(m) -> Type{<:Integer}

The narrowest integer that holds values up to m: Int32 for anything under two billion.

A builder passes the larger of the node count and the edge count, so a single width serves both buffers — nbrs holds node ids, ptr holds offsets into nbrs. At one width the two arrays go straight to a SparseMatrixCSC, which declares one index type for both.

Halves the CSR's memory and the bandwidth every traversal of it costs, and is the width a device kernel wants.

_sort_ball!(idxs, ds, lo, hi) -> nothing

Sort the ball by linear index, carrying each cell's distance with it.

Membership is then a binary search: the walk tests it once per (cell, neighbour) pair, and searchsortedfirst over a sorted Vector{Int} beats hashing at these sizes and allocates no dictionary per query.

Both arrays move together in place, so there is no permutation vector; sortperm plus two permute! is three allocations. Quicksort with a median-of-three pivot, recursing on the smaller side so the depth stays O(log m), and insertion sort for a short span.

_sort_unique_filter!(buf, lo, m, self, n) -> Int

Sort buf[lo+1 : lo+m] in place, drop duplicates, self-references, and out-of-range indices, and return the surviving count (left packed at the front of the slice).

_stencil_closed(t, stencil, I) -> Bool

Whether cell I is active and every offset from it lands in range on an active cell — the one question both interior and boundary_cells ask, so they cannot answer it differently.

The offset walk is unrolled at compile time through Stencils.fold_offsets

adjacency_matrix!(A, conn) -> A
adjacency_matrix!(A, grid; stencil=Axial(1), active_only=true) -> A

Fill preallocated N×N A. Grid overload uses the stencil directly (no CSR alloc).

adjacency_matrix(grid_or_conn; kwargs...) -> Matrix{Bool}

Dense n × n adjacency over the n nodes.

This allocates n² bytes, which is quadratic in the node count and therefore quartic in the side of a 2-D grid: a 1000×1000 grid has 10⁶ nodes and so needs ~10¹² bytes. Dense adjacency is for small node counts and for testing. For anything else use sparse_adjacency_matrix, which stores nedges entries, or neighbors!, which answers neighbour queries from the index stencil with no graph storage at all.

ball_scratch() -> Vector{Int}

A candidate buffer to hand to repeated ball queries through their scratch argument. One buffer per task; an indexed query then holds one allocation across any number of calls.

boundary_cells(grid; stencil = Stencils.Axial(1), backend = nothing) -> Array{Bool}

The active cells interior excludes: those touching an edge or a masked-out neighbour.

One pass and one array: a cell is a boundary cell exactly when it is active and its stencil is not closed, the same predicate interior reads.

build_connectivity(grid; stencil=Axial(1), active_only=true) -> CSRConnectivity

Materialize CSR adjacency.

Which builder runs is Grids.adjacency_source, the trait the per-cell neighbour queries resolve through, so a layout gets this by declaring how its adjacency is defined and nothing else: Grids.IndexStencilNeighbors ranges the stencil over an index space, Grids.FormulaNeighbors evaluates the arithmetic per cell, and Grids.StoredMeshNeighbors wraps the mesh's own buffers. stencil selects among the offsets of the first, which is the one whose adjacency is a stencil shape.

For adjacency by physical distance, see build_connectivity_within.

build_connectivity(grid; active_only = true) -> CSRConnectivity

The adjacency of a layout whose neighbours are arithmetic, materialized.

Count, scan, fill — the same three passes the index-stencil builder makes, and for the same reason: both cell passes write only slots their own cell owns, so they carry no running offset and need no coordination. The adjacency is a per-cell formula, so the whole shape it takes is that formula's.

A formula fixes the neighbour set, so stencil selects nothing here. The generic entry point resolves Grids.adjacency_source and forwards one keyword set to whichever builder it lands on, so this one absorbs the keywords that shape the others, as Grids.StoredMeshNeighbors does.

build_connectivity(sampling, nlat; nlon, mask, periodic, stencil, active_only)

Sampling topology straight to CSR. A tensor-product sampling's neighbor graph is fixed by its axis lengths and longitude wrapping alone, so the axes themselves are never evaluated — for Gauss–Legendre that is an O(n²) root solve.

build_connectivity(::CubedSphereSampling, n; stencil=Axial(1)) -> CSRConnectivity

Six-panel gnomonic cubed sphere with cross-face seams. Indexing matches SphericalSampling.cubed_sphere_points!.

build_connectivity(s::HEALPixSampling) -> CSRConnectivity

HEALPix RING topological adjacency (usually 8 neighbors; 7 or 6 at singular pixels). Julia node indices are 1-based (pixel 0 → node 1).

build_connectivity(s::IcosahedralSampling) -> CSRConnectivity

Undirected edges of the frequency-ν geodesic triangulation (same vertex set as SphericalSampling.icosahedral_vertices).

A vertex's neighbours are arithmetic in (ν, id) — see _ico_neighbor_ids — so this is the same count, scan, fill the layout's own builder makes, over 10ν² + 2 vertices. The triangulation's 20ν² triangles and 30ν² edges are never formed.

build_connectivity(::YinYangSampling, nlon, nlat; stencil=Axial(1)) -> CSRConnectivity

Panel-local face/vertex stencils on yin then yang. Global ordering matches SphericalSampling.spherical_points! for Yin–Yang: yin (nlon×nlat, lon fastest), then yang with the same panel indexing. The overlap is not cross-linked: this is the standard Yin–Yang discrete topology, where the panels couple through interpolation.

build_connectivity_within(grid; ball, active_only=true) -> CSRConnectivity

Materialize the CSR adjacency of every pair of cells within ball of each other — the bulk form of neighbors_within, row k holding exactly what the per-cell query returns for cell k.

Symmetric by construction, since the metric is.

Where a separable window can bound the candidates the default topology needs no index; elsewhere it carries a cell list, built once and amortized over the n rows, so a row costs O(log n + m). Pass topology = MetricTopology(grid) for the scanning build, or an indexed topology for the k-d tree.

Rows are balls, i.e. Unrestricted, and there is no Connected form: reachability within one cell's ball is asymmetric — a bridge cell can lie in one cell's ball while that cell lies outside its own — so such a graph is not an adjacency.

For a mesh-degree radius

The result is ∑ᵢ degree(i) integers, and a ball's degree grows with the cube (or square) of its radius. At a radius of a few cell widths that is mesh-degree adjacency, built once and read row by row many times. At a radius of tens of widths the degree reaches 10³–10⁴, and on a million cells the graph is 10⁹–10¹⁰ integers: tens of gigabytes.

Ask neighbors_within!, fold_within or mapreduce_within instead. Those go through the same index and visit the same cells, one row at a time, and never hold more than one row.

connected_components(grid; stencil = Stencils.Axial(1), active = true) -> (labels, ncomponents)

Label the connected components of the active region (or of the inactive region with active = false), by flood fill honouring the grid's own wrapping. labels is 0 off the region and 1:ncomponents on it.

There is no backend: a fill's next cell is decided by the cells already labelled, so the traversal is sequential. interior and boundary_cells are the per-cell questions, and both take one.

connected_scratch([T = Float64]) -> ConnectedScratch{T}

Buffers for a Connected query, so a caller making many of them allocates none. T is the grid's coordinate type, which its distances are reported in.

The buffers grow to the largest ball seen and are reused, so the first query on a new size is the only one that allocates.

count_holes(grid; stencil = Stencils.Axial(1)) -> Int

How many connected inactive regions are fully enclosed by active cells — the number of holes in the active region, and so an estimate of its first Betti number.

A region that reaches a non-wrapping edge counts as outside. Along a wrapping direction there is no edge to reach, so enclosure there is decided by the fill alone.

csr_connectivity(nbrs, ptr; validate=true) -> CSRConnectivity

Wrap CSR buffers. validate=false skips O(nnz) checks (internal / trusted data).

empty_csr(nnodes, [I=Int]) -> CSRConnectivity

Adjacency in which every node has no neighbors, with I-typed indices.

fold_at(f, init, grid, p; ball, active_only=true, topology, scratch) -> acc

Fold acc = f(acc, J, d) over every cell J within ball of the point p, d being its distance. p is a coordinate in the grid's own coordinates, written any way a point is accepted elsewhere; fold_within is this at a cell centre.

There is no cell to exclude, so unlike the cell-seeded form every cell within ball is visited.

fold_within(f, init, grid, I...; ball, images=NearestImage(), self=false, active_only=true)

Fold acc = f(acc, J, d) over every cell J within ball of cell I, d being its distance. The traversal every distance query here is built on; the accumulator is threaded through as a value, so nothing is captured and nothing is boxed.

images selects how a periodic direction is treated — NearestImage (the default, each cell once, the convention neighbors_within! exposes) or AllImages, which visits every image of a cell that lands inside the ball, each carrying its own displacement.

AllImages is what a periodic convolution needs: on a torus of period L, f̄(x) = Σₖ ∫ K(x − y − kL) f(y) dy, so where the kernel support exceeds L/2 one cell contributes through several images at different displacements, and keeping only the nearest drops the rest. Below L/2 the two conventions coincide exactly. It also widens the search: the window becomes the uncapped ceil(r/s) per periodic direction, in place of metric_window's one-turn cap. It raises where a periodic direction is an angular identification.

self = true also folds the centre cell, at distance zero. The default excludes it, matching a neighbour set; a convolution needs it, and it carries the kernel's largest weight.

reach selects the ball (Unrestricted) or the part of it reachable from the seed without leaving it (Connected); topology and scratch are as in neighbors_within!.

foreach_within(f, grid; ball, …) -> nothing

Call f(I, J, d) for every cell I of grid and every cell J within ball of it. The same hoisting as mapreduce_within, for an f that writes.

Under a threaded backend, f runs on disjoint spans of cells concurrently, so what it writes has to be determined by I — the same contract the connectivity builders keep.

healpix_neighbor_ids(nside, ipix0) -> (NTuple{8,Int}, n)

healpix_neighbors! into a stack tuple: the n neighbours in the first n entries, still 0-based. Nothing is allocated, so a traversal over every pixel holds no buffer.

healpix_neighbors!(out, nside, ipix0) -> n_written

RING-scheme topological neighbors of 0-based pixel ipix0. Writes up to 8 0-based neighbor indices into out, skipping the neighbors that do not exist at the eight singular pixels. Order: SW, W, NW, N, NE, E, SE, S.

indexed(grid) -> MetricTopology

A MetricTopology carrying a spatial index, which brings a ball query to O(log n + m).

Requires NearestNeighbors — Grids.spatial_index raises when it is not loaded. An unindexed topology answers the same queries in O(n).

interior(grid; stencil = Stencils.Axial(1), backend = nothing) -> Array{Bool}

Which active cells have their whole stencil active and in range. false at a domain edge that does not wrap, and beside any masked-out cell.

Each cell's answer depends on its own neighbourhood alone, so backend runs the cells concurrently.

is_symmetric_adjacency(conn) -> Bool

Whether j ∈ N(i) implies i ∈ N(j) throughout. O(nedges + nnodes), by comparing the graph with its transpose; it guards the shortcut that reads a CSR as a CSC.

k_nearest(grid, I...; k, …) -> (idx, dist)

Allocating form of k_nearest!: returns the indices and their distances, nearest first.

k_nearest!(idx, dist, grid, I...; k, active_only=true, …) -> n

Write the k cells nearest to cell I into idx, and their distances into dist, nearest first. Returns how many were written, which is fewer than k only when the grid holds fewer candidates. The cell itself is excluded, as in neighbors_within!.

Exact under the geometry's own metric, on every architecture. It searches a ball, widens it until k cells have been seen, and keeps the k smallest in a bounded heap — so the answer never depends on the starting radius, and no candidate list is materialized. topology, scratch and reach behave as they do for neighbors_within!; an indexed topology makes each round a range query.

Ties at equal distance are broken by linear index, so the result is reproducible.

k_nearest(grid, p; k, …) -> (idx, dist)

The k cells nearest the point p, nearest first, exact under the geometry's own metric. The cell-seeded k_nearest is this at a cell centre, minus the cell itself.

mapreduce_within(f, op, init, grid; ball, …) -> value

Reduce f(I, J, d) with op over every cell I of grid and every cell J within ball of it, d being the distance. The bulk counterpart of fold_within.

Everything that depends on the grid alone is built once and reused across all n cells — above all the spatial index, which brings the sweep to O(n log n) on a curvilinear or node grid. A hand-written loop gets the topology for free, that being O(1), and rebuilds the index per cell.

That hoisting covers one call. The default index is binned at this call's ball, so a second sweep builds a second one; several sweeps at one radius should share a topology built once:

top = MetricTopology(grid; index = Grids.cell_list(grid; ball = r))
mapreduce_within(f, op, init, grid; ball = r, topology = top)

op must be associative and init its identity; partials are combined in cell order, so the answer is deterministic and independent of scheduling.

Which form the reduction takes is _buffered_candidates, as for foreach_within: where the candidates need no per-task buffer this is Execution.reduce_indices, so a grid integral runs wherever that does — a device included.

metric_band(grid, dim, coord_t, coord_n, ball) -> T

The exact half-width along direction dim of the part of the row at coord_n that lies within ball of a point at coord_t, in that direction's own coordinate units. coord_t and coord_n are coordinates on the other direction of a two-direction grid.

metric_window returns a bounding box, which suits a query that then filters on distance. A separable sweep — a prefix sum along a row, a row-by-row convolution — has no filtering step and needs the exact extent. This is the same geodesic solve, resolved per row.

Returns a negative number where the row is out of reach entirely, so band < 0 is the empty test. A row the ball covers completely gives the half-width of the whole direction (π in longitude).

On a sphere, for dim = 1, this inverts the spherical law of cosines:

\[|Δλ| ≤ \arccos\left(\frac{\cos(r/R) - \sin φ_t \sin φ_n}{\cos φ_t \cos φ_n}\right)\]

The empty band, the full circle and a pole at either end all fall out of that one expression. At a pole the denominator vanishes and the separation stops depending on λ; this returns the full half-width there, so no caller handles it.

metric_window(grid, I, ball) -> NTuple{N,Int}

Per-direction index half-width guaranteed to contain every cell within ball of cell I.

Each direction is bounded through its smallest gap — Grids.minimum_spacing, and the seam gap where the direction wraps — which is one number on a uniform axis and an O(N) scan on a stretched one. MetricTopology holds those gaps, so the four-argument form does no scanning at all; the three-argument form builds a topology per call. On a spherical or ellipsoidal grid the longitude cut additionally walks the latitude window for its smallest cosφ, so it costs the window it returns.

The window is a bound: neighbors_within! scans it and then filters on the geometry's own distance. It must cover the ball on the geometry it is asked about, so it is derived per geometry. On a spherical grid one longitude step spans R·cosφ·Δλ, so the λ half-width is taken at the latitude in the window nearest a pole; at a polar cell every longitude is in range, and the window says so.

metric_window(grid, ball) -> NTuple{N,Int}
metric_window(grid, ball, topology) -> NTuple{N,Int}

The per-cell window maximised over every cell of grid, for sizing a cache or a footprint table.

O(1): Grids.minimum_spacing gives the smallest gap per axis, and the extreme |cos φ| over a latitude axis is at one of its two ends, since |cos| on [-π/2, π/2] peaks in the middle. No cos per row, and no scan.

The result is the per-cell window at the worst cell, so it covers the ball at every cell.

neighbors!(out, grid, I...; stencil=Axial(1), active_only=true) -> n_written

Cell I's neighbors, as linear indices into the grid's mask, written into out. This is the form to use on a hot path: nneighbors counts them without writing, and Grids.neighbors returns a fresh vector. stencil is any Stencils.AbstractStencil.

neighbors_within(grid, I...; ball, active_only=true) -> Vector{Int}

The allocating form of neighbors_within!: counts, sizes, and fills in one call.

neighbors_within!(out, grid, I...; ball, active_only=true, topology, scratch, reach) -> n_written

Write the linear indices of every cell whose centre lies within ball of cell I. ball is a Stencils.MetricBall or a bare radius in the geometry's length units.

Distance is the geometry's own — great-circle on a sphere, Vincenty on a spheroid, the chord where a third direction is present — so the neighbourhood is a metric ball in that distance. The cell itself is excluded, matching stencil semantics where the zero offset is no neighbour. A periodic direction wraps, each cell appears at most once, and its coordinate is taken by minimum image, so the seam neither shortens nor lengthens a distance.

Cost is metric_window — O(1) per direction on any separable axis, uniform or stretched, given the per-direction minimum steps that topology carries — times one distance evaluation per candidate. Size the buffer with nneighbors_within: on a non-uniform or curved grid the number of cells within a fixed distance varies from cell to cell.

Three arguments matter for anything beyond a single query:

• topology — a MetricTopology, the grid invariants a ball query reads. The default is O(1) and allocation-free. On a curvilinear or node grid, pass indexed to bring each query to O(log n + m), or use foreach_within, which builds the index once for a whole sweep.
• scratch — a candidate buffer from ball_scratch, one per task. Accepted on every grid type and used where a query goes through a spatial index, i.e. on a curvilinear or node grid; a separable window has no candidate list to buffer. With one, an indexed query allocates nothing; without one it allocates its candidate list per call.
• reach — Unrestricted (the ball, and the default) or Connected (the part of it reachable from I without leaving it). A ball is not a connected patch: with a mask or a concave domain it can contain cells reachable from the seed only by going outside ball.

neighbors_within(grid, p; ball, …) -> Vector{Int}
nneighbors_within(grid, p; ball, …) -> Int

Cells within ball of the point p, and how many. p is a coordinate, where the cell-seeded methods take index arguments; it may be a Tuple, NamedTuple, AbstractVector or SVector, as everywhere else a point is accepted.

nneighbors(grid, I...; stencil=Axial(1), active_only=true) -> Int

How many neighbors neighbors! writes for cell I, counted without writing them.

nneighbors_within(grid, I...; ball, active_only=true) -> Int

The count neighbors_within! writes — how large its buffer must be.

sort_neighbors!(conn) -> conn

Sort each node's neighbor block ascending, in place. Rows are stencil-short, so an insertion sort per row is O(nedges) overall and needs no scratch.

sparse_adjacency_coo!(I, J, conn) -> ne
sparse_adjacency_coo!(I, J, V, conn) -> ne

Fill preallocated COO buffers (length ≥ nedges(conn)). V, if given, is set to true.

sparse_adjacency_csc!(colptr, rowval, conn) -> nedges

Fill caller-owned CSC structure arrays (length(colptr) ≥ nnodes+1, length(rowval) ≥ nedges) for the adjacency of conn, so that entry (i, j) is set iff j is a neighbor of i.

This is the direct route to a sparse matrix: CSR and CSC are the same layout transposed, so the structure is obtained by one counting pass and one placement pass over the existing neighbor list — no coordinate triples are materialized, nothing is sorted, and no permutation vector is built. Row indices come out ascending within each column for free, because the placement pass walks nodes in order. The running cursors live in colptr itself and are shifted back at the end, so this needs no scratch beyond the two output arrays.

sparse_adjacency_matrix(grid_or_conn; kwargs...) -> SparseMatrixCSC

Requires using SparseArrays (extension). Prefer sparse_adjacency_coo! when reusing COO buffers.

sparse_adjacency_matrix!(colptr, rowval, nzval, conn) -> SparseMatrixCSC

Assemble the adjacency matrix into caller-owned buffers and wrap them without copying, so a repeated build reuses one set of storage. Requires using SparseArrays.

The returned matrix aliases the three buffers, so reusing them for a later call invalidates any matrix built from them earlier. Buffers longer than needed are trimmed to fit (nnodes+1 and nedges), a matrix owning arrays of exactly the right length.

structured_grid([T], sampling, nlat; geometry, nlon, mask, periodic) -> StructuredGrid

Build a spherical StructuredGrid from a tensor-product sampling (Clenshaw–Curtis, Gauss–Legendre, Driscoll–Healy, McEwen–Wiaux, lat–lon, …). Longitude periodicity is auto-detected unless periodic is set.

T is the element type to build in, and defaults to the geometry's own, a geometry fixing the width of every coordinate and metric factor computed against it. Naming T converts the geometry to that width, so the grid is T throughout.

unstructured_grid([T], sampling, args...; geometry, areas, mask) -> UnstructuredGrid

Points from spherical_points, exact sampling topology from build_connectivity, and exact cell areas from the sampling's own tessellation. Pass areas to supply them instead.

T is the element type to build in, and defaults to the geometry's own, as for structured_grid.

The spherical pixelizations have their own layouts — Grids.HEALPixGrid, Grids.CubedSphereGrid, Grids.YinYangGrid, Grids.RingGrid — with coordinates, adjacency and measure arithmetic in their resolution parameters, and Grids.materialize turns one into a dense point cloud. This entry point covers the arbitrary mesh: the icosahedral geodesic, and a caller's own points.

unstructured_grid(::AbstractScatteredSphericalSampling, λ, φ; geometry, k, radius, areas, mask)

Build an UnstructuredGrid on an arbitrary (λ, φ) point set. The points are the caller's, so there is no resolution parameter. Adjacency comes from a k-d-tree query (k nearest, or everything within a physical radius) and cell areas default to the spherical Voronoi dual; see Grids.UnstructuredGrid for the extension each needs.

Grids.formula_neighbors(grid::CubedSphereGrid, k)

A cubed-sphere cell's four edge neighbours: the panel-interior offsets where they stay on the panel, and _cubed_neighbor's exact seam fold where they cross to another. The fold is derived by matching cube coordinates along the shared edge, so a seam neighbour is symmetric.

Grids.formula_neighbors(grid::RingGrid, i)

A ring grid's adjacency: the two points either side along the ring, wrapping in longitude, and on each adjacent ring the two points whose longitudes straddle this one's.

The straddling pair comes from proportional position, ⌊(j−1)·nlon[r′]/nlon[r]⌋ and its successor. Where adjacent rings differ in width this relation is directed — a wide ring's point can straddle a narrow ring's point that does not straddle it back — so the graph is not symmetric in general. It is symmetric whenever the two rings have equal counts, which is most of a Gaussian grid's interior.

Duplicates are dropped, so a ring holding one or two points reports fewer than the six a wide ring does.

Grids.formula_neighbors(grid::YinYangGrid, k)

A Yin–Yang cell's four edge neighbours within its own panel. Neither panel wraps and the two are not cross-linked, so a cell on a panel edge reports fewer; the panels couple through interpolation, the standard Yin–Yang discrete topology.