1bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 2bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com/* 3bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * Copyright 2012 Google Inc. 4bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * 5bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * Use of this source code is governed by a BSD-style license that can be 6bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * found in the LICENSE file. 7bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com */ 8bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 9bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com#ifndef SkRTree_DEFINED 10bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com#define SkRTree_DEFINED 11bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 12bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com#include "SkRect.h" 13bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com#include "SkTDArray.h" 14bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com#include "SkChunkAlloc.h" 15bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com#include "SkBBoxHierarchy.h" 16bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 17bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com/** 18bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of 19c644d2934787bb3372813377f13441f9d59aa45bskia.committer@gmail.com * bounding rectangles. 20c644d2934787bb3372813377f13441f9d59aa45bskia.committer@gmail.com * 21c644d2934787bb3372813377f13441f9d59aa45bskia.committer@gmail.com * Much like a B-Tree it maintains balance by enforcing minimum and maximum child counts, and 22bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * splitting nodes when they become overfull. Unlike B-trees, however, we're using spatial data; so 23c644d2934787bb3372813377f13441f9d59aa45bskia.committer@gmail.com * there isn't a canonical ordering to use when choosing insertion locations and splitting 24bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * distributions. A variety of heuristics have been proposed for these problems; here, we're using 25c644d2934787bb3372813377f13441f9d59aa45bskia.committer@gmail.com * something resembling an R*-tree, which attempts to minimize area and overlap during insertion, 26bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * and aims to minimize a combination of margin, overlap, and area when splitting. 27bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * 28bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * One detail that is thus far unimplemented that may improve tree quality is attempting to remove 29bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * and reinsert nodes when they become full, instead of immediately splitting (nodes that may have 30bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * been placed well early on may hurt the tree later when more nodes have been added; removing 31bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * and reinserting nodes generally helps reduce overlap and make a better tree). Deletion of nodes 32bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * is also unimplemented. 33bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * 34bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * For more details see: 35bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * 36c644d2934787bb3372813377f13441f9d59aa45bskia.committer@gmail.com * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree: 37bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * an efficient and robust access method for points and rectangles" 38bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * 39bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * It also supports bulk-loading from a batch of bounds and values; if you don't require the tree 40bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * to be usable in its intermediate states while it is being constructed, this is significantly 41bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * quicker than individual insertions and produces more consistent trees. 42bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com */ 43bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.comclass SkRTree : public SkBBoxHierarchy { 44bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.compublic: 4501a73aa9cdc7d1ea2839d0636dbac7a7fc6f2112rileya@google.com SK_DECLARE_INST_COUNT(SkRTree) 46bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 47bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com /** 48bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * Create a new R-Tree with specified min/max child counts. 49bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * The child counts are valid iff: 50bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes) 51bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * - min < max 52bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * - min > 0 53bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * - max < SK_MaxU16 54baf86dcb12e3261a409dcb78f7518f87681148b0rileya@google.com * If you have some prior information about the distribution of bounds you're expecting, you 55baf86dcb12e3261a409dcb78f7518f87681148b0rileya@google.com * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to create 56baf86dcb12e3261a409dcb78f7518f87681148b0rileya@google.com * better proportioned tiles of rectangles. 57bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com */ 58baf86dcb12e3261a409dcb78f7518f87681148b0rileya@google.com static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1); 59bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com virtual ~SkRTree(); 60bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 61bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com /** 62bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately 63bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load 64bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * a large batch of nodes at once, which tends to be faster and produce a better tree). 65bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * @param data The data value 66bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * @param bounds The corresponding bounding box 67bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * @param defer Can this insert be deferred? (this may be ignored) 68bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com */ 69bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com virtual void insert(void* data, const SkIRect& bounds, bool defer = false); 70bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 71bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com /** 72bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * If any inserts have been deferred, this will add them into the tree 73bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com */ 74bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com virtual void flushDeferredInserts(); 75bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 76bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com /** 77bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * Given a query rectangle, populates the passed-in array with the elements it intersects 78bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com */ 79bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com virtual void search(const SkIRect& query, SkTDArray<void*>* results); 80bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 81bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com virtual void clear(); 82bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com bool isEmpty() const { return 0 == fCount; } 83bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com int getDepth() const { return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; } 84bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 85bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com /** 86bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * This gets the insertion count (rather than the node count) 87bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com */ 88bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com virtual int getCount() const { return fCount; } 89bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 9047c2076e9e3b4777af036acfa5ff258a38cca586commit-bot@chromium.org virtual void rewindInserts() SK_OVERRIDE; 9147c2076e9e3b4777af036acfa5ff258a38cca586commit-bot@chromium.org 92bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.comprivate: 93bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 94bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com struct Node; 95bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 96bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com /** 97bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * A branch of the tree, this may contain a pointer to another interior node, or a data value 98bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com */ 99bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com struct Branch { 100bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com union { 101bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com Node* subtree; 102bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com void* data; 103bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com } fChild; 104bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com SkIRect fBounds; 105bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com }; 106c644d2934787bb3372813377f13441f9d59aa45bskia.committer@gmail.com 107bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com /** 108bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case) 109bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com */ 110bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com struct Node { 111bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com uint16_t fNumChildren; 112bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com uint16_t fLevel; 113bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com bool isLeaf() { return 0 == fLevel; } 114bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com // Since we want to be able to pick min/max child counts at runtime, we assume the creator 115bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com // has allocated sufficient space directly after us in memory, and index into that space 116bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com Branch* child(size_t index) { 117bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com return reinterpret_cast<Branch*>(this + 1) + index; 118bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com } 119bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com }; 120bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 121bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com typedef int32_t SkIRect::*SortSide; 122bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 123bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com // Helper for sorting our children arrays by sides of their rects 1242e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com struct RectLessThan { 1252e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com RectLessThan(SkRTree::SortSide side) : fSide(side) { } 1262e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) const { 1272e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com return lhs.fBounds.*fSide < rhs.fBounds.*fSide; 1282e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com } 1292e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com private: 1302e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com const SkRTree::SortSide fSide; 1312e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com }; 1322e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com 1332e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com struct RectLessX { 1342e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) { 1352e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) < 1362e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1); 1372e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com } 1382e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com }; 1392e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com 1402e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com struct RectLessY { 1412e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) { 1422e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) < 1432e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1); 1442e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com } 1452e14b8660b0bffcdd105bcaf6fe14b88e4e096e2bungeman@google.com }; 146bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 147baf86dcb12e3261a409dcb78f7518f87681148b0rileya@google.com SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio); 148bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 149bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com /** 150bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * Recursively descend the tree to find an insertion position for 'branch', updates 151bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * bounding boxes on the way up. 152bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com */ 153bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com Branch* insert(Node* root, Branch* branch, uint16_t level = 0); 154bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 155bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com int chooseSubtree(Node* root, Branch* branch); 156bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com SkIRect computeBounds(Node* n); 157bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com int distributeChildren(Branch* children); 158bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com void search(Node* root, const SkIRect query, SkTDArray<void*>* results) const; 159bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 160bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com /** 161c644d2934787bb3372813377f13441f9d59aa45bskia.committer@gmail.com * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this 162c644d2934787bb3372813377f13441f9d59aa45bskia.committer@gmail.com * seems to generally produce better, more consistent trees at significantly lower cost than 163bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * repeated insertions. 164bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * 165bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * This consumes the input array. 166bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * 167bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant, 168bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * which groups rects by position on the Hilbert curve, is probably worth a look). There also 169bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc). 170bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com */ 171bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); 172bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 173bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com void validate(); 174bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false); 175bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 176bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com const int fMinChildren; 177bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com const int fMaxChildren; 178bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com const size_t fNodeSize; 179bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 180bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com // This is the count of data elements (rather than total nodes in the tree) 181bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com size_t fCount; 182bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 183bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com Branch fRoot; 184bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com SkChunkAlloc fNodes; 185bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com SkTDArray<Branch> fDeferredInserts; 186baf86dcb12e3261a409dcb78f7518f87681148b0rileya@google.com SkScalar fAspectRatio; 187bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 188bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com Node* allocateNode(uint16_t level); 189bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 19001a73aa9cdc7d1ea2839d0636dbac7a7fc6f2112rileya@google.com typedef SkBBoxHierarchy INHERITED; 191bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com}; 192bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com 193bc190873c7703a3c811f5e6e04d458af877ff52erileya@google.com#endif 194