summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDavid Beaumont <dbeaumont@google.com>2011-10-31 18:44:08 -0400
committerMichael Bolin <bolinfest@google.com>2011-10-31 18:44:08 -0400
commit89b87704cb0060932f099cb45182145d9ec46337 (patch)
treea7ba7f4dcf9dd67d70ef2b081ab1cdae5a1dc3c8
parent9d370a807464bd49b220f17944eadde7e5d8e0af (diff)
downloads2-geometry-library-java-89b87704cb0060932f099cb45182145d9ec46337.tar.gz
Made 'constant' classes fully immutable by either removing or wrapping final
static arrays. The IJ_TO_POS array was never being called so for now I removed it. We can trivially add it back (with appropriate lookup function) if we need it later. The other arrays were wrapped and given (hopefully) better JavaDoc. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=25078833
-rw-r--r--src/com/google/common/geometry/S2.java83
-rw-r--r--src/com/google/common/geometry/S2Cell.java4
-rw-r--r--src/com/google/common/geometry/S2CellId.java16
-rw-r--r--src/com/google/common/geometry/S2Projections.java17
-rw-r--r--tests/com/google/common/geometry/S2CellIdTest.java2
-rw-r--r--tests/com/google/common/geometry/S2Test.java23
6 files changed, 89 insertions, 56 deletions
diff --git a/src/com/google/common/geometry/S2.java b/src/com/google/common/geometry/S2.java
index 9fc876a..1b49ca9 100644
--- a/src/com/google/common/geometry/S2.java
+++ b/src/com/google/common/geometry/S2.java
@@ -47,8 +47,8 @@ public final strictfp class S2 {
* {@code (0.5 <= |v|*2^(-exp) < 1)}. If v is zero, return 0.
*
* <p>Note that this arguably a bad definition of exponent because it makes
- * {@code exp(9) == 4}. In decimal this would be like saying that the exponent
- * of 1234 is 4, when in scientific 'exponent' notation 1234 is
+ * {@code exp(9) == 4}. In decimal this would be like saying that the
+ * exponent of 1234 is 4, when in scientific 'exponent' notation 1234 is
* {@code 1.234 x 10^3}.
*
* TODO(dbeaumont): Replace this with "DoubleUtils.getExponent(v) - 1" ?
@@ -62,26 +62,30 @@ public final strictfp class S2 {
return (int) ((EXPONENT_MASK & bits) >> EXPONENT_SHIFT) - 1022;
}
- /**
- * kPosToOrientation[pos] -> orientation_modifier
- *
- * Return a modifier indicating how the orientation of the child subcell with
- * the given traversal position [0..3] is related to the orientation of the
- * parent cell. The modifier should be XOR-ed with the parent orientation to
- * obtain the curve orientation in the child.
- *
- */
- static final int[] POS_TO_ORIENTATION = {SWAP_MASK, 0, 0, INVERT_MASK + SWAP_MASK};
+ /** Mapping Hilbert traversal order to orientation adjustment mask. */
+ private static final int[] POS_TO_ORIENTATION =
+ {SWAP_MASK, 0, 0, INVERT_MASK + SWAP_MASK};
/**
+ * Returns an XOR bit mask indicating how the orientation of a child subcell
+ * is related to the orientation of its parent cell. The returned value can
+ * be XOR'd with the parent cell's orientation to give the orientation of
+ * the child cell.
*
- * kPosToIJ[orientation][pos] -> ij // // Return the (i,j) index of the
- * subcell at the given position 'pos' in the // Hilbert curve traversal order
- * with the given orientation. This is the // inverse of the previous table:
- * kPosToIJ[r][kIJtoPos[r][ij]] == ij
+ * @param position the position of the subcell in the Hilbert traversal, in
+ * the range [0,3].
+ * @return a bit mask containing some combination of {@link #SWAP_MASK} and
+ * {@link #INVERT_MASK}.
+ * @throws IllegalArgumentException if position is out of bounds.
*/
- public static final int[][] POS_TO_IJ = {
- // 0 1 2 3
+ public static int posToOrientation(int position) {
+ Preconditions.checkArgument(0 <= position && position < 4);
+ return POS_TO_ORIENTATION[position];
+ }
+
+ /** Mapping from cell orientation + Hilbert traversal to IJ-index. */
+ private static final int[][] POS_TO_IJ = {
+ // 0 1 2 3
{0, 1, 3, 2}, // canonical order: (0,0), (0,1), (1,1), (1,0)
{0, 2, 3, 1}, // axes swapped: (0,0), (1,0), (1,1), (0,1)
{3, 2, 0, 1}, // bits inverted: (1,1), (1,0), (0,0), (0,1)
@@ -89,6 +93,49 @@ public final strictfp class S2 {
};
/**
+ * Return the IJ-index of the subcell at the given position in the Hilbert
+ * curve traversal with the given orientation. This is the inverse of
+ * {@link #ijToPos}.
+ *
+ * @param orientation the subcell orientation, in the range [0,3].
+ * @param position the position of the subcell in the Hilbert traversal, in
+ * the range [0,3].
+ * @return the IJ-index where {@code 0->(0,0), 1->(0,1), 2->(1,0), 3->(1,1)}.
+ * @throws IllegalArgumentException if either parameter is out of bounds.
+ */
+ public static int posToIJ(int orientation, int position) {
+ Preconditions.checkArgument(0 <= orientation && orientation < 4);
+ Preconditions.checkArgument(0 <= position && position < 4);
+ return POS_TO_IJ[orientation][position];
+ }
+
+ /** Mapping from Hilbert traversal order + cell orientation to IJ-index. */
+ private static final int IJ_TO_POS[][] = {
+ // (0,0) (0,1) (1,0) (1,1)
+ {0, 1, 3, 2}, // canonical order
+ {0, 3, 1, 2}, // axes swapped
+ {2, 3, 1, 0}, // bits inverted
+ {2, 1, 3, 0}, // swapped & inverted
+ };
+
+ /**
+ * Returns the order in which a specified subcell is visited by the Hilbert
+ * curve. This is the inverse of {@link #posToIJ}.
+ *
+ * @param orientation the subcell orientation, in the range [0,3].
+ * @param ijIndex the subcell index where
+ * {@code 0->(0,0), 1->(0,1), 2->(1,0), 3->(1,1)}.
+ * @return the position of the subcell in the Hilbert traversal, in the range
+ * [0,3].
+ * @throws IllegalArgumentException if either parameter is out of bounds.
+ */
+ public static final int ijToPos(int orientation, int ijIndex) {
+ Preconditions.checkArgument(0 <= orientation && orientation < 4);
+ Preconditions.checkArgument(0 <= ijIndex && ijIndex < 4);
+ return IJ_TO_POS[orientation][ijIndex];
+ }
+
+ /**
* Defines an area or a length cell metric.
*/
public static class Metric {
diff --git a/src/com/google/common/geometry/S2Cell.java b/src/com/google/common/geometry/S2Cell.java
index 26c7af1..dea2b4f 100644
--- a/src/com/google/common/geometry/S2Cell.java
+++ b/src/com/google/common/geometry/S2Cell.java
@@ -144,9 +144,9 @@ public final strictfp class S2Cell implements S2Region {
S2Cell child = children[pos];
child.face = face;
child.level = (byte) (level + 1);
- child.orientation = (byte) (orientation ^ S2.POS_TO_ORIENTATION[pos]);
+ child.orientation = (byte) (orientation ^ S2.posToOrientation(pos));
child.cellId = id;
- int ij = S2.POS_TO_IJ[orientation][pos];
+ int ij = S2.posToIJ(orientation, pos);
for (int d = 0; d < 2; ++d) {
// The dimension 0 index (i/u) is in bit 1 of ij.
int m = 1 - ((ij >> (1 - d)) & 1);
diff --git a/src/com/google/common/geometry/S2CellId.java b/src/com/google/common/geometry/S2CellId.java
index 4de0a59..00b93fe 100644
--- a/src/com/google/common/geometry/S2CellId.java
+++ b/src/com/google/common/geometry/S2CellId.java
@@ -944,15 +944,13 @@ public final strictfp class S2CellId implements Comparable<S2CellId> {
i <<= 1;
j <<= 1;
pos <<= 2;
- int[] r = S2.POS_TO_IJ[orientation];
- initLookupCell(level, i + (r[0] >>> 1), j + (r[0] & 1), origOrientation,
- pos, orientation ^ S2.POS_TO_ORIENTATION[0]);
- initLookupCell(level, i + (r[1] >>> 1), j + (r[1] & 1), origOrientation,
- pos + 1, orientation ^ S2.POS_TO_ORIENTATION[1]);
- initLookupCell(level, i + (r[2] >>> 1), j + (r[2] & 1), origOrientation,
- pos + 2, orientation ^ S2.POS_TO_ORIENTATION[2]);
- initLookupCell(level, i + (r[3] >>> 1), j + (r[3] & 1), origOrientation,
- pos + 3, orientation ^ S2.POS_TO_ORIENTATION[3]);
+ // Initialize each sub-cell recursively.
+ for (int subPos = 0; subPos < 4; subPos++) {
+ int ij = S2.posToIJ(orientation, subPos);
+ int orientationMask = S2.posToOrientation(subPos);
+ initLookupCell(level, i + (ij >>> 1), j + (ij & 1), origOrientation,
+ pos + subPos, orientation ^ orientationMask);
+ }
}
}
diff --git a/src/com/google/common/geometry/S2Projections.java b/src/com/google/common/geometry/S2Projections.java
index 0f366b1..ceeb3fc 100644
--- a/src/com/google/common/geometry/S2Projections.java
+++ b/src/com/google/common/geometry/S2Projections.java
@@ -214,25 +214,10 @@ public final strictfp class S2Projections {
S2_PROJECTION == Projections.S2_QUADRATIC_PROJECTION ? 1.44261527445268292 : // 1.443
0;
-
- public static final double MAX_DIAG_ASPECT = Math.sqrt(3); // 1.732
// This is the maximum diagonal aspect ratio over all cells at any level,
// where the diagonal aspect ratio of a cell is defined as the ratio of its
// longest diagonal length to its shortest diagonal length.
-
-
- // IJ_TO_POS[orientation][ij] -> pos
- //
- // Given a cell orientation and the (i,j)-index of a subcell (0=(0,0),
- // 1=(0,1), 2=(1,0), 3=(1,1)), return the order in which this subcell is
- // visited by the Hilbert curve (a position in the range [0..3]).
- public static final int IJ_TO_POS[][] = {
- // (0,0) (0,1) (1,0) (1,1)
- {0, 1, 3, 2}, // canonical order
- {0, 3, 1, 2}, // axes swapped
- {2, 3, 1, 0}, // bits inverted
- {2, 1, 3, 0}, // swapped & inverted
- };
+ public static final double MAX_DIAG_ASPECT = Math.sqrt(3); // 1.732
public static double stToUV(double s) {
switch (S2_PROJECTION) {
diff --git a/tests/com/google/common/geometry/S2CellIdTest.java b/tests/com/google/common/geometry/S2CellIdTest.java
index 456c542..9a959e7 100644
--- a/tests/com/google/common/geometry/S2CellIdTest.java
+++ b/tests/com/google/common/geometry/S2CellIdTest.java
@@ -144,7 +144,7 @@ public strictfp class S2CellIdTest extends GeometryTestCase {
MutableInteger childOrientation = new MutableInteger(0);
assertEquals(child.toFaceIJOrientation(i, j, childOrientation), face);
assertEquals(
- childOrientation.intValue(), orientation.intValue() ^ S2.POS_TO_ORIENTATION[pos]);
+ childOrientation.intValue(), orientation.intValue() ^ S2.posToOrientation(pos));
parentMap.put(child, parent);
expandCell(child, cells, parentMap);
diff --git a/tests/com/google/common/geometry/S2Test.java b/tests/com/google/common/geometry/S2Test.java
index 6b90661..5cf02e6 100644
--- a/tests/com/google/common/geometry/S2Test.java
+++ b/tests/com/google/common/geometry/S2Test.java
@@ -21,11 +21,12 @@ public strictfp class S2Test extends GeometryTestCase {
private static Logger logger = Logger.getLogger(S2Test.class.getName());
- static int swapAxes(int ij) {
+ // Test helper methods for testing the traversal order.
+ private static int swapAxes(int ij) {
return ((ij >> 1) & 1) + ((ij & 1) << 1);
}
- static int invertBits(int ij) {
+ private static int invertBits(int ij) {
return ij ^ 3;
}
@@ -33,18 +34,20 @@ public strictfp class S2Test extends GeometryTestCase {
for (int r = 0; r < 4; ++r) {
for (int i = 0; i < 4; ++i) {
// Check consistency with respect to swapping axes.
- assertEquals(
- S2Projections.IJ_TO_POS[r][i], S2Projections.IJ_TO_POS[r ^ S2.SWAP_MASK][swapAxes(i)]);
- assertEquals(S2.POS_TO_IJ[r][i], swapAxes(S2.POS_TO_IJ[r ^ S2.SWAP_MASK][i]));
+ assertEquals(S2.ijToPos(r, i),
+ S2.ijToPos(r ^ S2.SWAP_MASK, swapAxes(i)));
+ assertEquals(S2.posToIJ(r, i),
+ swapAxes(S2.posToIJ(r ^ S2.SWAP_MASK, i)));
// Check consistency with respect to reversing axis directions.
- assertEquals(S2Projections.IJ_TO_POS[r][i],
- S2Projections.IJ_TO_POS[r ^ S2.INVERT_MASK][invertBits(i)]);
- assertEquals(S2.POS_TO_IJ[r][i], invertBits(S2.POS_TO_IJ[r ^ S2.INVERT_MASK][i]));
+ assertEquals(S2.ijToPos(r, i),
+ S2.ijToPos(r ^ S2.INVERT_MASK, invertBits(i)));
+ assertEquals(S2.posToIJ(r, i),
+ invertBits(S2.posToIJ(r ^ S2.INVERT_MASK, i)));
// Check that the two tables are inverses of each other.
- assertEquals(S2Projections.IJ_TO_POS[r][S2.POS_TO_IJ[r][i]], i);
- assertEquals(S2.POS_TO_IJ[r][S2Projections.IJ_TO_POS[r][i]], i);
+ assertEquals(S2.ijToPos(r, S2.posToIJ(r, i)), i);
+ assertEquals(S2.posToIJ(r, S2.ijToPos(r, i)), i);
}
}
}