SkRTree.h revision c22d1398089fdb95480fb3459b23e4931e4f5280
11f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 21f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com/* 31f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Copyright 2012 Google Inc. 41f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * 51f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Use of this source code is governed by a BSD-style license that can be 61f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * found in the LICENSE file. 71f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 81f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 91f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#ifndef SkRTree_DEFINED 101f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#define SkRTree_DEFINED 111f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 121f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#include "SkRect.h" 131f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#include "SkTDArray.h" 141f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#include "SkChunkAlloc.h" 151f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#include "SkBBoxHierarchy.h" 161f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 171f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com/** 181f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of 196c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com * bounding rectangles. 206c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com * 216c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com * Much like a B-Tree it maintains balance by enforcing minimum and maximum child counts, and 221f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * splitting nodes when they become overfull. Unlike B-trees, however, we're using spatial data; so 236c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com * there isn't a canonical ordering to use when choosing insertion locations and splitting 241f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * distributions. A variety of heuristics have been proposed for these problems; here, we're using 256c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com * something resembling an R*-tree, which attempts to minimize area and overlap during insertion, 261f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * and aims to minimize a combination of margin, overlap, and area when splitting. 271f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * 281f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * One detail that is thus far unimplemented that may improve tree quality is attempting to remove 291f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * and reinsert nodes when they become full, instead of immediately splitting (nodes that may have 301f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * been placed well early on may hurt the tree later when more nodes have been added; removing 311f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * and reinserting nodes generally helps reduce overlap and make a better tree). Deletion of nodes 321f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * is also unimplemented. 331f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * 341f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * For more details see: 351f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * 366c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree: 371f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * an efficient and robust access method for points and rectangles" 381f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * 391f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * It also supports bulk-loading from a batch of bounds and values; if you don't require the tree 401f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * to be usable in its intermediate states while it is being constructed, this is significantly 411f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * quicker than individual insertions and produces more consistent trees. 421f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 431f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comclass SkRTree : public SkBBoxHierarchy { 441f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.compublic: 454813458d89fb276680168848bd861b307cf83f51rileya@google.com SK_DECLARE_INST_COUNT(SkRTree) 461f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 471f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 481f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Create a new R-Tree with specified min/max child counts. 491f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * The child counts are valid iff: 501f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes) 511f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * - min < max 521f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * - min > 0 531f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * - max < SK_MaxU16 54b839f0f6a92db9bcdbf8aa8004f20b0c0000111crileya@google.com * If you have some prior information about the distribution of bounds you're expecting, you 55b839f0f6a92db9bcdbf8aa8004f20b0c0000111crileya@google.com * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to create 56b839f0f6a92db9bcdbf8aa8004f20b0c0000111crileya@google.com * better proportioned tiles of rectangles. 571f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 588c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1, 598c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com bool orderWhenBulkLoading = true); 601f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com virtual ~SkRTree(); 611f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 621f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 631f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately 641f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load 651f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * a large batch of nodes at once, which tends to be faster and produce a better tree). 661f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * @param data The data value 671f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * @param bounds The corresponding bounding box 681f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * @param defer Can this insert be deferred? (this may be ignored) 691f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 70c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE; 711f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 721f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 731f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * If any inserts have been deferred, this will add them into the tree 741f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 75c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual void flushDeferredInserts() SK_OVERRIDE; 761f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 771f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 781f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Given a query rectangle, populates the passed-in array with the elements it intersects 791f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 80c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE; 811f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 82c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual void clear() SK_OVERRIDE; 831f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com bool isEmpty() const { return 0 == fCount; } 84c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 85c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org /** 86c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * Gets the depth of the tree structure 87c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org */ 88c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual int getDepth() const SK_OVERRIDE { 89c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; 90c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org } 911f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 921f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 931f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * This gets the insertion count (rather than the node count) 941f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 95c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual int getCount() const SK_OVERRIDE { return fCount; } 961f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 974b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org virtual void rewindInserts() SK_OVERRIDE; 984b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org 991f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comprivate: 1001f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1011f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com struct Node; 1021f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1031f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 1041f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * A branch of the tree, this may contain a pointer to another interior node, or a data value 1051f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 1061f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com struct Branch { 1071f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com union { 1081f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Node* subtree; 1091f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com void* data; 1101f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } fChild; 1111f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkIRect fBounds; 1121f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com }; 1136c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com 1141f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 1151f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case) 1161f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 1171f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com struct Node { 1181f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com uint16_t fNumChildren; 1191f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com uint16_t fLevel; 1201f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com bool isLeaf() { return 0 == fLevel; } 1211f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // Since we want to be able to pick min/max child counts at runtime, we assume the creator 1221f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // has allocated sufficient space directly after us in memory, and index into that space 1231f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Branch* child(size_t index) { 1241f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return reinterpret_cast<Branch*>(this + 1) + index; 1251f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 1261f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com }; 1271f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1281f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com typedef int32_t SkIRect::*SortSide; 1291f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1301f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // Helper for sorting our children arrays by sides of their rects 131e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com struct RectLessThan { 132e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com RectLessThan(SkRTree::SortSide side) : fSide(side) { } 133e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) const { 134e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com return lhs.fBounds.*fSide < rhs.fBounds.*fSide; 135e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com } 136e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com private: 137e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com const SkRTree::SortSide fSide; 138e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com }; 139e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com 140e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com struct RectLessX { 141e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) { 142e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) < 143e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1); 144e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com } 145e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com }; 146e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com 147e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com struct RectLessY { 148e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) { 149e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) < 150e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1); 151e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com } 152e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com }; 1531f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1548c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading); 1551f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1561f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 1571f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Recursively descend the tree to find an insertion position for 'branch', updates 1581f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * bounding boxes on the way up. 1591f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 1601f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Branch* insert(Node* root, Branch* branch, uint16_t level = 0); 1611f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1621f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int chooseSubtree(Node* root, Branch* branch); 1631f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkIRect computeBounds(Node* n); 1641f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int distributeChildren(Branch* children); 1651f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com void search(Node* root, const SkIRect query, SkTDArray<void*>* results) const; 1661f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1671f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 1686c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this 1696c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com * seems to generally produce better, more consistent trees at significantly lower cost than 1701f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * repeated insertions. 1711f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * 1721f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * This consumes the input array. 1731f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * 1741f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant, 1751f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * which groups rects by position on the Hilbert curve, is probably worth a look). There also 1761f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc). 1771f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 1781f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); 1791f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1801f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com void validate(); 1811f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false); 1821f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1831f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com const int fMinChildren; 1841f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com const int fMaxChildren; 1851f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com const size_t fNodeSize; 1861f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1871f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // This is the count of data elements (rather than total nodes in the tree) 188adacc7067ad617cdc7bbef39192ca80f4b4d27f9robertphillips@google.com int fCount; 1891f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1901f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Branch fRoot; 1911f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkChunkAlloc fNodes; 1921f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkTDArray<Branch> fDeferredInserts; 193b839f0f6a92db9bcdbf8aa8004f20b0c0000111crileya@google.com SkScalar fAspectRatio; 1948c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com bool fSortWhenBulkLoading; 1951f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1961f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Node* allocateNode(uint16_t level); 1971f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1984813458d89fb276680168848bd861b307cf83f51rileya@google.com typedef SkBBoxHierarchy INHERITED; 1991f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com}; 2001f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 2011f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#endif 202