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();
key()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>
RTree(size_t min_children,size_t max_children)83 RTree<Key>::RTree(size_t min_children, size_t max_children)
84 : RTreeBase(min_children, max_children) {
85 }
86
87 template <typename Key>
~RTree()88 RTree<Key>::~RTree() {
89 }
90
91 template <typename Key>
Insert(const Rect & rect,Key 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>
Clear()133 void RTree<Key>::Clear() {
134 record_map_.clear();
135 ResetRoot();
136 }
137
138 template <typename Key>
Remove(Key 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>
AppendIntersectingRecords(const Rect & query_rect,Matches * matches_out)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>
Record(const Rect & rect,const Key & key)171 RTree<Key>::Record::Record(const Rect& rect, const Key& key)
172 : RecordBase(rect),
173 key_(key) {
174 }
175
176 template <typename Key>
~Record()177 RTree<Key>::Record::~Record() {
178 }
179
180 } // namespace gfx
181
182 #endif // UI_GFX_GEOMETRY_R_TREE_H_
183