1 // Copyright 2014 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // Defines a hierarchical bounding rectangle data structure for Rect objects, 6 // associated with a generic unique key K for efficient spatial queries. The 7 // R*-tree algorithm is used to build the trees. Based on the papers: 8 // 9 // A Guttman 'R-trees: a dynamic index structure for spatial searching', Proc 10 // ACM SIGMOD Int Conf on Management of Data, 47-57, 1984 11 // 12 // N Beckmann, H-P Kriegel, R Schneider, B Seeger 'The R*-tree: an efficient and 13 // robust access method for points and rectangles', Proc ACM SIGMOD Int Conf on 14 // Management of Data, 322-331, 1990 15 16 #ifndef UI_GFX_GEOMETRY_R_TREE_H_ 17 #define UI_GFX_GEOMETRY_R_TREE_H_ 18 19 #include "r_tree_base.h" 20 21 namespace gfx { 22 23 template <typename Key> 24 class RTree : public RTreeBase { 25 public: 26 typedef base::hash_set<Key> Matches; 27 28 // RTrees organize pairs of keys and rectangles in a hierarchical bounding 29 // box structure. This allows for queries of the tree within logarithmic time. 30 // |min_children| and |max_children| allows for adjustment of the average size 31 // of the nodes within RTree, which adjusts the base of the logarithm in the 32 // algorithm runtime. Some parts of insertion and deletion are polynomial 33 // in the size of the individual node, so the trade-off with larger nodes is 34 // potentially faster queries but slower insertions and deletions. Generally 35 // it is worth considering how much overlap between rectangles of different 36 // keys will occur in the tree, and trying to set |max_children| as a 37 // reasonable upper bound to the number of overlapping rectangles expected. 38 // Then |min_children| can bet set to a quantity slightly less than half of 39 // that. 40 RTree(size_t min_children, size_t max_children); 41 ~RTree(); 42 43 // Insert a new rect into the tree, associated with provided key. Note that if 44 // |rect| is empty, the |key| will not actually be inserted. Duplicate keys 45 // overwrite old entries. 46 void Insert(const Rect& rect, Key key); 47 48 // If present, remove the supplied |key| from the tree. 49 void Remove(Key key); 50 51 // Fills |matches_out| with all keys having bounding rects intersecting 52 // |query_rect|. 53 void AppendIntersectingRecords(const Rect& query_rect, 54 Matches* matches_out) const; 55 56 void Clear(); 57 58 private: 59 friend class RTreeTest; 60 friend class RTreeNodeTest; 61 62 class Record : public RecordBase { 63 public: 64 Record(const Rect& rect, const Key& key); 65 virtual ~Record(); 66 const Key& key() const { return key_; } 67 68 private: 69 Key key_; 70 71 DISALLOW_COPY_AND_ASSIGN(Record); 72 }; 73 74 // A map of supplied keys to their Node representation within the RTree, for 75 // efficient retrieval of keys without requiring a bounding rect. 76 typedef base::hash_map<Key, Record*> RecordMap; 77 RecordMap record_map_; 78 79 DISALLOW_COPY_AND_ASSIGN(RTree); 80 }; 81 82 template <typename Key> 83 RTree<Key>::RTree(size_t min_children, size_t max_children) 84 : RTreeBase(min_children, max_children) { 85 } 86 87 template <typename Key> 88 RTree<Key>::~RTree() { 89 } 90 91 template <typename Key> 92 void RTree<Key>::Insert(const Rect& rect, Key key) { 93 scoped_ptr<NodeBase> record; 94 // Check if this key is already present in the tree. 95 typename RecordMap::iterator it(record_map_.find(key)); 96 97 if (it != record_map_.end()) { 98 // We will re-use this node structure, regardless of re-insert or return. 99 Record* existing_record = it->second; 100 // If the new rect and the current rect are identical we can skip the rest 101 // of Insert() as nothing has changed. 102 if (existing_record->rect() == rect) 103 return; 104 105 // Remove the node from the tree in its current position. 106 record = RemoveNode(existing_record); 107 108 PruneRootIfNecessary(); 109 110 // If we are replacing this key with an empty rectangle we just remove the 111 // old node from the list and return, thus preventing insertion of empty 112 // rectangles into our spatial database. 113 if (rect.IsEmpty()) { 114 record_map_.erase(it); 115 return; 116 } 117 118 // Reset the rectangle to the new value. 119 record->set_rect(rect); 120 } else { 121 if (rect.IsEmpty()) 122 return; 123 124 record.reset(new Record(rect, key)); 125 record_map_.insert(std::make_pair(key, static_cast<Record*>(record.get()))); 126 } 127 128 int highest_reinsert_level = -1; 129 InsertNode(record.Pass(), &highest_reinsert_level); 130 } 131 132 template <typename Key> 133 void RTree<Key>::Clear() { 134 record_map_.clear(); 135 ResetRoot(); 136 } 137 138 template <typename Key> 139 void RTree<Key>::Remove(Key key) { 140 // Search the map for the leaf parent that has the provided record. 141 typename RecordMap::iterator it = record_map_.find(key); 142 if (it == record_map_.end()) 143 return; 144 145 Record* record = it->second; 146 record_map_.erase(it); 147 RemoveNode(record); 148 149 // Lastly check the root. If it has only one non-leaf child, delete it and 150 // replace it with its child. 151 PruneRootIfNecessary(); 152 } 153 154 template <typename Key> 155 void RTree<Key>::AppendIntersectingRecords( 156 const Rect& query_rect, Matches* matches_out) const { 157 RTreeBase::Records matching_records; 158 root()->AppendIntersectingRecords(query_rect, &matching_records); 159 for (RTreeBase::Records::const_iterator it = matching_records.begin(); 160 it != matching_records.end(); 161 ++it) { 162 const Record* record = static_cast<const Record*>(*it); 163 matches_out->insert(record->key()); 164 } 165 } 166 167 168 // RTree::Record -------------------------------------------------------------- 169 170 template <typename Key> 171 RTree<Key>::Record::Record(const Rect& rect, const Key& key) 172 : RecordBase(rect), 173 key_(key) { 174 } 175 176 template <typename Key> 177 RTree<Key>::Record::~Record() { 178 } 179 180 } // namespace gfx 181 182 #endif // UI_GFX_GEOMETRY_R_TREE_H_ 183
