Z7 index round-trip fails for some cells at aperture 7 (encode/decode pentagon-rotation mismatch)

[gcol33]

Defect (found while verifying #47's get_children_indices fix)

For aperture 7, encoding a cell ID to a Z7 index and decoding it back does not always recover the original cell ID.

Reproduction

g <- hex_grid(resolution = 4, aperture = 7)
cells <- lonlat_to_cell(c(0, 30, -60), c(10, 45, -30), g)
print(cells)
# [1] 17979 25142 46111

idx <- cell_to_index(cells, g)
print(idx)
# [1] "036566" "004545" "076106"

rt <- sapply(idx, function(s) {
  r <- cpp_index_to_cell(s, 7, "z7")
  cpp_quad_ij_to_cell(r$face, r$i, r$j, r$resolution, 7)
})
print(rt)
# 036566 004545 076106
#  17979   9316  46111

The first and third cells round-trip correctly; the second (25142) decodes to a different cell (9316) than it was encoded from.

Confirmed pre-existing

Verified via git stash that this reproduces identically at commit 59e3404 (before any of this audit session's fixes) -- not a regression from #31/#32/#35/#36/#37/#50 or the R-level fixes in ab2a811/d15edea.

Likely area

src/index_z7.cpp's encode()/decode() have nontrivial pentagon-adjacency rotation logic (adjacentBaseCellTable, rotateDigitVecCCW, the skipRotate/firstNonZero digit-rotation handling for pentagon gaps near cells 0-5/6-11) that likely has an edge case where the rotation applied during encode doesn't exactly invert during decode for certain base-cell/digit combinations. Given the complexity of this logic (ported/adapted pentagon-skip handling), this needs a dedicated investigation pass against known-good reference values (e.g. DGGRID or H3's own Z7-equivalent, if one exists) rather than a quick patch -- same caution as #50's investigation.

[gcol33]

Investigation findings

Confirmed the reported repro (quad=4, i=16, j=41, res=4 -> 004545 decodes to a different cell) and traced it to a genuine root cause -- but the fix turned out to be far bigger than the reported symptom, so documenting everything found here before pausing.

Root cause of the reported case: encode() is not injective near the poles

encode()'s pentagon-boundary handling (the adjacentBaseCellTable/rotateDigitVecCCW logic that folds a boundary cell from quad 1-5 or 6-10 onto base cell 0/11) destroys information. Concretely:

g <- hex_grid(resolution = 4, aperture = 7)
# Two different, independently-verified-valid real cells:
cpp_quad_ij_to_cell(4, 16, 41, 4, 7)  # -> cell 25142, quad 4
cpp_quad_ij_to_cell(1, 24, 49, 4, 7)  # -> cell 4155,  quad 1
# Both round-trip correctly through the full geographic pipeline (id -> lonlat -> id).
# Both encode to the SAME Z7 string:
cell_to_index(c(25142, 4155), g)  # -> "004545" "004545"  <- collision

No decode function can recover the original cell from "004545" alone -- the collision is in encode(), not decode(). This isn't an edge case limited to the reported repro; a restricted fuzz test (pentagon-remapped cells only, quads 1-5/6-10, resolutions 1-8) hits ambiguous or wrong decodes on effectively all cases I tried once collisions are accounted for.

This is a faithful, byte-for-byte port of DGGRID's own code -- and DGGRID has the same bug

I compared hexify's src/index_z7.cpp/ijk_coordinates.cpp line-by-line against DGGRID's actual upstream source (sahrk/DGGRID, current master):

• DgZ7StringRF.cpp (quantify/invQuantify) -- identical algorithm, identical tables (adjacentBaseCellTable, inverseAdjacentBaseCellTable), identical branch structure, down to the same // why is H3 different? comment.
• DgIVec3D.cpp (upAp7/upAp7r/downAp7/downAp7r/ijkPlusNormalize/rotateDigitVecCCW) -- identical.

DGGRID's own changelog documents a prior fix in this exact area (v8.36, 2025-05-11: "errors indexing pentagonal descendents with Z7 indexing") -- that fix is already reflected in both DGGRID's current master and hexify's port. The collision above reproduces against DGGRID's current, already-patched code, so this looks like a still-open upstream defect, not a hexify porting mistake. I have not been able to build/run DGGRID itself in this environment to confirm directly against the compiled tool, so treat "still-open upstream" as high-confidence but not 100% certain.

Broader problem: odd-resolution round-trip is badly broken even away from any pentagon

Testing the real forward pipeline (lonlat_to_cell -> cell_to_index -> index_to_cell -> cpp_quad_ij_to_cell) on random points, away from poles:

resolution	round-trip success
1 (odd)	8.8%
2 (even)	69.8%
3 (odd)	errors out (cell_id must be a finite value in [1, 12252])

Odd resolutions are far worse, but even resolutions are clearly broken too (69.8%, nowhere near acceptable). I traced this to a mismatch between two independently-developed subsystems:

• index_z7.cpp's encode()/decode() assume (i,j) at a given resolution relates to the next resolution via a clean aperture-7 hierarchy walk (upAp7/upAp7r, with odd resolutions getting a "+1 level, discard first digit" pad).
• coordinate_transforms.cpp's actual aperture-7 quantization (quad_xy_to_ij/quad_ij_to_xy) scales (i,j) by sqrt(7)^resolution * substrate_mult, where substrate_mult is sqrt(7) for even (Class III-I) resolutions and sqrt(21) for odd (Class III-II) resolutions -- a different multiplier depending on which resolution-class transition is being crossed.

I verified this concretely: computing a cell's true geometric parent (by re-projecting its lon/lat center at resolution - 1 through the validated forward pipeline, sidestepping index_z7.cpp entirely) and checking whether child_ij = 7 * parent_ij + small_offset holds -- it does not. The offset is unbounded and unpatterned across 100 sampled cells (ranging roughly -30 to +44), confirming (i,j) does not scale by a constant factor between consecutive resolutions the way index_z7.cpp assumes.

What a real fix needs

This is bigger than index_z7.cpp. A correct fix needs to either:

1. Precisely account for the substrate_mult (sqrt(7) vs sqrt(21)) relationship between consecutive resolutions when walking the hierarchy, so a cell's digit path is computed consistently with how coordinate_transforms.cpp actually quantizes (i,j) at each resolution, or
2. Build Z7 encoding on a different, more robust basis -- e.g. determining each digit via geometric re-projection through the already-validated lonlat_to_cell/cell_to_lonlat pipeline instead of the abstract upAp7/downAp7 IJK walk (slower, but grounded in code that's independently proven correct).

Either path touches code shared by every aperture-7 feature (cell IDs, lon/lat conversion), not just Z7 indexing, so it needs careful regression testing across the whole aperture-7 surface, not just Z7 round-trips.

Also worth noting: get_parent()/get_children() (R/grid_helpers.R) for aperture 7 route entirely through this same Z7 machinery (cpp_get_parent_index/cpp_get_children_indices) -- there is no independent, already-correct parent/child implementation to build from. A fix here would also fix those.

Suggested next steps

• File the collision repro upstream against sahrk/DGGRID (I can draft this if useful).
• Treat this as a dedicated redesign effort (comparable to hexify::z3::encode() discards the sign of i/j via std::abs(), causing Z3 index collisions #50), not a quick patch -- likely needs its own investigation into the substrate_mult relationship before writing any replacement code.

[gcol33]

Root cause pinned down (2026-07-18): faithful port, wrong coordinate feed

Diffed hexify's src/index_z7.cpp + src/ijk_coordinates.cpp (IVec3D) line-by-line against DGGRID master (DgZ7StringRF.cpp, DgIVec3D.cpp). hexify's z7::encode/decode and every IVec3D op are a byte-for-byte faithful port — the encoder is not the bug.

The bug is that hexify feeds z7::encode its own surrogate (i,j) addressing, while DGGRID's quantify() expects the DGG's Q2DI (i,j). These agree only for interior, even-resolution cells; everywhere else they diverge. Measured cell -> cell_to_index -> cpp_index_to_cell -> cpp_quad_ij_to_cell round-trip on 400-500 random cells/res:

res	round-trip OK
1 (odd)	18%
2 (even)	66%
3 (odd)	12%
4 (even)	65%
5 (odd)	14%
6 (even)	65%
7 (odd)	9%

Two independent coordinate defects, now isolated:

1. Odd resolutions (Class III) — SOLVED in a test harness. DGGRID's quantify uses effectiveRes = res+1 and treats the input coord as being at the Class I substrate (res+1), not at res (see DgZ7StringRF.cpp:57, and the first && isClassIII digit skip). hexify feeds the surrogate at res. Feeding the res+1 substrate coord instead (quad_xy_to_surrogate_ij_ap7(qx, qy, res+1)) lifts odd-res parity up to even-res levels (~63% uniform). Even resolutions already use effectiveRes = res, which is why they were less broken.

2. Cross-quad / base-cell adjacency — the remaining blocker (~37%, uniform). Of the residual failures, ~87% are cells where z7 remaps the base cell (out_quad != in_quad via adjacentBaseCellTable). hexify assigns each ap7 cell to one quad in a centred surrogate frame (coords can go negative near seams); DGGRID assigns to base cells in a corner frame [0, 7^numClassI) with base-cell adjacency + per-base-cell orientation. Reconciling the two — DGGRID's 12 base-cell frames/orientations, the cross-seam folding, and the pentagon (base cell 0/11) rotation skips — against hexify's quad frames (kQuadAdjacency, kTriangleMap) is the substantial remaining work.

A geometric encode/decode framework (project centre -> per-quad quantize -> substrate at odd res -> z7 -> geometric inverse back to lon/lat) reaches ~63% and cleanly separates defect 2 from defect 1. Completing it to 100% is the multi-day Q2DI-addressing reimplementation, isolated to the z7 index path (it must not disturb the shared, validated ap7 forward/inverse pipeline).

Scope confirmed as "bigger than index_z7.cpp alone": the fix lives in the ap7 coordinate addressing (coordinate_transforms.cpp surrogate/substrate + a new cell<->Q2DI layer), not in the faithful z7 port.