11320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// Copyright 2014 The Chromium Authors. All rights reserved. 21320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// Use of this source code is governed by a BSD-style license that can be 31320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// found in the LICENSE file. 41320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 51320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// Defines a hierarchical bounding rectangle data structure for Rect objects, 61320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// associated with a generic unique key K for efficient spatial queries. The 71320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// R*-tree algorithm is used to build the trees. Based on the papers: 81320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 91320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// A Guttman 'R-trees: a dynamic index structure for spatial searching', Proc 101320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// ACM SIGMOD Int Conf on Management of Data, 47-57, 1984 111320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 121320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// N Beckmann, H-P Kriegel, R Schneider, B Seeger 'The R*-tree: an efficient and 131320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// robust access method for points and rectangles', Proc ACM SIGMOD Int Conf on 141320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// Management of Data, 322-331, 1990 151320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 161320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#ifndef UI_GFX_GEOMETRY_R_TREE_H_ 171320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#define UI_GFX_GEOMETRY_R_TREE_H_ 181320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 191320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "r_tree_base.h" 201320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 211320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccinamespace gfx { 221320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 231320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccitemplate <typename Key> 241320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciclass RTree : public RTreeBase { 251320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci public: 261320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci typedef base::hash_set<Key> Matches; 271320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 281320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // RTrees organize pairs of keys and rectangles in a hierarchical bounding 291320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // box structure. This allows for queries of the tree within logarithmic time. 301320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // |min_children| and |max_children| allows for adjustment of the average size 311320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // of the nodes within RTree, which adjusts the base of the logarithm in the 321320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // algorithm runtime. Some parts of insertion and deletion are polynomial 331320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // in the size of the individual node, so the trade-off with larger nodes is 341320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // potentially faster queries but slower insertions and deletions. Generally 351320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // it is worth considering how much overlap between rectangles of different 361320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // keys will occur in the tree, and trying to set |max_children| as a 371320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // reasonable upper bound to the number of overlapping rectangles expected. 381320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // Then |min_children| can bet set to a quantity slightly less than half of 391320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // that. 401320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci RTree(size_t min_children, size_t max_children); 411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci ~RTree(); 421320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 431320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // Insert a new rect into the tree, associated with provided key. Note that if 441320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // |rect| is empty, the |key| will not actually be inserted. Duplicate keys 451320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // overwrite old entries. 461320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void Insert(const Rect& rect, Key key); 471320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 481320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // If present, remove the supplied |key| from the tree. 491320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void Remove(Key key); 501320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 511320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // Fills |matches_out| with all keys having bounding rects intersecting 521320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // |query_rect|. 531320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void AppendIntersectingRecords(const Rect& query_rect, 541320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Matches* matches_out) const; 551320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 561320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void Clear(); 571320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 581320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci private: 591320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci friend class RTreeTest; 601320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci friend class RTreeNodeTest; 611320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 621320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci class Record : public RecordBase { 631320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci public: 641320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Record(const Rect& rect, const Key& key); 651320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci virtual ~Record(); 661320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const Key& key() const { return key_; } 671320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 681320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci private: 691320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Key key_; 701320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 711320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci DISALLOW_COPY_AND_ASSIGN(Record); 721320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci }; 731320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 741320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // A map of supplied keys to their Node representation within the RTree, for 751320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // efficient retrieval of keys without requiring a bounding rect. 761320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci typedef base::hash_map<Key, Record*> RecordMap; 771320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci RecordMap record_map_; 781320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 791320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci DISALLOW_COPY_AND_ASSIGN(RTree); 801320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci}; 811320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 821320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccitemplate <typename Key> 831320f92c476a1ad9d19dba2a48c72b75566198e9Primiano TucciRTree<Key>::RTree(size_t min_children, size_t max_children) 841320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci : RTreeBase(min_children, max_children) { 851320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 861320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 871320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccitemplate <typename Key> 881320f92c476a1ad9d19dba2a48c72b75566198e9Primiano TucciRTree<Key>::~RTree() { 891320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 901320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 91template <typename Key> 92void 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 132template <typename Key> 133void RTree<Key>::Clear() { 134 record_map_.clear(); 135 ResetRoot(); 136} 137 138template <typename Key> 139void 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 154template <typename Key> 155void 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 170template <typename Key> 171RTree<Key>::Record::Record(const Rect& rect, const Key& key) 172 : RecordBase(rect), 173 key_(key) { 174} 175 176template <typename Key> 177RTree<Key>::Record::~Record() { 178} 179 180} // namespace gfx 181 182#endif // UI_GFX_GEOMETRY_R_TREE_H_ 183