diff options
author | Siyuan Zhou <siyuan.zhou@mongodb.com> | 2014-10-29 15:33:55 -0400 |
---|---|---|
committer | Siyuan Zhou <siyuan.zhou@mongodb.com> | 2014-10-30 15:37:47 -0400 |
commit | f5090f81588b684fc3cd27200ae6a822f16c37ae (patch) | |
tree | f6336bb8ab45d5cfc6bd052624038726bd478842 /src/mongo/db/geo | |
parent | 4f95fb4b9131e2bea07be0cf8257c2059a063c3e (diff) | |
download | mongo-f5090f81588b684fc3cd27200ae6a822f16c37ae.tar.gz |
SERVER-15562 Search neighbors for density estimation with 2d index
Diffstat (limited to 'src/mongo/db/geo')
-rw-r--r-- | src/mongo/db/geo/hash.cpp | 63 | ||||
-rw-r--r-- | src/mongo/db/geo/hash.h | 9 | ||||
-rw-r--r-- | src/mongo/db/geo/hash_test.cpp | 84 |
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")); + } } |