1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
// 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);
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 gfx
#endif // UI_GFX_GEOMETRY_R_TREE_H_
|
