Home | History | Annotate | Download | only in core 
      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     ~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
     98