Skip to content

Commit d3b17f1

Browse files
ZaczeroZaczero
committed
Bidirectional gridPathCells
1 parent 7a9fdf1 commit d3b17f1

File tree

2 files changed

+143
-36
lines changed

2 files changed

+143
-36
lines changed

‎src/apps/testapps/testGridPathCells.c‎

Lines changed: 44 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
* usage: `testGridPathCells`
2020
*/
2121

22+
#include <math.h>
2223
#include <stdio.h>
2324
#include <stdlib.h>
2425
#include <string.h>
@@ -29,6 +30,20 @@
2930
#include "test.h"
3031
#include "utility.h"
3132

33+
static void assertPathValid(H3Index start, H3Index end, const H3Index *path,
34+
int64_t size) {
35+
t_assert(size > 0, "path size is positive");
36+
t_assert(path[0] == start, "path starts with start index");
37+
t_assert(path[size - 1] == end, "path ends with end index");
38+
39+
for (int64_t i = 1; i < size; i++) {
40+
int isNeighbor;
41+
t_assertSuccess(
42+
H3_EXPORT(areNeighborCells)(path[i], path[i - 1], &isNeighbor));
43+
t_assert(isNeighbor, "path is contiguous");
44+
}
45+
}
46+
3247
SUITE(gridPathCells) {
3348
TEST(gridPathCells_acrossMultipleFaces) {
3449
H3Index start = 0x85285aa7fffffff;
@@ -40,15 +55,40 @@ SUITE(gridPathCells) {
4055
"Line not computable across multiple icosa faces");
4156
}
4257

43-
TEST(gridPathCells_pentagon) {
58+
TEST(gridPathCells_pentagonReverseInterpolation) {
4459
H3Index start = 0x820807fffffffff;
4560
H3Index end = 0x8208e7fffffffff;
4661

4762
int64_t size;
4863
t_assertSuccess(H3_EXPORT(gridPathCellsSize)(start, end, &size));
49-
H3Index *path = calloc(sizeof(H3Index), size);
50-
t_assert(H3_EXPORT(gridPathCells)(start, end, path) == E_PENTAGON,
51-
"Line not computable due to pentagon distortion");
64+
H3Index *path = calloc(size, sizeof(H3Index));
65+
66+
t_assertSuccess(H3_EXPORT(gridPathCells)(start, end, path));
67+
assertPathValid(start, end, path, size);
68+
69+
free(path);
70+
}
71+
72+
TEST(gridPathCells_knownFailureNotCoveredByReverseInterpolation) {
73+
// Known limitation case:
74+
//
75+
// There are still pairs where `gridDistance` succeeds but interpolation
76+
// fails in both origin-anchored local IJK charts (anchored at `start`
77+
// and anchored at `end`). Since `gridPathCells` only performs these two
78+
// interpolation attempts, it returns an error.
79+
//
80+
// This test keeps a pinned input pair to demonstrate that the current
81+
// approach is not complete.
82+
H3Index start = 0x8411b61ffffffff;
83+
H3Index end = 0x84016d3ffffffff;
84+
85+
int64_t size;
86+
t_assertSuccess(H3_EXPORT(gridPathCellsSize)(start, end, &size));
87+
H3Index *path = calloc(size, sizeof(H3Index));
88+
89+
H3Error err = H3_EXPORT(gridPathCells)(start, end, path);
90+
t_assert(err != E_SUCCESS, "Expected gridPathCells to fail");
91+
5292
free(path);
5393
}
5494
}

‎src/h3lib/lib/localij.c‎

Lines changed: 99 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -22,9 +22,12 @@
2222
#include <assert.h>
2323
#include <inttypes.h>
2424
#include <math.h>
25+
#include <stdbool.h>
2526
#include <stdlib.h>
2627
#include <string.h>
2728

29+
#include "algos.h"
30+
#include "alloc.h"
2831
#include "baseCells.h"
2932
#include "faceijk.h"
3033
#include "h3Assert.h"
@@ -398,9 +401,10 @@ H3Error localIjkToCell(H3Index origin, const CoordIJK *ijk, H3Index *out) {
398401
for (int i = 0; i < pentagonRotations; i++) {
399402
dir = _rotate60ccw(dir);
400403
}
401-
// The pentagon rotations are being chosen so that dir is not the
402-
// deleted direction. If it still happens, it means we're moving
403-
// into a deleted subsequence, so there is no index here.
404+
// The pentagon rotations are chosen to avoid the deleted direction
405+
// (the missing neighbor direction around a pentagon). If we still
406+
// land on it, the coordinate would cross pentagon distortion and
407+
// cannot be represented.
404408
if (dir == K_AXES_DIGIT) {
405409
return E_PENTAGON;
406410
}
@@ -603,13 +607,15 @@ H3Error H3_EXPORT(gridDistance)(H3Index origin, H3Index index, int64_t *out) {
603607

604608
/**
605609
* Number of indexes in a line from the start index to the end index,
606-
* to be used for allocating memory. Returns a negative number if the
607-
* line cannot be computed.
610+
* to be used for allocating memory.
611+
*
612+
* On success, sets `*size` to `gridDistance(start, end) + 1`
613+
* (including both endpoints).
608614
*
609615
* @param start Start index of the line
610616
* @param end End index of the line
611-
* @param size Size of the line
612-
* @returns 0 on success, or another value on error
617+
* @param size Output size of the line
618+
* @returns 0 on success, otherwise the error from `gridDistance`
613619
*/
614620
H3Error H3_EXPORT(gridPathCellsSize)(H3Index start, H3Index end,
615621
int64_t *size) {
@@ -654,34 +660,32 @@ static void cubeRound(double i, double j, double k, CoordIJK *ijk) {
654660
}
655661

656662
/**
657-
* Given two H3 indexes, return the line of indexes between them (inclusive).
658-
*
659-
* This function may fail to find the line between two indexes, for
660-
* example if they are very far apart. It may also fail when finding
661-
* distances for indexes on opposite sides of a pentagon.
663+
* Attempts to generate a shortest-length path by interpolating through an
664+
* origin-anchored local IJK coordinate space.
662665
*
663-
* Notes:
666+
* This helper implements the interpolation-based path construction used by
667+
* `gridPathCells`. It can fail if interpolation lands on intermediate IJK
668+
* coordinates that cannot be mapped back to valid H3 cells. This can occur
669+
* because the origin-anchored local IJ(K) space is not globally continuous, and
670+
* some intermediate coordinates do not have an inverse mapping back to a cell
671+
* in the chosen chart (for example, due to discontinuities or warping near
672+
* pentagons).
664673
*
665-
* - The specific output of this function should not be considered stable
666-
* across library versions. The only guarantees the library provides are
667-
* that the line length will be `gridDistance(start, end) + 1` and that
668-
* every index in the line will be a neighbor of the preceding index.
669-
* - Lines are drawn in grid space, and may not correspond exactly to either
670-
* Cartesian lines or great arcs.
674+
* The output is written to `out[outOffset + outStep * n]`, allowing callers to
675+
* fill the path in either direction without an intermediate buffer.
671676
*
672-
* @param start Start index of the line
673-
* @param end End index of the line
674-
* @param out Output array, which must be of size gridPathCellsSize(start, end)
675-
* @return 0 on success, or another value on failure.
677+
* @param start Origin cell for local IJK conversions
678+
* @param end Target cell
679+
* @param distance Expected edge distance between `start` and `end`
680+
* @param out Output buffer
681+
* @param outOffset Output index for the first element
682+
* @param outStep Output stride (+1 for forward fill, -1 for reverse fill)
683+
* @return E_SUCCESS if all intermediate steps convert successfully, otherwise
684+
* the first encountered conversion error
676685
*/
677-
H3Error H3_EXPORT(gridPathCells)(H3Index start, H3Index end, H3Index *out) {
678-
int64_t distance;
679-
H3Error distanceError = H3_EXPORT(gridDistance)(start, end, &distance);
680-
// Early exit if we can't calculate the line
681-
if (distanceError) {
682-
return distanceError;
683-
}
684-
686+
static H3Error gridPathCellsInterpolate(H3Index start, H3Index end,
687+
int64_t distance, H3Index *out,
688+
int64_t outOffset, int64_t outStep) {
685689
// Get IJK coords for the start and end. We've already confirmed
686690
// that these can be calculated with the distance check above.
687691
CoordIJK startIjk = {0};
@@ -715,7 +719,8 @@ H3Error H3_EXPORT(gridPathCells)(H3Index start, H3Index end, H3Index *out) {
715719
(double)startIjk.k + kStep * n, &currentIjk);
716720
// Convert cube -> ijk -> h3 index
717721
cubeToIjk(&currentIjk);
718-
H3Error currentError = localIjkToCell(start, &currentIjk, &out[n]);
722+
const int64_t idx = outOffset + outStep * n;
723+
H3Error currentError = localIjkToCell(start, &currentIjk, &out[idx]);
719724
if (currentError) {
720725
// The cells between `start` and `end` may fall in pentagon
721726
// distortion.
@@ -725,3 +730,65 @@ H3Error H3_EXPORT(gridPathCells)(H3Index start, H3Index end, H3Index *out) {
725730

726731
return E_SUCCESS;
727732
}
733+
734+
/**
735+
* Given two H3 indexes, return the line of indexes between them (inclusive).
736+
*
737+
* This function relies on `gridDistance(start, end)` to determine the expected
738+
* path length, and will return the same error if `gridDistance` fails.
739+
*
740+
* Path construction is performed by straight-line interpolation in the
741+
* origin-anchored local IJK coordinate space:
742+
*
743+
* - First, interpolate using `start` as the local IJK origin.
744+
* - If interpolation fails, retry using `end` as the local IJK origin and
745+
* reverse the resulting sequence into `out`.
746+
*
747+
* If both interpolation attempts fail, this function returns the error from the
748+
* first attempt.
749+
*
750+
* Notes:
751+
*
752+
* - The specific output of this function should not be considered stable
753+
* across library versions. The only guarantees the library provides are
754+
* that the line length will be `gridDistance(start, end) + 1` and that
755+
* every index in the line will be a neighbor of the preceding index.
756+
* - Lines are drawn in grid space, and may not correspond exactly to either
757+
* Cartesian lines or great arcs.
758+
*
759+
* @param start Start index of the line
760+
* @param end End index of the line
761+
* @param out Output array, which must be of size gridPathCellsSize(start, end)
762+
* @return 0 on success, or another value on failure.
763+
*/
764+
H3Error H3_EXPORT(gridPathCells)(H3Index start, H3Index end, H3Index *out) {
765+
int64_t distance;
766+
H3Error distanceError = H3_EXPORT(gridDistance)(start, end, &distance);
767+
// Early exit if we can't calculate the line
768+
if (distanceError) {
769+
return distanceError;
770+
}
771+
772+
if (distance == 0) {
773+
out[0] = start;
774+
return E_SUCCESS;
775+
}
776+
777+
// Straight-line interpolation in local IJK space anchored at `start`.
778+
H3Error interpolateErr =
779+
gridPathCellsInterpolate(start, end, distance, out, 0, 1);
780+
if (!interpolateErr) {
781+
return E_SUCCESS;
782+
}
783+
784+
// Retry interpolation anchored at `end` and reverse the output.
785+
// This can resolve cases where the local IJK chart is discontinuous
786+
// relative to one origin but not the other.
787+
H3Error reverseErr =
788+
gridPathCellsInterpolate(end, start, distance, out, distance, -1);
789+
if (!reverseErr) {
790+
return E_SUCCESS;
791+
}
792+
793+
return interpolateErr;
794+
}

0 commit comments

Comments
 (0)