Mixed aperture "4/3" grids: cell_to_index()/get_parent()/get_children() use the wrong numbering scheme and error

[gcol33]

Mixed aperture "4/3" grids: cell_to_index(), get_parent(), get_children() use the wrong numbering scheme and error on every call

Defect

lonlat_to_cell() (R/grid_helpers.R:71-94) and cell_to_lonlat() (:112-134) both special-case g@aperture == "4/3" and call the dedicated cpp_lonlat_to_cell_ap43/cpp_cell_to_lonlat_ap43 C++ entry points, which use calc_grid_params_ap43() — a distinct cell-ID numbering scheme for mixed grids (src/rcpp_cell.cpp:1209).

cell_to_index() (R/grid_helpers.R:653-674), get_parent() (:692-731), and get_children() (:745-780) have no such special case: they always call aperture_to_int(g@aperture) (returns 3L for "4/3", R/constants.R:257-259) and feed that into the generic cpp_cell_to_quad_ij/cpp_cell_to_index/cpp_get_parent_index/cpp_get_children_indices, which use the pure aperture-3 numbering (calc_grid_params(), not the ap43 variant).

Reproduction

grid <- hex_grid(resolution = 6, aperture = "4/3")
cells <- lonlat_to_cell(c(0, 30, -60), c(10, 45, -30), grid)   # 3629 5216 10420
get_parent(cells, grid)
# Error: cell_id must be a finite value in [1, 7292] for resolution 6, aperture 3
cell_to_index(cells, grid)
# same error

7292 is 10*3^6+2 (the pure aperture-3 cell count), not the actual ap43 cell space for this grid — a documented, first-class hex_grid(aperture = "4/3") option throws on every call to these three functions.

Impact

tests/testthat/test-hierarchical-index.R only exercises apertures 3, 4, 7 — never "4/3" — so this is completely uncovered by CI.

Fix

Add the same g@aperture == "4/3" special-casing to cell_to_index(), get_parent(), and get_children() that lonlat_to_cell()/cell_to_lonlat() already have, routing through the ap43-aware C++ entry points.

[gcol33]

Partially addressed in commit 17011c7, but the full fix turned out to be harder than the original write-up assumed -- leaving this open.

What changed

cell_to_index()/get_parent()/get_children() now raise a clear, explicit error for aperture = "4/3" grids ("Hierarchical index navigation ... is not implemented for mixed aperture "4/3" grids") instead of the confusing cell_id must be a finite value in [1, 7292] for resolution 6, aperture 3 bound error from the original report.

Why a full fix is more than wiring up special-casing

I implemented the naive fix first (route through icosa_tri_to_quad_ij-style ap43-aware quad/i/j conversion, matching lonlat_to_cell()/cell_to_lonlat()'s existing special-casing) and it produced silently wrong cell IDs, not just an error. Root cause: a mixed "4/3" grid's actual (i,j) coordinate range at a given nominal resolution is larger than a pure aperture-3 grid's range at that same resolution (it mixes base-4 and base-3 subdivisions per level -- e.g. at resolution 6 with mixed_aperture_level=3, valid (i,j) reach into the 20-40 range, confirmed via cpp_cell_to_quad_ij_ap43-equivalent decoding), but the Z3/zorder index-string encoders size their digit capacity purely from resolution (3^((resolution+1)/2) for Z3), which is far too small. Encoding those larger (i,j) values with the plain aperture-3 Z3 encoder truncates/collides silently -- confirmed by a same-resolution round-trip test that didn't recover the original cell ID (3629 -> 3795, off by ~166).

There's a second, deeper wrinkle: ap43_level(resolution) = floor(resolution/2) is recomputed independently at every resolution, so a resolution-6 "4/3" grid and a resolution-5 "4/3" grid don't nest the way pure-aperture grids do (the aperture-4/aperture-3 split boundary itself shifts between them) -- so even a correct index encoding would need to double check what "parent at resolution-1" is supposed to mean for this grid type before hierarchy navigation is well-defined.

What a real fix needs

A dedicated mixed-radix index format for "4/3" (some digits base-4, some base-3, matching the actual per-level branching factor), not a reuse of the pure aperture-3 Z3/zorder encoders. I didn't attempt this given the scope -- it's closer in size to #50 than to a wiring fix.

[gcol33]

Investigation findings

Following the same approach that paid off on #53 (check the DGGRID reference before designing anything from scratch), I checked whether DGGRID itself supports hierarchical index navigation for mixed-aperture (ISEA43H-style) grids.

DGGRID does not support this either

DGGRID's hierarchical index system enum is exhaustive:

// src/lib/dglib/include/dglib/DgAddressType.h
enum DgHierNdxSysType { Z7, ZOrder, Z3, InvalidHierNdxSysType };

and its own setup code (src/apps/dggrid/SubOpDGG.cpp) explicitly requires a pure aperture DGGS for every one of them:

if (hierNdxSysType == dgg::addtype::Z7) {
   if (apertureType != "PURE" || aperture != 7)
      ::report("hier_indexing_system_type Z7 requires a pure aperture 7 DGGS", DgBase::Fatal);
} else if (hierNdxSysType == dgg::addtype::Z3) {
    if (apertureType != "PURE" || aperture != 3)
        ::report("hier_indexing_system_type Z3 requires a pure aperture 3 DGGS", DgBase::Fatal);
} else if (hierNdxSysType == dgg::addtype::ZOrder) {
    if (apertureType != "PURE" || (aperture != 3 && aperture != 4))
        ::report("hier_indexing_system_type ZOrder requires a pure aperture 3 or 4 DGGS", DgBase::Fatal);
}

There is no Z43 system and no mixed-aperture path through any of the three. Mixed 4/3 (isMixed43) grids in DGGRID support cell IDs and geometry, but not hierarchical Z-index addressing -- this is a real capability gap in the reference tool, not something hexify is missing relative to it.

hexify's own mixed-aperture (i,j) coordinates are already an approximation, not a true mixed-radix substrate

Digging into cpp_lonlat_to_cell_ap43() (src/rcpp_cell.cpp:1232) while checking whether a hexify-original mixed-radix index would even be buildable, I found the (i,j) it uses isn't actually on a "aperture 4 for N levels, then aperture 3" substrate at all:

// Note: icosa_tri_to_quad_ij currently doesn't support mixed aperture sequences
// We use aperture=3 with adjusted resolution for the Quad IJ conversion
// This is a simplification that works because the final grid class
// depends only on the number of aperture-3 levels
...
hexify::icosa_tri_to_quad_ij(fwd.face, fwd.icosa_triangle_x, fwd.icosa_triangle_y, 3, resolution,
                             quad, i, j);

It quantizes as pure aperture 3 at the full target resolution, then relies on calc_grid_params_ap43()/calc_max_grid_dim_ap43() (which do correctly account for the mixed cell count) only for the cell-ID offset arithmetic. The (i,j) values themselves are not a genuine mixed-radix coordinate -- the comment already flags this as "a simplification... may need refinement."

This matters for scoping a fix: a hierarchical index built on top of the current (i,j) would be indexing an already-approximate coordinate system, not a mathematically exact ISEA43H grid. A fully correct mixed-radix Z-index would need the underlying quantization fixed first, which is a separate, larger piece of work than index encoding alone.

Current state is safe

Confirmed all three entry points (cell_to_index(), get_parent(), get_children()) cleanly throw the same explicit, descriptive error for "4/3" grids -- no silent wrong data anywhere I could find:

g <- hex_grid(resolution = 6, aperture = "4/3")
cells <- lonlat_to_cell(c(0, 30), c(10, 45), g)
cell_to_index(cells, g)  # errors: "Hierarchical index navigation ... is not implemented for mixed aperture \"4/3\" grids."
get_parent(cells, g)     # same error
get_children(cells, g)   # same error

Recommendation

Given DGGRID itself doesn't support this, and given hexify's mixed-aperture coordinate quantization is itself a documented approximation, I don't think this should be tackled as a quick "wire it up" fix or even a contained index-format design -- it's really two pieces of work stacked: (1) a genuine mixed-radix (i,j) substrate for ISEA43H, then (2) a hierarchical index format on top of it, neither of which has a reference implementation to check against. Given the risk profile demonstrated on #53 (hand-rolled hex-hierarchy math is easy to get subtly, silently wrong even when closely following a mature reference), I'd treat this as a dedicated, from-scratch design effort rather than something to attempt opportunistically. The current explicit-error behavior is the correct interim state.

[gcol33]

Update: fixed the underlying coordinate-system bug (7053391)

Following up on the investigation above -- I found and fixed a real, separate bug it surfaced: cpp_lonlat_to_cell_ap43()/cpp_cell_to_lonlat_ap43() were quantizing (i,j) as pure aperture 3 at the full resolution, completely ignoring mixed_aperture_level for the coordinate computation itself (only the cell-count/offset arithmetic accounted for the aperture-4 prefix). A mixed grid's true (i,j) range scales by 2^level * sqrt(3)^(res-level), not sqrt(3)^res -- so distinct real cells could silently collide onto the same cell ID once the aperture-4 prefix meaningfully changed the coordinate scale.

Fixed by adding quad_xy_to_ij_ap43()/quad_ij_to_xy_ap43() using the same scale/class formula calc_max_grid_dim_ap43() already used for grid sizing (so coordinates and sizing are finally consistent), and wiring them into both cell-ID functions. Validated with fuzz testing: 100% cell-ID round-trip across thousands of sampled points at every tested resolution/mixed-level combination, versus frequent collisions before. Full test suite passes; added regression tests in test-aperture-mixed.R.

This does not implement hierarchical index navigation (cell_to_index()/get_parent()/get_children() still throw the same explicit "not implemented" error) -- that's still the from-scratch design task described above, and DGGRID still has no reference for it. But the coordinate substrate it would need to build on is now correct instead of an approximation, which removes one of the two stacked problems I flagged earlier. It's also a real, independent correctness fix for anyone using lonlat_to_cell()/cell_to_lonlat() on "4/3" grids directly, regardless of hierarchical indexing.

[gcol33]

Follow-up: tested the "quick" mixed-radix index path -- it doesn't work either

Before attempting an actual index encoder on top of the now-fixed coordinate substrate, I tested the natural first hypothesis: that a mixed grid's (i,j) at full resolution cleanly decomposes into an aperture-4 "coarse" part (matching a pure aperture-4 quantization at mixed_aperture_level) plus an aperture-3 "fine" residual, via simple integer division (i_coarse = i_full %/% 3^eff_res_ap3).

It doesn't: only ~63% of sampled cells (806 same-quad cases, 511-517 matching) had i_coarse/j_coarse actually equal to the independently-computed pure aperture-4 coordinate at that level; the rest were off by small amounts (1-2), the same scattered-offset pattern seen elsewhere in this investigation (see #53's aperture-7 findings) whenever a naive integer decomposition is tried against quantization that's actually defined via geometric re-quantization (rotate/quantize/un-rotate/rescale), not plain positional-number arithmetic.

This rules out the "quick win" path definitively (with evidence, not just concern) -- a correct mixed-radix index encoder needs the same kind of careful, validated, iterative design as any other hex-hierarchy code in this area, most likely built by mirroring Z3's actual technique (src/index_z3.cpp): direct digit-PAIR extraction via a lookup table (kZ3EncodeTable) operating on geometrically-requantized sub-positions, not on the final (i,j) integers directly. That's a real, from-scratch design-and-validate effort, not a follow-up patch. Leaving this issue as-is (coordinate substrate fixed, index encoding not implemented) rather than attempting a rushed implementation now that I have direct evidence it would be wrong.

[gcol33]

Second investigation: why a mixed-radix digit encoder is harder than it looks

Attempted the "digit-pair-extraction, mirroring Z3" approach this comment thread already flagged as the right direction. Derived from first principles that a mixed 4/3 grid's resolution steps (at mixed_aperture_level = floor(resolution/2), the convention ap43_level() always uses) alternate cleanly between a single aperture-4-type step (R even) and a single aperture-3-type step with Class I/II flip (R odd) -- confirmed via the scale ratio X(R)/X(R-1) always reducing to exactly 2 or sqrt(3) with matching/flipping class, never a mixed step. That part holds up.

Built a candidate encoder from this: one radix-4 digit per aperture-4-type step (digit = 2*(i%2)+(j%2), matching encode_ap4), one radix-3 digit per aperture-3-type step (digit = i%3, reconstructing j%3 via the same j_required = {0,2,1} table cell_index.cpp's get_children_indices() already uses for pure aperture-3). Fuzz-tested (200k random points, quads 1-10, res 2-12) against the shipped, validated quad_xy_to_ij_ap43():

• Self-consistency (decode(encode(i,j)) == (i,j)) failed 86.6% of the time.

Root cause: encoding only i%3 and reconstructing j%3 from a fixed table silently discards real information in j -- it assumes every valid cell's (i,j) satisfies j%3 == j_required[i%3], which is not actually true in general.

To check whether that assumption is even sound for pure aperture-3 (no mixing involved), I tested it directly: took genuine quad_xy_to_ij(aperture=3) output and walked the ancestry chain down via floor-division, checking j%3 == j_required[i%3] at every level. It failed at 33.6% of levels, and 97% of cells hit at least one mismatch somewhere in their ancestry. So this single-digit-per-level shortcut is unsound even for pure aperture-3 -- it's not a mixing-specific problem.

This clarifies why the real Z3 encoder (index_z3.cpp) never does this: z3::encode() maps (i_digit, j_digit) pairs through kZ3EncodeTable, a genuine 9-to-9 bijection over two consecutive resolution levels -- it never throws away j. cell_index.cpp's separate get_children_indices() filter (the j_required table) is a different, narrower thing: given an already-known parent, it picks 3 of 9 candidate (i,j) combinations as "the children" -- that's a one-directional enumeration, not a losslessly-invertible per-level digit, and was never meant to support recovering j from i alone.

The complication specific to the mixed grid: Z3's fix (pair up two levels, bijective 9-to-9 table) assumes both levels are aperture-3. In the mixed grid the step sequence alternates aperture-3, aperture-4, aperture-3, aperture-4, ... (never two consecutive aperture-3 steps under the floor(resolution/2) convention), so Z3's pair table doesn't have two aperture-3 levels to pair up in the first place. A correct mixed-radix encoder needs a joint, lossless (i,j) encoding per single aperture-3 step (not per level-pair) -- which doesn't have a smaller-than-9-way lookup table by the analysis above, since a single un-paired aperture-3 step genuinely needs to distinguish all 9 (i%3, j%3) combinations, not just 3.

I did not attempt building that 9-ary-per-step encoder in this pass -- want to flag the finding rather than ship another unvalidated guess. Recommendation unchanged from the prior comment: this is a from-scratch design task, now with a clearer specific target (a lossless single-step joint (i,j) mod-3 encoding, verified against genuine quad_xy_to_ij output at every ancestry level, not just against itself).

Current state remains safe: cell_to_index()/get_parent()/get_children() still throw the explicit "not implemented for mixed aperture 4/3" error for these grids -- no silent wrong data shipped.

[gcol33]

Fixed in e390a1b (v0.7.3.9000). Mixed 4/3 grids have no DGGRID-standard hierarchical index (DGGRID rejects hierarchical indexing for any non-PURE aperture), so hexify now defines the hierarchy geometrically: since quad_xy_to_ij_ap43() does a single scaled quantisation per resolution, a cell's parent is the coarser cell whose lattice point contains its centre.

• get_parent() — re-quantise the cell centre at the coarser resolution.
• get_children() — exact inverse of get_parent (fast interior walk; O(sqrt n) boundary-band sweep for parents near a quad seam / icosahedron vertex).
• cell_to_index() — prefix-hierarchical string that round-trips cell -> index -> cell exactly.

Verified: get_children equals the brute-force geometric-parent inverse for every parent at res 2->3 .. 6->7 (0 missed, 0 extra), cell_to_index round-trips 100% of cells at res 1-8 including seam and vertex-scatter cells. Full suite: 6440 pass. Adds cpp_quad_ij_to_cell_ap43(), R/aperture_mixed_hierarchy.R, and tests in test-aperture-mixed.R.