blob: eb6acb20d83093dee8d22d90148180972b3f6919 [file] [log] [blame]
// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Defines a hierarchical bounding rectangle data structure for Rect objects,
// associated with a generic unique key K for efficient spatial queries. The
// R*-tree algorithm is used to build the trees. Based on the papers:
//
// A Guttman 'R-trees: a dynamic index structure for spatial searching', Proc
// ACM SIGMOD Int Conf on Management of Data, 47-57, 1984
//
// N Beckmann, H-P Kriegel, R Schneider, B Seeger 'The R*-tree: an efficient and
// robust access method for points and rectangles', Proc ACM SIGMOD Int Conf on
// Management of Data, 322-331, 1990
#ifndef COBALT_MATH_R_TREE_H_
#define COBALT_MATH_R_TREE_H_
#include "cobalt/math/r_tree_base.h"
#include "base/hash_tables.h"
namespace cobalt {
namespace math {
template <typename Key>
class RTree : public RTreeBase {
public:
typedef base::hash_set<Key> Matches;
// RTrees organize pairs of keys and rectangles in a hierarchical bounding
// box structure. This allows for queries of the tree within logarithmic time.
// |min_children| and |max_children| allows for adjustment of the average size
// of the nodes within RTree, which adjusts the base of the logarithm in the
// algorithm runtime. Some parts of insertion and deletion are polynomial
// in the size of the individual node, so the trade-off with larger nodes is
// potentially faster queries but slower insertions and deletions. Generally
// it is worth considering how much overlap between rectangles of different
// keys will occur in the tree, and trying to set |max_children| as a
// reasonable upper bound to the number of overlapping rectangles expected.
// Then |min_children| can bet set to a quantity slightly less than half of
// that.
RTree(size_t min_children, size_t max_children);
~RTree();
// Insert a new rect into the tree, associated with provided key. Note that if
// |rect| is empty, the |key| will not actually be inserted. Duplicate keys
// overwrite old entries.
void Insert(const Rect& rect, Key key);
// If present, remove the supplied |key| from the tree.
void Remove(Key key);
// Fills |matches_out| with all keys having bounding rects intersecting
// |query_rect|.
void AppendIntersectingRecords(const Rect& query_rect,
Matches* matches_out) const;
void Clear();
private:
friend class RTreeTest;
friend class RTreeNodeTest;
class Record : public RecordBase {
public:
Record(const Rect& rect, const Key& key);
virtual ~Record();
const Key& key() const { return key_; }
private:
Key key_;
DISALLOW_COPY_AND_ASSIGN(Record);
};
// A map of supplied keys to their Node representation within the RTree, for
// efficient retrieval of keys without requiring a bounding rect.
typedef base::hash_map<Key, Record*> RecordMap;
RecordMap record_map_;
DISALLOW_COPY_AND_ASSIGN(RTree);
};
template <typename Key>
RTree<Key>::RTree(size_t min_children, size_t max_children)
: RTreeBase(min_children, max_children) {}
template <typename Key>
RTree<Key>::~RTree() {}
template <typename Key>
void RTree<Key>::Insert(const Rect& rect, Key key) {
scoped_ptr<NodeBase> record;
// Check if this key is already present in the tree.
typename RecordMap::iterator it(record_map_.find(key));
if (it != record_map_.end()) {
// We will re-use this node structure, regardless of re-insert or return.
Record* existing_record = it->second;
// If the new rect and the current rect are identical we can skip the rest
// of Insert() as nothing has changed.
if (existing_record->rect() == rect) return;
// Remove the node from the tree in its current position.
record = RemoveNode(existing_record);
PruneRootIfNecessary();
// If we are replacing this key with an empty rectangle we just remove the
// old node from the list and return, thus preventing insertion of empty
// rectangles into our spatial database.
if (rect.IsEmpty()) {
record_map_.erase(it);
return;
}
// Reset the rectangle to the new value.
record->set_rect(rect);
} else {
if (rect.IsEmpty()) return;
record.reset(new Record(rect, key));
record_map_.insert(std::make_pair(key, static_cast<Record*>(record.get())));
}
int highest_reinsert_level = -1;
InsertNode(record.Pass(), &highest_reinsert_level);
}
template <typename Key>
void RTree<Key>::Clear() {
record_map_.clear();
ResetRoot();
}
template <typename Key>
void RTree<Key>::Remove(Key key) {
// Search the map for the leaf parent that has the provided record.
typename RecordMap::iterator it = record_map_.find(key);
if (it == record_map_.end()) return;
Record* record = it->second;
record_map_.erase(it);
RemoveNode(record);
// Lastly check the root. If it has only one non-leaf child, delete it and
// replace it with its child.
PruneRootIfNecessary();
}
template <typename Key>
void RTree<Key>::AppendIntersectingRecords(const Rect& query_rect,
Matches* matches_out) const {
RTreeBase::Records matching_records;
root()->AppendIntersectingRecords(query_rect, &matching_records);
for (RTreeBase::Records::const_iterator it = matching_records.begin();
it != matching_records.end(); ++it) {
const Record* record = static_cast<const Record*>(*it);
matches_out->insert(record->key());
}
}
// RTree::Record --------------------------------------------------------------
template <typename Key>
RTree<Key>::Record::Record(const Rect& rect, const Key& key)
: RecordBase(rect), key_(key) {}
template <typename Key>
RTree<Key>::Record::~Record() {}
} // namespace math
} // namespace cobalt
#endif // COBALT_MATH_R_TREE_H_