/* * Copyright 2012 Google Inc. * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #ifndef SkRTree_DEFINED #define SkRTree_DEFINED #include "include/core/SkRect.h" #include "include/private/SkTDArray.h" #include "src/core/SkBBoxHierarchy.h" /** * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of * bounding rectangles. * * It only supports bulk-loading, i.e. creation from a batch of bounding rectangles. * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm. * * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant, * which groups rects by position on the Hilbert curve, is probably worth a look). There also * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc). * * For more details see: * * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree: * an efficient and robust access method for points and rectangles" */ class SkRTree : public SkBBoxHierarchy { public: SkRTree(); ~SkRTree() override {} void insert(const SkRect[], int N) override; void search(const SkRect& query, SkTDArray* results) const override; size_t bytesUsed() const override; // Methods and constants below here are only public for tests. // Return the depth of the tree structure. int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; } // Insertion count (not overall node count, which may be greater). int getCount() const { return fCount; } // Get the root bound. SkRect getRootBound() const override; // These values were empirically determined to produce reasonable performance in most cases. static const int kMinChildren = 6, kMaxChildren = 11; private: struct Node; struct Branch { union { Node* fSubtree; int fOpIndex; }; SkRect fBounds; }; struct Node { uint16_t fNumChildren; uint16_t fLevel; Branch fChildren[kMaxChildren]; }; void search(Node* root, const SkRect& query, SkTDArray* results) const; // Consumes the input array. Branch bulkLoad(SkTDArray* branches, int level = 0); // How many times will bulkLoad() call allocateNodeAtLevel()? static int CountNodes(int branches); Node* allocateNodeAtLevel(uint16_t level); // This is the count of data elements (rather than total nodes in the tree) int fCount; Branch fRoot; SkTDArray fNodes; typedef SkBBoxHierarchy INHERITED; }; #endif