1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889 |
- /*
- * 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<int>* 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<int>* results) const;
- // Consumes the input array.
- Branch bulkLoad(SkTDArray<Branch>* 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<Node> fNodes;
- typedef SkBBoxHierarchy INHERITED;
- };
- #endif
|