SkRTree.h 2.6 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
  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. #ifndef SkRTree_DEFINED
  8. #define SkRTree_DEFINED
  9. #include "include/core/SkRect.h"
  10. #include "include/private/SkTDArray.h"
  11. #include "src/core/SkBBoxHierarchy.h"
  12. /**
  13. * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
  14. * bounding rectangles.
  15. *
  16. * It only supports bulk-loading, i.e. creation from a batch of bounding rectangles.
  17. * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm.
  18. *
  19. * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
  20. * which groups rects by position on the Hilbert curve, is probably worth a look). There also
  21. * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
  22. *
  23. * For more details see:
  24. *
  25. * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree:
  26. * an efficient and robust access method for points and rectangles"
  27. */
  28. class SkRTree : public SkBBoxHierarchy {
  29. public:
  30. SkRTree();
  31. ~SkRTree() override {}
  32. void insert(const SkRect[], int N) override;
  33. void search(const SkRect& query, SkTDArray<int>* results) const override;
  34. size_t bytesUsed() const override;
  35. // Methods and constants below here are only public for tests.
  36. // Return the depth of the tree structure.
  37. int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; }
  38. // Insertion count (not overall node count, which may be greater).
  39. int getCount() const { return fCount; }
  40. // Get the root bound.
  41. SkRect getRootBound() const override;
  42. // These values were empirically determined to produce reasonable performance in most cases.
  43. static const int kMinChildren = 6,
  44. kMaxChildren = 11;
  45. private:
  46. struct Node;
  47. struct Branch {
  48. union {
  49. Node* fSubtree;
  50. int fOpIndex;
  51. };
  52. SkRect fBounds;
  53. };
  54. struct Node {
  55. uint16_t fNumChildren;
  56. uint16_t fLevel;
  57. Branch fChildren[kMaxChildren];
  58. };
  59. void search(Node* root, const SkRect& query, SkTDArray<int>* results) const;
  60. // Consumes the input array.
  61. Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
  62. // How many times will bulkLoad() call allocateNodeAtLevel()?
  63. static int CountNodes(int branches);
  64. Node* allocateNodeAtLevel(uint16_t level);
  65. // This is the count of data elements (rather than total nodes in the tree)
  66. int fCount;
  67. Branch fRoot;
  68. SkTDArray<Node> fNodes;
  69. typedef SkBBoxHierarchy INHERITED;
  70. };
  71. #endif