| // 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 UI_GFX_GEOMETRY_R_TREE_H_ |
| #define UI_GFX_GEOMETRY_R_TREE_H_ |
| |
| #include "r_tree_base.h" |
| |
| namespace gfx { |
| |
| 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); |
| |
| // 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 gfx |
| |
| #endif // UI_GFX_GEOMETRY_R_TREE_H_ |