diff options
Diffstat (limited to 'src/mongo/db/geo/r2_region_coverer.cpp')
| -rw-r--r-- | src/mongo/db/geo/r2_region_coverer.cpp | 446 |
1 files changed, 221 insertions, 225 deletions
diff --git a/src/mongo/db/geo/r2_region_coverer.cpp b/src/mongo/db/geo/r2_region_coverer.cpp index b43db9665ad..3e49ab97099 100644 --- a/src/mongo/db/geo/r2_region_coverer.cpp +++ b/src/mongo/db/geo/r2_region_coverer.cpp @@ -36,250 +36,246 @@ namespace mongo { - // Definition - int const R2RegionCoverer::kDefaultMaxCells = 8; - - // Doesn't take ownership of "hashConverter". The caller should guarantee its life cycle - // is longer than this coverer. - R2RegionCoverer::R2RegionCoverer( GeoHashConverter* hashConverter ) : - _hashConverter( hashConverter ), - _minLevel( 0u ), - _maxLevel( GeoHash::kMaxBits ), - _maxCells( kDefaultMaxCells ), - _region( NULL ), - _candidateQueue( new CandidateQueue ), - _results( new vector<GeoHash> ) - { - } - - // Need to declare explicitly because of scoped pointers. - R2RegionCoverer::~R2RegionCoverer() { } - - void R2RegionCoverer::setMinLevel( unsigned int minLevel ) { - dassert(minLevel >= 0); - dassert(minLevel <= GeoHash::kMaxBits); - _minLevel = max(0u, min(GeoHash::kMaxBits, minLevel)); - } - - void R2RegionCoverer::setMaxLevel( unsigned int maxLevel ) { - dassert(maxLevel >= 0); - dassert(maxLevel <= GeoHash::kMaxBits); - _maxLevel = max(0u, min(GeoHash::kMaxBits, maxLevel)); - } - - void R2RegionCoverer::setMaxCells( int maxCells ) { - _maxCells = maxCells; - } - - void R2RegionCoverer::getCovering( const R2Region& region, vector<GeoHash>* cover ) { - // Strategy: Start with the full plane. Discard any - // that do not intersect the shape. Then repeatedly choose the - // largest cell that intersects the shape and subdivide it. - // - // _result contains the cells that will be part of the output, while the - // queue contains cells that we may still subdivide further. Cells that - // are entirely contained within the region are immediately added to the - // output, while cells that do not intersect the region are immediately - // discarded. Therefore the queue only contains cells that partially - // intersect the region. Candidates are prioritized first according to - // cell size (larger cells first), then by the number of intersecting - // children they have (fewest children first), and then by the number of - // fully contained children (fewest children first). - - verify(_minLevel <= _maxLevel); - dassert(_candidateQueue->empty()); - dassert(_results->empty()); - _region = ®ion; - - getInitialCandidates(); - - while(!_candidateQueue->empty()) { - Candidate* candidate = _candidateQueue->top().second; // Owned - _candidateQueue->pop(); - LOG(3) << "Pop: " << candidate->cell; - - // Try to expand this cell into its children - if (candidate->cell.getBits() < _minLevel || - candidate->numChildren == 1 || - (int)_results->size() + - (int)_candidateQueue->size() + - candidate->numChildren <= _maxCells) { - - for (int i = 0; i < candidate->numChildren; i++) { - addCandidate(candidate->children[i]); - } - deleteCandidate(candidate, false); - } else { - // Reached max cells. Move all candidates from the queue into results. - candidate->isTerminal = true; - addCandidate(candidate); +// Definition +int const R2RegionCoverer::kDefaultMaxCells = 8; + +// Doesn't take ownership of "hashConverter". The caller should guarantee its life cycle +// is longer than this coverer. +R2RegionCoverer::R2RegionCoverer(GeoHashConverter* hashConverter) + : _hashConverter(hashConverter), + _minLevel(0u), + _maxLevel(GeoHash::kMaxBits), + _maxCells(kDefaultMaxCells), + _region(NULL), + _candidateQueue(new CandidateQueue), + _results(new vector<GeoHash>) {} + +// Need to declare explicitly because of scoped pointers. +R2RegionCoverer::~R2RegionCoverer() {} + +void R2RegionCoverer::setMinLevel(unsigned int minLevel) { + dassert(minLevel >= 0); + dassert(minLevel <= GeoHash::kMaxBits); + _minLevel = max(0u, min(GeoHash::kMaxBits, minLevel)); +} + +void R2RegionCoverer::setMaxLevel(unsigned int maxLevel) { + dassert(maxLevel >= 0); + dassert(maxLevel <= GeoHash::kMaxBits); + _maxLevel = max(0u, min(GeoHash::kMaxBits, maxLevel)); +} + +void R2RegionCoverer::setMaxCells(int maxCells) { + _maxCells = maxCells; +} + +void R2RegionCoverer::getCovering(const R2Region& region, vector<GeoHash>* cover) { + // Strategy: Start with the full plane. Discard any + // that do not intersect the shape. Then repeatedly choose the + // largest cell that intersects the shape and subdivide it. + // + // _result contains the cells that will be part of the output, while the + // queue contains cells that we may still subdivide further. Cells that + // are entirely contained within the region are immediately added to the + // output, while cells that do not intersect the region are immediately + // discarded. Therefore the queue only contains cells that partially + // intersect the region. Candidates are prioritized first according to + // cell size (larger cells first), then by the number of intersecting + // children they have (fewest children first), and then by the number of + // fully contained children (fewest children first). + + verify(_minLevel <= _maxLevel); + dassert(_candidateQueue->empty()); + dassert(_results->empty()); + _region = ®ion; + + getInitialCandidates(); + + while (!_candidateQueue->empty()) { + Candidate* candidate = _candidateQueue->top().second; // Owned + _candidateQueue->pop(); + LOG(3) << "Pop: " << candidate->cell; + + // Try to expand this cell into its children + if (candidate->cell.getBits() < _minLevel || candidate->numChildren == 1 || + (int)_results->size() + (int)_candidateQueue->size() + candidate->numChildren <= + _maxCells) { + for (int i = 0; i < candidate->numChildren; i++) { + addCandidate(candidate->children[i]); } - LOG(3) << "Queue: " << _candidateQueue->size(); - } - - _region = NULL; - cover->swap(*_results); - } - - // Caller owns the returned pointer - R2RegionCoverer::Candidate* R2RegionCoverer::newCandidate( const GeoHash& cell ) { - // Exclude the cell that doesn't intersect with the geometry. - Box box = _hashConverter->unhashToBoxCovering(cell); - - if (_region->fastDisjoint(box)) { - return NULL; - } - - Candidate* candidate = new Candidate(); - candidate->cell = cell; - candidate->numChildren = 0; - // Stop subdivision when we reach the max level or there is no need to do so. - // Don't stop if we haven't reach min level. - candidate->isTerminal = cell.getBits() >= _minLevel && - (cell.getBits() >= _maxLevel || _region->fastContains(box)); - - return candidate; - } - - // Takes ownership of "candidate" - void R2RegionCoverer::addCandidate( Candidate* candidate ) { - if (candidate == NULL) return; - - if (candidate->isTerminal) { - _results->push_back(candidate->cell); - deleteCandidate(candidate, true); - return; - } - - verify(candidate->numChildren == 0); - - // Expand children - int numTerminals = expandChildren(candidate); - - if (candidate->numChildren == 0) { - deleteCandidate(candidate, true); - } else if (numTerminals == 4 && candidate->cell.getBits() >= _minLevel) { - // Optimization: add the parent cell rather than all of its children. + deleteCandidate(candidate, false); + } else { + // Reached max cells. Move all candidates from the queue into results. candidate->isTerminal = true; addCandidate(candidate); - } else { - // Add the cell into the priority queue for further subdivision. - // - // We negate the priority so that smaller absolute priorities are returned - // first. The heuristic is designed to refine the largest cells first, - // since those are where we have the largest potential gain. Among cells - // at the same level, we prefer the cells with the smallest number of - // intersecting children. Finally, we prefer cells that have the smallest - // number of children that cannot be refined any further. - int priority = -(((((int)candidate->cell.getBits() << 4) - + candidate->numChildren) << 4) - + numTerminals); - _candidateQueue->push(make_pair(priority, candidate)); // queue owns candidate - LOG(3) << "Push: " << candidate->cell << " (" << priority << ") "; } + LOG(3) << "Queue: " << _candidateQueue->size(); } - // Dones't take ownership of "candidate" - int R2RegionCoverer::expandChildren( Candidate* candidate ) { - GeoHash childCells[4]; - invariant(candidate->cell.subdivide(childCells)); - - int numTerminals = 0; - for (int i = 0; i < 4; ++i) { - Candidate* child = newCandidate(childCells[i]); - if (child) { - candidate->children[candidate->numChildren++] = child; - if (child->isTerminal) ++numTerminals; - } - } - return numTerminals; - } + _region = NULL; + cover->swap(*_results); +} - // Takes ownership of "candidate" - void R2RegionCoverer::deleteCandidate( Candidate* candidate, bool freeChildren ) { - if (freeChildren) { - for (int i = 0; i < candidate->numChildren; i++) { - deleteCandidate(candidate->children[i], true); - } - } +// Caller owns the returned pointer +R2RegionCoverer::Candidate* R2RegionCoverer::newCandidate(const GeoHash& cell) { + // Exclude the cell that doesn't intersect with the geometry. + Box box = _hashConverter->unhashToBoxCovering(cell); - delete candidate; + if (_region->fastDisjoint(box)) { + return NULL; } - void R2RegionCoverer::getInitialCandidates() { - // Add the full plane - // TODO a better initialization. - addCandidate(newCandidate(GeoHash())); + Candidate* candidate = new Candidate(); + candidate->cell = cell; + candidate->numChildren = 0; + // Stop subdivision when we reach the max level or there is no need to do so. + // Don't stop if we haven't reach min level. + candidate->isTerminal = + cell.getBits() >= _minLevel && (cell.getBits() >= _maxLevel || _region->fastContains(box)); + + return candidate; +} + +// Takes ownership of "candidate" +void R2RegionCoverer::addCandidate(Candidate* candidate) { + if (candidate == NULL) + return; + + if (candidate->isTerminal) { + _results->push_back(candidate->cell); + deleteCandidate(candidate, true); + return; } - // - // R2CellUnion - // - void R2CellUnion::init(const vector<GeoHash>& cellIds) { - _cellIds = cellIds; - normalize(); - } + verify(candidate->numChildren == 0); - bool R2CellUnion::contains(const GeoHash cellId) const { - // Since all cells are ordered, if an ancestor of id exists, it must be the previous one. - vector<GeoHash>::const_iterator it; - it = upper_bound(_cellIds.begin(), _cellIds.end(), cellId); // it > cellId - return it != _cellIds.begin() && (--it)->contains(cellId); // --it <= cellId - } + // Expand children + int numTerminals = expandChildren(candidate); - bool R2CellUnion::normalize() { - vector<GeoHash> output; - output.reserve(_cellIds.size()); - sort(_cellIds.begin(), _cellIds.end()); - - for (size_t i = 0; i < _cellIds.size(); i++) { - GeoHash id = _cellIds[i]; - - // Parent is less than children. If an ancestor of id exists, it must be the last one. - // - // Invariant: output doesn't contain intersected cells (ancestor and its descendants) - // Proof: Assume another cell "c" exists between ancestor "p" and the current "id", - // i.e. p < c < id, then "c" has "p" as its prefix, since id share the same prefix "p", - // so "p" contains "c", which conflicts with the invariant. - if (!output.empty() && output.back().contains(id)) continue; - - // Check whether the last 3 elements of "output" plus "id" can be - // collapsed into a single parent cell. - while (output.size() >= 3) { - // A necessary (but not sufficient) condition is that the XOR of the - // four cells must be zero. This is also very fast to test. - if ((output.end()[-3].getHash() ^ output.end()[-2].getHash() ^ output.back().getHash()) - != id.getHash()) - break; - - // Now we do a slightly more expensive but exact test. - GeoHash parent = id.parent(); - if (parent != output.end()[-3].parent() || - parent != output.end()[-2].parent() || - parent != output.end()[-1].parent()) - break; - - // Replace four children by their parent cell. - output.erase(output.end() - 3, output.end()); - id = parent; - } - output.push_back(id); + if (candidate->numChildren == 0) { + deleteCandidate(candidate, true); + } else if (numTerminals == 4 && candidate->cell.getBits() >= _minLevel) { + // Optimization: add the parent cell rather than all of its children. + candidate->isTerminal = true; + addCandidate(candidate); + } else { + // Add the cell into the priority queue for further subdivision. + // + // We negate the priority so that smaller absolute priorities are returned + // first. The heuristic is designed to refine the largest cells first, + // since those are where we have the largest potential gain. Among cells + // at the same level, we prefer the cells with the smallest number of + // intersecting children. Finally, we prefer cells that have the smallest + // number of children that cannot be refined any further. + int priority = -(((((int)candidate->cell.getBits() << 4) + candidate->numChildren) << 4) + + numTerminals); + _candidateQueue->push(make_pair(priority, candidate)); // queue owns candidate + LOG(3) << "Push: " << candidate->cell << " (" << priority << ") "; + } +} + +// Dones't take ownership of "candidate" +int R2RegionCoverer::expandChildren(Candidate* candidate) { + GeoHash childCells[4]; + invariant(candidate->cell.subdivide(childCells)); + + int numTerminals = 0; + for (int i = 0; i < 4; ++i) { + Candidate* child = newCandidate(childCells[i]); + if (child) { + candidate->children[candidate->numChildren++] = child; + if (child->isTerminal) + ++numTerminals; } - if (output.size() < _cellIds.size()) { - _cellIds.swap(output); - return true; + } + return numTerminals; +} + +// Takes ownership of "candidate" +void R2RegionCoverer::deleteCandidate(Candidate* candidate, bool freeChildren) { + if (freeChildren) { + for (int i = 0; i < candidate->numChildren; i++) { + deleteCandidate(candidate->children[i], true); } - return false; } - string R2CellUnion::toString() const { - std::stringstream ss; - ss << "[ "; - for (size_t i = 0; i < _cellIds.size(); i++) { - ss << _cellIds[i] << " "; + delete candidate; +} + +void R2RegionCoverer::getInitialCandidates() { + // Add the full plane + // TODO a better initialization. + addCandidate(newCandidate(GeoHash())); +} + +// +// R2CellUnion +// +void R2CellUnion::init(const vector<GeoHash>& cellIds) { + _cellIds = cellIds; + normalize(); +} + +bool R2CellUnion::contains(const GeoHash cellId) const { + // Since all cells are ordered, if an ancestor of id exists, it must be the previous one. + vector<GeoHash>::const_iterator it; + it = upper_bound(_cellIds.begin(), _cellIds.end(), cellId); // it > cellId + return it != _cellIds.begin() && (--it)->contains(cellId); // --it <= cellId +} + +bool R2CellUnion::normalize() { + vector<GeoHash> output; + output.reserve(_cellIds.size()); + sort(_cellIds.begin(), _cellIds.end()); + + for (size_t i = 0; i < _cellIds.size(); i++) { + GeoHash id = _cellIds[i]; + + // Parent is less than children. If an ancestor of id exists, it must be the last one. + // + // Invariant: output doesn't contain intersected cells (ancestor and its descendants) + // Proof: Assume another cell "c" exists between ancestor "p" and the current "id", + // i.e. p < c < id, then "c" has "p" as its prefix, since id share the same prefix "p", + // so "p" contains "c", which conflicts with the invariant. + if (!output.empty() && output.back().contains(id)) + continue; + + // Check whether the last 3 elements of "output" plus "id" can be + // collapsed into a single parent cell. + while (output.size() >= 3) { + // A necessary (but not sufficient) condition is that the XOR of the + // four cells must be zero. This is also very fast to test. + if ((output.end()[-3].getHash() ^ output.end()[-2].getHash() ^ + output.back().getHash()) != id.getHash()) + break; + + // Now we do a slightly more expensive but exact test. + GeoHash parent = id.parent(); + if (parent != output.end()[-3].parent() || parent != output.end()[-2].parent() || + parent != output.end()[-1].parent()) + break; + + // Replace four children by their parent cell. + output.erase(output.end() - 3, output.end()); + id = parent; } - ss << "]"; - return ss.str(); + output.push_back(id); + } + if (output.size() < _cellIds.size()) { + _cellIds.swap(output); + return true; + } + return false; +} + +string R2CellUnion::toString() const { + std::stringstream ss; + ss << "[ "; + for (size_t i = 0; i < _cellIds.size(); i++) { + ss << _cellIds[i] << " "; } + ss << "]"; + return ss.str(); +} } /* namespace mongo */ |