Merge "Update AltitudeConverter assets and references to be consistent with external documentation."

3 files changed, 94 insertions, 72 deletions

diff --git a/location/java/android/location/altitude/AltitudeConverter.java b/location/java/android/location/altitude/AltitudeConverter.java
index eb73b69737a2..3dc024efef56 100644
--- a/location/java/android/location/altitude/AltitudeConverter.java
+++ b/location/java/android/location/altitude/AltitudeConverter.java
@@ -31,6 +31,14 @@ import java.io.IOException;
 /**
  * Converts altitudes reported above the World Geodetic System 1984 (WGS84) reference ellipsoid
  * into ones above Mean Sea Level.
+ *
+ * <p>Reference:
+ *
+ * <pre>
+ * Brian Julian and Michael Angermann.
+ * "Resource efficient and accurate altitude conversion to Mean Sea Level."
+ * To appear in 2023 IEEE/ION Position, Location and Navigation Symposium (PLANS).
+ * </pre>
  */
 public final class AltitudeConverter {
 
@@ -81,27 +89,47 @@ public final class AltitudeConverter {
         long s2CellId = S2CellIdUtils.fromLatLngDegrees(location.getLatitude(),
                 location.getLongitude());
 
-        // (0,0) cell.
+        // Cell-space properties and coordinates.
+        int sizeIj = 1 << (S2CellIdUtils.MAX_LEVEL - params.mapS2Level);
+        int maxIj = 1 << S2CellIdUtils.MAX_LEVEL;
         long s0 = S2CellIdUtils.getParent(s2CellId, params.mapS2Level);
+        int f0 = S2CellIdUtils.getFace(s2CellId);
+        int i0 = S2CellIdUtils.getI(s2CellId);
+        int j0 = S2CellIdUtils.getJ(s2CellId);
+        int i1 = i0 + sizeIj;
+        int j1 = j0 + sizeIj;
+
+        // Non-boundary region calculation - simplest and most common case.
+        if (i1 < maxIj && j1 < maxIj) {
+            return new long[]{
+                    s0,
+                    S2CellIdUtils.getParent(S2CellIdUtils.fromFij(f0, i1, j0), params.mapS2Level),
+                    S2CellIdUtils.getParent(S2CellIdUtils.fromFij(f0, i0, j1), params.mapS2Level),
+                    S2CellIdUtils.getParent(S2CellIdUtils.fromFij(f0, i1, j1), params.mapS2Level)
+            };
+        }
+
+        // Boundary region calculation.
         long[] edgeNeighbors = new long[4];
         S2CellIdUtils.getEdgeNeighbors(s0, edgeNeighbors);
-
-        // (1,0) cell.
-        int i1 = S2CellIdUtils.getI(s2CellId) > S2CellIdUtils.getI(s0) ? -1 : 1;
-        long s1 = edgeNeighbors[i1 + 2];
-
-        // (0,1) cell.
-        int i2 = S2CellIdUtils.getJ(s2CellId) > S2CellIdUtils.getJ(s0) ? 1 : -1;
-        long s2 = edgeNeighbors[i2 + 1];
-
-        // (1,1) cell.
-        S2CellIdUtils.getEdgeNeighbors(s1, edgeNeighbors);
-        long s3 = 0;
-        for (int i = 0; i < edgeNeighbors.length; i++) {
-            if (edgeNeighbors[i] == s0) {
-                int i3 = (i + i1 * i2 + edgeNeighbors.length) % edgeNeighbors.length;
-                s3 = edgeNeighbors[i3] == s2 ? 0 : edgeNeighbors[i3];
-                break;
+        long s1 = edgeNeighbors[1];
+        long s2 = edgeNeighbors[2];
+        long s3;
+        if (f0 % 2 == 1) {
+            S2CellIdUtils.getEdgeNeighbors(s1, edgeNeighbors);
+            if (i1 < maxIj) {
+                s3 = edgeNeighbors[2];
+            } else {
+                s3 = s1;
+                s1 = edgeNeighbors[1];
+            }
+        } else {
+            S2CellIdUtils.getEdgeNeighbors(s2, edgeNeighbors);
+            if (j1 < maxIj) {
+                s3 = edgeNeighbors[1];
+            } else {
+                s3 = s2;
+                s2 = edgeNeighbors[3];
             }
         }
 
@@ -118,13 +146,12 @@ public final class AltitudeConverter {
      * Mean Sea Level altitude accuracy is added if the {@code location} has a valid vertical
      * accuracy; otherwise, does not add a corresponding accuracy.
      */
-    private static void addMslAltitude(@NonNull MapParamsProto params, @NonNull long[] s2CellIds,
+    private static void addMslAltitude(@NonNull MapParamsProto params,
             @NonNull double[] geoidHeightsMeters, @NonNull Location location) {
-        long s0 = s2CellIds[0];
         double h0 = geoidHeightsMeters[0];
         double h1 = geoidHeightsMeters[1];
         double h2 = geoidHeightsMeters[2];
-        double h3 = s2CellIds[3] == 0 ? h0 : geoidHeightsMeters[3];
+        double h3 = geoidHeightsMeters[3];
 
         // Bilinear interpolation on an S2 square of size equal to that of a map cell. wi and wj
         // are the normalized [0,1] weights in the i and j directions, respectively, allowing us to
@@ -132,8 +159,8 @@ public final class AltitudeConverter {
         long s2CellId = S2CellIdUtils.fromLatLngDegrees(location.getLatitude(),
                 location.getLongitude());
         double sizeIj = 1 << (S2CellIdUtils.MAX_LEVEL - params.mapS2Level);
-        double wi = Math.abs(S2CellIdUtils.getI(s2CellId) - S2CellIdUtils.getI(s0)) / sizeIj;
-        double wj = Math.abs(S2CellIdUtils.getJ(s2CellId) - S2CellIdUtils.getJ(s0)) / sizeIj;
+        double wi = (S2CellIdUtils.getI(s2CellId) % sizeIj) / sizeIj;
+        double wj = (S2CellIdUtils.getJ(s2CellId) % sizeIj) / sizeIj;
         double offsetMeters = h0 + (h1 - h0) * wi + (h2 - h0) * wj + (h3 - h1 - h2 + h0) * wi * wj;
 
         location.setMslAltitudeMeters(location.getAltitude() - offsetMeters);
@@ -167,7 +194,7 @@ public final class AltitudeConverter {
         MapParamsProto params = GeoidHeightMap.getParams(context);
         long[] s2CellIds = findMapSquare(params, location);
         double[] geoidHeightsMeters = mGeoidHeightMap.readGeoidHeights(params, context, s2CellIds);
-        addMslAltitude(params, s2CellIds, geoidHeightsMeters, location);
+        addMslAltitude(params, geoidHeightsMeters, location);
     }
 
     /**
@@ -190,7 +217,7 @@ public final class AltitudeConverter {
             return false;
         }
 
-        addMslAltitude(params, s2CellIds, geoidHeightsMeters, location);
+        addMslAltitude(params, geoidHeightsMeters, location);
         return true;
     }
 }
diff --git a/location/java/com/android/internal/location/altitude/GeoidHeightMap.java b/location/java/com/android/internal/location/altitude/GeoidHeightMap.java
index 73b6ab556ad0..8067050d9da3 100644
--- a/location/java/com/android/internal/location/altitude/GeoidHeightMap.java
+++ b/location/java/com/android/internal/location/altitude/GeoidHeightMap.java
@@ -99,8 +99,8 @@ public final class GeoidHeightMap {
 
     /**
      * Adds to {@code values} values in the unit interval [0, 1] for the map cells identified by
-     * {@code s2CellIds}. Returns true if values are present for all non-zero IDs; otherwise,
-     * returns false and adds NaNs for absent values.
+     * {@code s2CellIds}. Returns true if values are present for all IDs; otherwise, returns false
+     * and adds NaNs for absent values.
      */
     private static boolean getUnitIntervalValues(@NonNull MapParamsProto params,
             @NonNull TileFunction tileFunction,
@@ -109,10 +109,8 @@ public final class GeoidHeightMap {
 
         S2TileProto[] tiles = new S2TileProto[len];
         for (int i = 0; i < len; i++) {
-            if (s2CellIds[i] != 0) {
-                long cacheKey = getCacheKey(params, s2CellIds[i]);
-                tiles[i] = tileFunction.getTile(cacheKey);
-            }
+            long cacheKey = getCacheKey(params, s2CellIds[i]);
+            tiles[i] = tileFunction.getTile(cacheKey);
             values[i] = Double.NaN;
         }
 
@@ -128,9 +126,6 @@ public final class GeoidHeightMap {
 
         boolean allFound = true;
         for (int i = 0; i < len; i++) {
-            if (s2CellIds[i] == 0) {
-                continue;
-            }
             if (Double.isNaN(values[i])) {
                 allFound = false;
             } else {
@@ -195,7 +190,7 @@ public final class GeoidHeightMap {
         }
 
         for (int i = tileIndex; i < tiles.length; i++) {
-            if (s2CellIds[i] == 0 || tiles[i] != tiles[tileIndex]) {
+            if (tiles[i] != tiles[tileIndex]) {
                 continue;
             }
 
@@ -226,15 +221,14 @@ public final class GeoidHeightMap {
     private static void validate(@NonNull MapParamsProto params, @NonNull long[] s2CellIds) {
         Preconditions.checkArgument(s2CellIds.length == 4);
         for (long s2CellId : s2CellIds) {
-            Preconditions.checkArgument(
-                    s2CellId == 0 || S2CellIdUtils.getLevel(s2CellId) == params.mapS2Level);
+            Preconditions.checkArgument(S2CellIdUtils.getLevel(s2CellId) == params.mapS2Level);
         }
     }
 
     /**
      * Returns the geoid heights in meters associated with the map cells identified by
-     * {@code s2CellIds}. Throws an {@link IOException} if a geoid height cannot be calculated for a
-     * non-zero ID.
+     * {@code s2CellIds}. Throws an {@link IOException} if a geoid height cannot be calculated for
+     * an ID.
      */
     @NonNull
     public double[] readGeoidHeights(@NonNull MapParamsProto params, @NonNull Context context,
@@ -254,8 +248,8 @@ public final class GeoidHeightMap {
 
     /**
      * Same as {@link #readGeoidHeights(MapParamsProto, Context, long[])} except that data will not
-     * be loaded from raw assets. Returns the heights if present for all non-zero IDs; otherwise,
-     * returns null.
+     * be loaded from raw assets. Returns the heights if present for all IDs; otherwise, returns
+     * null.
      */
     @Nullable
     public double[] readGeoidHeights(@NonNull MapParamsProto params, @NonNull long[] s2CellIds) {
@@ -269,8 +263,8 @@ public final class GeoidHeightMap {
 
     /**
      * Adds to {@code heightsMeters} the geoid heights in meters associated with the map cells
-     * identified by {@code s2CellIds}. Returns true if heights are present for all non-zero IDs;
-     * otherwise, returns false and adds NaNs for absent heights.
+     * identified by {@code s2CellIds}. Returns true if heights are present for all IDs; otherwise,
+     * returns false and adds NaNs for absent heights.
      */
     private boolean getGeoidHeights(@NonNull MapParamsProto params,
             @NonNull TileFunction tileFunction, @NonNull long[] s2CellIds,
@@ -292,9 +286,6 @@ public final class GeoidHeightMap {
         // Enable batch loading by finding all cache keys upfront.
         long[] cacheKeys = new long[len];
         for (int i = 0; i < len; i++) {
-            if (s2CellIds[i] == 0) {
-                continue;
-            }
             cacheKeys[i] = getCacheKey(params, s2CellIds[i]);
         }
 
@@ -302,7 +293,7 @@ public final class GeoidHeightMap {
         S2TileProto[] loadedTiles = new S2TileProto[len];
         String[] diskTokens = new String[len];
         for (int i = 0; i < len; i++) {
-            if (s2CellIds[i] == 0 || diskTokens[i] != null) {
+            if (diskTokens[i] != null) {
                 continue;
             }
             loadedTiles[i] = mCacheTiles.get(cacheKeys[i]);
@@ -319,7 +310,7 @@ public final class GeoidHeightMap {
 
         // Attempt to load tiles from disk.
         for (int i = 0; i < len; i++) {
-            if (s2CellIds[i] == 0 || loadedTiles[i] != null) {
+            if (loadedTiles[i] != null) {
                 continue;
             }
 
diff --git a/location/java/com/android/internal/location/altitude/S2CellIdUtils.java b/location/java/com/android/internal/location/altitude/S2CellIdUtils.java
index 5f113877d416..08bcda41790e 100644
--- a/location/java/com/android/internal/location/altitude/S2CellIdUtils.java
+++ b/location/java/com/android/internal/location/altitude/S2CellIdUtils.java
@@ -70,6 +70,34 @@ public final class S2CellIdUtils {
         return fromLatLngRadians(Math.toRadians(latDegrees), Math.toRadians(lngDegrees));
     }
 
+    /** Returns the leaf S2 cell ID of the specified (face, i, j) coordinate. */
+    public static long fromFij(int face, int i, int j) {
+        int bits = (face & SWAP_MASK);
+        // Update most significant bits.
+        long msb = ((long) face) << (POS_BITS - 33);
+        for (int k = 7; k >= 4; --k) {
+            bits = lookupBits(i, j, k, bits);
+            msb = updateBits(msb, k, bits);
+            bits = maskBits(bits);
+        }
+        // Update least significant bits.
+        long lsb = 0;
+        for (int k = 3; k >= 0; --k) {
+            bits = lookupBits(i, j, k, bits);
+            lsb = updateBits(lsb, k, bits);
+            bits = maskBits(bits);
+        }
+        return (((msb << 32) + lsb) << 1) + 1;
+    }
+
+    /**
+     * Returns the face of the specified S2 cell. The returned face is in [0, 5] for valid S2 cell
+     * IDs. Behavior is undefined for invalid S2 cell IDs.
+     */
+    public static int getFace(long s2CellId) {
+        return (int) (s2CellId >>> POS_BITS);
+    }
+
     /**
      * Returns the ID of the parent of the specified S2 cell at the specified parent level.
      * Behavior is undefined for invalid S2 cell IDs or parent levels not in
@@ -219,26 +247,6 @@ public final class S2CellIdUtils {
         return fromFij(face, i, j);
     }
 
-    /** Returns the leaf S2 cell ID of the specified (face, i, j) coordinate. */
-    private static long fromFij(int face, int i, int j) {
-        int bits = (face & SWAP_MASK);
-        // Update most significant bits.
-        long msb = ((long) face) << (POS_BITS - 33);
-        for (int k = 7; k >= 4; --k) {
-            bits = lookupBits(i, j, k, bits);
-            msb = updateBits(msb, k, bits);
-            bits = maskBits(bits);
-        }
-        // Update least significant bits.
-        long lsb = 0;
-        for (int k = 3; k >= 0; --k) {
-            bits = lookupBits(i, j, k, bits);
-            lsb = updateBits(lsb, k, bits);
-            bits = maskBits(bits);
-        }
-        return (((msb << 32) + lsb) << 1) + 1;
-    }
-
     private static long fromFijWrap(int face, int i, int j) {
         double u = iToU(i);
         double v = jToV(j);
@@ -314,10 +322,6 @@ public final class S2CellIdUtils {
         return bits & (SWAP_MASK | INVERT_MASK);
     }
 
-    private static int getFace(long s2CellId) {
-        return (int) (s2CellId >>> POS_BITS);
-    }
-
     private static boolean isLeaf(long s2CellId) {
         return ((int) s2CellId & LEAF_MASK) != 0;
     }