summaryrefslogtreecommitdiff
path: root/src/mongo/db/geo
diff options
context:
space:
mode:
Diffstat (limited to 'src/mongo/db/geo')
-rw-r--r--src/mongo/db/geo/hash.cpp63
-rw-r--r--src/mongo/db/geo/hash.h9
-rw-r--r--src/mongo/db/geo/hash_test.cpp84
3 files changed, 156 insertions, 0 deletions
diff --git a/src/mongo/db/geo/hash.cpp b/src/mongo/db/geo/hash.cpp
index ea481e14e14..6daf1e2744b 100644
--- a/src/mongo/db/geo/hash.cpp
+++ b/src/mongo/db/geo/hash.cpp
@@ -496,6 +496,69 @@ namespace mongo {
return GeoHash(_hash, _bits - 1);
}
+
+ void GeoHash::appendVertexNeighbors(unsigned level, vector<GeoHash>* output) const {
+ invariant(level >= 0 && level < _bits);
+
+ // Parent at the given level.
+ GeoHash parentHash = parent(level);
+ output->push_back(parentHash);
+
+ // Generate the neighbors of parent that are closest to me.
+ unsigned px, py, parentBits;
+ parentHash.unhash(&px, &py);
+ parentBits = parentHash.getBits();
+
+ // No Neighbors for the top level.
+ if (parentBits == 0U) return;
+
+ // Position in parent
+ // Y
+ // ^
+ // | 01, 11
+ // | 00, 10
+ // +----------> X
+ // We can guarantee _bits > 0.
+ long long posInParent = (_hash >> (64 - 2 * (parentBits + 1))) & 3LL;
+
+ // 1 bit at parent's level, the least significant bit of parent.
+ unsigned parentMask = 1U << (32 - parentBits);
+
+ // Along X Axis
+ if ((posInParent & 2LL) == 0LL) {
+ // Left side of parent, X - 1
+ if (!parentHash.atMinX()) output->push_back(GeoHash(px - parentMask, py, parentBits));
+ } else {
+ // Right side of parent, X + 1
+ if (!parentHash.atMaxX()) output->push_back(GeoHash(px + parentMask, py, parentBits));
+ }
+
+ // Along Y Axis
+ if ((posInParent & 1LL) == 0LL) {
+ // Bottom of parent, Y - 1
+ if (!parentHash.atMinY()) output->push_back(GeoHash(px, py - parentMask, parentBits));
+ } else {
+ // Top of parent, Y + 1
+ if (!parentHash.atMaxY()) output->push_back(GeoHash(px, py + parentMask, parentBits));
+ }
+
+ // Four corners
+ if (posInParent == 0LL) {
+ if (!parentHash.atMinX() && !parentHash.atMinY())
+ output->push_back(GeoHash(px - parentMask, py - parentMask, parentBits));
+ } else if (posInParent == 1LL) {
+ if (!parentHash.atMinX() && !parentHash.atMaxY())
+ output->push_back(GeoHash(px - parentMask, py + parentMask, parentBits));
+ } else if (posInParent == 2LL) {
+ if (!parentHash.atMaxX() && !parentHash.atMinY())
+ output->push_back(GeoHash(px + parentMask, py - parentMask, parentBits));
+ } else {
+ // PosInParent == 3LL
+ if (!parentHash.atMaxX() && !parentHash.atMaxY())
+ output->push_back(GeoHash(px + parentMask, py + parentMask, parentBits));
+ }
+ }
+
static BSONField<int> bitsField("bits", 26);
static BSONField<double> maxField("max", 180.0);
static BSONField<double> minField("min", -180.0);
diff --git a/src/mongo/db/geo/hash.h b/src/mongo/db/geo/hash.h
index dbd357983e9..51d299b0248 100644
--- a/src/mongo/db/geo/hash.h
+++ b/src/mongo/db/geo/hash.h
@@ -128,6 +128,15 @@ namespace mongo {
GeoHash parent(unsigned int level) const;
GeoHash parent() const;
+ // Return the neighbors of closest vertex to this cell at the given level,
+ // by appending them to "output". Normally there are four neighbors, but
+ // the closest vertex may only have two or one neighbor if it is next to the
+ // boundary.
+ //
+ // Requires: level < this->_bits, so that we can determine which vertex is
+ // closest (in particular, level == kMaxBits is not allowed).
+ void appendVertexNeighbors(unsigned level, vector<GeoHash>* output) const;
+
private:
// Create a hash from the provided string. Used by the std::string and char* cons.
diff --git a/src/mongo/db/geo/hash_test.cpp b/src/mongo/db/geo/hash_test.cpp
index 7534a2efc04..6b64e11ebe0 100644
--- a/src/mongo/db/geo/hash_test.cpp
+++ b/src/mongo/db/geo/hash_test.cpp
@@ -376,4 +376,88 @@ namespace {
mongo::Box box = converter.unhashToBoxCovering(hash);
ASSERT(box.inside(p));
}
+
+ TEST(GeoHash, NeighborsBasic) {
+ vector<GeoHash> neighbors;
+
+ // Top level
+ GeoHash hashAtLevel3("100001");
+ hashAtLevel3.appendVertexNeighbors(0u, &neighbors);
+ ASSERT_EQUALS(neighbors.size(), (size_t)1);
+ ASSERT_EQUALS(neighbors.front(), GeoHash(""));
+
+ // Level 1
+ neighbors.clear();
+ hashAtLevel3.appendVertexNeighbors(1u, &neighbors);
+ ASSERT_EQUALS(neighbors.size(), (size_t)2);
+ std::sort(neighbors.begin(), neighbors.end());
+ ASSERT_EQUALS(neighbors[0], GeoHash("00"));
+ ASSERT_EQUALS(neighbors[1], GeoHash("10"));
+
+ // Level 2
+ neighbors.clear();
+ hashAtLevel3.appendVertexNeighbors(2u, &neighbors);
+ ASSERT_EQUALS(neighbors.size(), (size_t)4);
+ std::sort(neighbors.begin(), neighbors.end());
+ ASSERT_EQUALS(neighbors[0], GeoHash("0010"));
+ ASSERT_EQUALS(neighbors[1], GeoHash("0011"));
+ ASSERT_EQUALS(neighbors[2], GeoHash("1000"));
+ ASSERT_EQUALS(neighbors[3], GeoHash("1001"));
+ }
+
+ TEST(GeoHash, NeighborsAtFinestLevel) {
+ std::vector<GeoHash> neighbors;
+
+ std::string zeroBase = "00000000000000000000000000000000000000000000000000000000";
+ // At finest level
+ GeoHash cellHash(zeroBase + "00011110");
+ neighbors.clear();
+ cellHash.appendVertexNeighbors(31u, &neighbors);
+ ASSERT_EQUALS(neighbors.size(), (size_t)4);
+ std::sort(neighbors.begin(), neighbors.end());
+ ASSERT_EQUALS(neighbors[0], GeoHash(zeroBase + "000110"));
+ ASSERT_EQUALS(neighbors[1], GeoHash(zeroBase + "000111"));
+ ASSERT_EQUALS(neighbors[2], GeoHash(zeroBase + "001100"));
+ ASSERT_EQUALS(neighbors[3], GeoHash(zeroBase + "001101"));
+
+ // Level 30
+ neighbors.clear();
+ cellHash.appendVertexNeighbors(30u, &neighbors);
+ ASSERT_EQUALS(neighbors.size(), (size_t)4);
+ std::sort(neighbors.begin(), neighbors.end());
+ ASSERT_EQUALS(neighbors[0], GeoHash(zeroBase + "0001"));
+ ASSERT_EQUALS(neighbors[1], GeoHash(zeroBase + "0011"));
+ ASSERT_EQUALS(neighbors[2], GeoHash(zeroBase + "0100"));
+ ASSERT_EQUALS(neighbors[3], GeoHash(zeroBase + "0110"));
+
+ // Level 29, only two neighbors including the parent.
+ // ^
+ // |
+ // +-+
+ // +-+
+ // +-+-------> x
+ neighbors.clear();
+ cellHash.appendVertexNeighbors(29u, &neighbors);
+ ASSERT_EQUALS(neighbors.size(), (size_t)2);
+ std::sort(neighbors.begin(), neighbors.end());
+ ASSERT_EQUALS(neighbors[0], GeoHash(zeroBase + "00"));
+ ASSERT_EQUALS(neighbors[1], GeoHash(zeroBase + "01"));
+
+ // Level 28, only one neighbor (the parent) at the left bottom corner.
+ // ^
+ // |
+ // +---+
+ // | |
+ // +---+-----> x
+ neighbors.clear();
+ cellHash.appendVertexNeighbors(28u, &neighbors);
+ ASSERT_EQUALS(neighbors.size(), (size_t)1);
+ ASSERT_EQUALS(neighbors[0], GeoHash(zeroBase));
+
+ // Level 1
+ neighbors.clear();
+ cellHash.appendVertexNeighbors(1u, &neighbors);
+ ASSERT_EQUALS(neighbors.size(), (size_t)1);
+ ASSERT_EQUALS(neighbors[0], GeoHash("00"));
+ }
}
View Lorry Controller Status