Line data    Source code

       1             : /*
       2             :  * Copyright 2012 Google Inc.
       3             :  *
       4             :  * Use of this source code is governed by a BSD-style license that can be
       5             :  * found in the LICENSE file.
       6             :  */
       7             : 
       8             : #ifndef SkRTree_DEFINED
       9             : #define SkRTree_DEFINED
      10             : 
      11             : #include "SkBBoxHierarchy.h"
      12             : #include "SkRect.h"
      13             : #include "SkTDArray.h"
      14             : 
      15             : /**
      16             :  * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
      17             :  * bounding rectangles.
      18             :  *
      19             :  * It only supports bulk-loading, i.e. creation from a batch of bounding rectangles.
      20             :  * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm.
      21             :  *
      22             :  * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
      23             :  * which groups rects by position on the Hilbert curve, is probably worth a look). There also
      24             :  * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
      25             :  *
      26             :  * For more details see:
      27             :  *
      28             :  *  Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree:
      29             :  *      an efficient and robust access method for points and rectangles"
      30             :  */
      31             : class SkRTree : public SkBBoxHierarchy {
      32             : public:
      33             : 
      34             : 
      35             :     /**
      36             :      * If you have some prior information about the distribution of bounds you're expecting, you
      37             :      * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to
      38             :      * create better proportioned tiles of rectangles.
      39             :      */
      40             :     explicit SkRTree(SkScalar aspectRatio = 1);
      41           0 :     ~SkRTree() override {}
      42             : 
      43             :     void insert(const SkRect[], int N) override;
      44             :     void search(const SkRect& query, SkTDArray<int>* results) const override;
      45             :     size_t bytesUsed() const override;
      46             : 
      47             :     // Methods and constants below here are only public for tests.
      48             : 
      49             :     // Return the depth of the tree structure.
      50             :     int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; }
      51             :     // Insertion count (not overall node count, which may be greater).
      52             :     int getCount() const { return fCount; }
      53             : 
      54             :     // Get the root bound.
      55             :     SkRect getRootBound() const override;
      56             : 
      57             :     // These values were empirically determined to produce reasonable performance in most cases.
      58             :     static const int kMinChildren = 6,
      59             :                      kMaxChildren = 11;
      60             : 
      61             : private:
      62             :     struct Node;
      63             : 
      64             :     struct Branch {
      65             :         union {
      66             :             Node* fSubtree;
      67             :             int fOpIndex;
      68             :         };
      69             :         SkRect fBounds;
      70             :     };
      71             : 
      72             :     struct Node {
      73             :         uint16_t fNumChildren;
      74             :         uint16_t fLevel;
      75             :         Branch fChildren[kMaxChildren];
      76             :     };
      77             : 
      78             :     void search(Node* root, const SkRect& query, SkTDArray<int>* results) const;
      79             : 
      80             :     // Consumes the input array.
      81             :     Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
      82             : 
      83             :     // How many times will bulkLoad() call allocateNodeAtLevel()?
      84             :     static int CountNodes(int branches, SkScalar aspectRatio);
      85             : 
      86             :     Node* allocateNodeAtLevel(uint16_t level);
      87             : 
      88             :     // This is the count of data elements (rather than total nodes in the tree)
      89             :     int fCount;
      90             :     SkScalar fAspectRatio;
      91             :     Branch fRoot;
      92             :     SkTDArray<Node> fNodes;
      93             : 
      94             :     typedef SkBBoxHierarchy INHERITED;
      95             : };
      96             : 
      97             : #endif