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