How to calculate the average distance between 2 neighboring H3 Cells?

883 Views Asked by At

I'm using the Uber H3 Library for Java https://github.com/uber/h3-java

I'm trying to figure out what is the average distance between 2 neighboring H3 cells of resolution 15 (the distance between their respective center points, or 2 x apothem).

I'm getting 3 significantly different results, depending on how I try to calculate:

  • 1.148 meters
  • 0.882 meters
  • 0.994 meters

Which one is correct ? And why am I getting such different results ?

public static final long RES_15_HEXAGON = 644569124665188486L; // some random res 15 H3 index (as Long)

private final H3Core h3;

H3UtilsTest() throws IOException {
   h3 = H3Core.newInstance();
}

@Test
void calculateDistanceBetweenNeighborsFromRealEdges() {
    final long h3Index = RES_15_HEXAGON;
    final GeoCoord centerPoint = h3.h3ToGeo(h3Index);
    assertEquals(46.94862876826281, centerPoint.lat);
    assertEquals(7.4404471879141205, centerPoint.lng);
    assertEquals(15, h3.h3GetResolution(h3Index));
    final List<GeoCoord> hexagon = this.h3.h3ToGeoBoundary(h3Index);
    assertEquals(6, hexagon.size());
    List<Double> edgeLengths = new ArrayList<>();
    for (int i = 0; i < hexagon.size(); i++) {
        edgeLengths.add(h3.pointDist(hexagon.get(i), hexagon.get((i + 1) % hexagon.size()), LengthUnit.m));
    }

    final double apothem = edgeLengths.stream().mapToDouble(Double::doubleValue).average().getAsDouble();
    assertEquals(0.5739852101653261, apothem);

    final double distanceBetweenNeighbors = 2 * apothem;
    assertEquals(1.1479704203306522, distanceBetweenNeighbors);
}

@Test
void calculateDistanceBetweenNeighborsFromAverageEdges() {
    final double averageEdgeLength = h3.edgeLength(15, LengthUnit.m);
    assertEquals(0.509713273, averageEdgeLength);
    assertEquals(1.019426546, 2 * averageEdgeLength);

    final double apothem = averageEdgeLength * Math.sqrt(3) / 2;
    assertEquals(0.4414246430641128, apothem);

    final double distanceBetweenNeighbors = 2 * apothem;
    assertEquals(0.8828492861282256, distanceBetweenNeighbors);
}

@Test
void calculateDistanceBetweenNeighborsFromNeighbors() {
    final GeoCoord origin = h3.h3ToGeo(RES_15_HEXAGON);
    final List<Long> neighbors = h3.kRing(RES_15_HEXAGON, 1);
    assertEquals(7, neighbors.size()); // contains the center hexagon as well
    neighbors.forEach(neighbor -> assertEquals(6, h3.h3ToGeoBoundary(neighbor).size())); // they are really 6-sided hexagons !
    final List<Double> distances = neighbors.stream().filter(neighbor -> neighbor != RES_15_HEXAGON).map(neighbor -> h3.pointDist(origin, h3.h3ToGeo(neighbor), LengthUnit.m)).toList();
    assertEquals(6, distances.size());

    final Double distanceBetweenNeighbors = distances.stream().mapToDouble(Double::doubleValue).average().getAsDouble();
    assertEquals(0.9941567117250641, distanceBetweenNeighbors);
}
2

There are 2 best solutions below

4
On BEST ANSWER

I assume you're getting different answers for these different approaches due to shape distortion of the "hexagon" shape across the grid. This is the cell you chose and its neighbors:

K-ring of 1 for 644569124665188486

You can see that the hexagons are not perfectly regular - while H3 tries to minimize distortion, we do have shape distortion that varies across the globe. Cell size and shape will vary slightly depending on where you choose to sample.

The "correct" answer here depends heavily on your use case. We can likely calculate an average distance between cell centers for the whole globe, but you might actually care about a more localized area. Or the average may not be what you really need - you may want to calculate this on a per-cell basis. In most cases, I have found that it is better to either:

  • Calculate the actual distances for the cells of interest, using pointDist between cell centers, or
  • Sample within an area of interest, e.g. an application viewport, and calculate an average from the sample.
0
On

For what it's worth, I implemented a way to create a larger sample, inspired by the suggestion by @nrabinowitz:

public static final long RES_15_HEXAGON = 644569124665188486L;

private final H3Core h3;

H3UtilsTest() throws IOException {
   h3 = H3Core.newInstance();
}

@Test
void calculateDistanceBetweenNeighborsUsingLargerSample() {
    final Set<Long> origins = new HashSet<>(Set.of(RES_15_HEXAGON));
    final Set<Long> visitedOrigins = new HashSet<>();
    final Set<Long> nextOrigins = new HashSet<>();

    final List<Double> distances = new ArrayList<>();
    final int nbIterations = 10;
    for (int i = 0; i < nbIterations; i++) {
        for (Long origin : origins) {
            visitedOrigins.add(origin);
            final Set<Long> destinations = new HashSet<>(h3.kRing(origin, 1));
            destinations.removeAll(visitedOrigins);
            for (Long destination : destinations) {
                distances.add(h3.pointDist(h3.h3ToGeo(origin), h3.h3ToGeo(destination), LengthUnit.m));
            }
            destinations.removeAll(origins); // we don't need the hexagons (anymore) that are on the same ring as origins
            nextOrigins.addAll(destinations);
        }
        origins.clear();
        origins.addAll(nextOrigins);
        nextOrigins.clear();
    }

    final double averageDistanceBetweenNeighbors = distances.stream().mapToDouble(Double::doubleValue).average().getAsDouble();
    assertEquals(0.9942, averageDistanceBetweenNeighbors, 0.0001);
    assertEquals(870, distances.size());
}