15c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Copyright 2014 The Chromium Authors. All rights reserved. 25c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Use of this source code is governed by a BSD-style license that can be 35c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// found in the LICENSE file. 45c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 56d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)// Defines a hierarchical bounding rectangle data structure for Rect objects, 65c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// associated with a generic unique key K for efficient spatial queries. The 75c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// R*-tree algorithm is used to build the trees. Based on the papers: 85c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// 95c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// A Guttman 'R-trees: a dynamic index structure for spatial searching', Proc 105c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// ACM SIGMOD Int Conf on Management of Data, 47-57, 1984 115c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// 125c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// N Beckmann, H-P Kriegel, R Schneider, B Seeger 'The R*-tree: an efficient and 135c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// robust access method for points and rectangles', Proc ACM SIGMOD Int Conf on 145c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Management of Data, 322-331, 1990 156d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 166d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)#ifndef UI_GFX_GEOMETRY_R_TREE_H_ 176d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)#define UI_GFX_GEOMETRY_R_TREE_H_ 186d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 196d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)#include "r_tree_base.h" 206d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 216d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)namespace gfx { 226d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 236d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)template <typename Key> 246d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)class RTree : public RTreeBase { 255c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu public: 266d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) typedef base::hash_set<Key> Matches; 276d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 286d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // RTrees organize pairs of keys and rectangles in a hierarchical bounding 296d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // box structure. This allows for queries of the tree within logarithmic time. 306d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // |min_children| and |max_children| allows for adjustment of the average size 316d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // of the nodes within RTree, which adjusts the base of the logarithm in the 326d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // algorithm runtime. Some parts of insertion and deletion are polynomial 336d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // in the size of the individual node, so the trade-off with larger nodes is 346d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // potentially faster queries but slower insertions and deletions. Generally 356d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // it is worth considering how much overlap between rectangles of different 366d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // keys will occur in the tree, and trying to set |max_children| as a 376d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // reasonable upper bound to the number of overlapping rectangles expected. 386d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // Then |min_children| can bet set to a quantity slightly less than half of 396d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // that. 405c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu RTree(size_t min_children, size_t max_children); 415c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu ~RTree(); 425c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 435c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu // Insert a new rect into the tree, associated with provided key. Note that if 446d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // |rect| is empty, the |key| will not actually be inserted. Duplicate keys 455c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu // overwrite old entries. 466d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) void Insert(const Rect& rect, Key key); 475c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 486d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // If present, remove the supplied |key| from the tree. 496d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) void Remove(Key key); 505c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 516d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // Fills |matches_out| with all keys having bounding rects intersecting 526d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // |query_rect|. 536d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) void AppendIntersectingRecords(const Rect& query_rect, 546d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) Matches* matches_out) const; 555c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 565c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu void Clear(); 575c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 585c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu private: 596d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) friend class RTreeTest; 606d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) friend class RTreeNodeTest; 615c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 626d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) class Record : public RecordBase { 636d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) public: 646d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) Record(const Rect& rect, const Key& key); 656d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) virtual ~Record(); 666d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) const Key& key() const { return key_; } 675c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 685c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu private: 696d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) Key key_; 705c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 716d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(Record); 726d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) }; 735c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 745c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu // A map of supplied keys to their Node representation within the RTree, for 755c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu // efficient retrieval of keys without requiring a bounding rect. 766d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) typedef base::hash_map<Key, Record*> RecordMap; 776d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) RecordMap record_map_; 785c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 795c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu DISALLOW_COPY_AND_ASSIGN(RTree); 805c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}; 815c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 826d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)template <typename Key> 836d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)RTree<Key>::RTree(size_t min_children, size_t max_children) 846d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) : RTreeBase(min_children, max_children) { 856d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)} 866d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 876d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)template <typename Key> 886d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)RTree<Key>::~RTree() { 896d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)} 906d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 916d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)template <typename Key> 926d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)void RTree<Key>::Insert(const Rect& rect, Key key) { 936d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) scoped_ptr<NodeBase> record; 946d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // Check if this key is already present in the tree. 956d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) typename RecordMap::iterator it(record_map_.find(key)); 966d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 976d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) if (it != record_map_.end()) { 986d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // We will re-use this node structure, regardless of re-insert or return. 996d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) Record* existing_record = it->second; 1006d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // If the new rect and the current rect are identical we can skip the rest 1016d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // of Insert() as nothing has changed. 1026d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) if (existing_record->rect() == rect) 1036d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) return; 1046d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1056d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // Remove the node from the tree in its current position. 1066d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) record = RemoveNode(existing_record); 1076d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1086d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) PruneRootIfNecessary(); 1096d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1106d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // If we are replacing this key with an empty rectangle we just remove the 1116d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // old node from the list and return, thus preventing insertion of empty 1126d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // rectangles into our spatial database. 1136d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) if (rect.IsEmpty()) { 1146d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) record_map_.erase(it); 1156d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) return; 1166d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) } 1176d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1186d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // Reset the rectangle to the new value. 1196d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) record->set_rect(rect); 1206d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) } else { 1216d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) if (rect.IsEmpty()) 1226d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) return; 1236d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1246d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) record.reset(new Record(rect, key)); 1256d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) record_map_.insert(std::make_pair(key, static_cast<Record*>(record.get()))); 1266d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) } 1276d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1286d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) int highest_reinsert_level = -1; 1296d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) InsertNode(record.Pass(), &highest_reinsert_level); 1306d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)} 1316d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1326d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)template <typename Key> 1336d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)void RTree<Key>::Clear() { 1346d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) record_map_.clear(); 1356d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) ResetRoot(); 1366d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)} 1376d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1386d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)template <typename Key> 1396d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)void RTree<Key>::Remove(Key key) { 1406d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // Search the map for the leaf parent that has the provided record. 1416d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) typename RecordMap::iterator it = record_map_.find(key); 1426d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) if (it == record_map_.end()) 1436d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) return; 1446d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1456d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) Record* record = it->second; 1466d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) record_map_.erase(it); 1476d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) RemoveNode(record); 1486d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1496d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // Lastly check the root. If it has only one non-leaf child, delete it and 1506d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) // replace it with its child. 1516d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) PruneRootIfNecessary(); 1526d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)} 1536d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1546d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)template <typename Key> 1556d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)void RTree<Key>::AppendIntersectingRecords( 1566d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) const Rect& query_rect, Matches* matches_out) const { 1576d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) RTreeBase::Records matching_records; 1586d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) root()->AppendIntersectingRecords(query_rect, &matching_records); 1596d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) for (RTreeBase::Records::const_iterator it = matching_records.begin(); 1606d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) it != matching_records.end(); 1616d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) ++it) { 1626d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) const Record* record = static_cast<const Record*>(*it); 1636d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) matches_out->insert(record->key()); 1646d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) } 1656d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)} 1666d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1676d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1686d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)// RTree::Record -------------------------------------------------------------- 1696d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1706d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)template <typename Key> 1716d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)RTree<Key>::Record::Record(const Rect& rect, const Key& key) 1726d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) : RecordBase(rect), 1736d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) key_(key) { 1746d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)} 1756d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1766d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)template <typename Key> 1776d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)RTree<Key>::Record::~Record() { 1786d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)} 1796d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 1805c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu} // namespace gfx 1815c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 1825c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#endif // UI_GFX_GEOMETRY_R_TREE_H_ 183