Add R-Tree data structure.

Review URL: https://codereview.appspot.com/6489055

git-svn-id: http://skia.googlecode.com/svn/trunk@5401 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 177 insertions, 0 deletions

diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
new file mode 100644
index 0000000000..c58fabfa37
--- /dev/null
+++ b/src/core/SkRTree.h
@@ -0,0 +1,177 @@
+
+/*
+ * 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 "SkRect.h"
+#include "SkTDArray.h"
+#include "SkChunkAlloc.h"
+#include "SkBBoxHierarchy.h"
+
+/**
+ * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
+ * bounding rectangles. 
+ * 
+ * Much like a B-Tree it maintains balance by enforcing minimum and maximum child counts, and 
+ * splitting nodes when they become overfull. Unlike B-trees, however, we're using spatial data; so
+ * there isn't a canonical ordering to use when choosing insertion locations and splitting 
+ * distributions. A variety of heuristics have been proposed for these problems; here, we're using
+ * something resembling an R*-tree, which attempts to minimize area and overlap during insertion, 
+ * and aims to minimize a combination of margin, overlap, and area when splitting.
+ *
+ * One detail that is thus far unimplemented that may improve tree quality is attempting to remove
+ * and reinsert nodes when they become full, instead of immediately splitting (nodes that may have
+ * been placed well early on may hurt the tree later when more nodes have been added; removing
+ * and reinserting nodes generally helps reduce overlap and make a better tree). Deletion of nodes
+ * is also unimplemented.
+ *
+ * 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"
+ *
+ * It also supports bulk-loading from a batch of bounds and values; if you don't require the tree
+ * to be usable in its intermediate states while it is being constructed, this is significantly
+ * quicker than individual insertions and produces more consistent trees.
+ */
+class SkRTree : public SkBBoxHierarchy {
+public:
+
+    /**
+     * Create a new R-Tree with specified min/max child counts.
+     * The child counts are valid iff:
+     * - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes)
+     * - min < max
+     * - min > 0
+     * - max < SK_MaxU16
+     */
+    static SkRTree* Create(int minChildren, int maxChildren);
+    virtual ~SkRTree();
+
+    /**
+     * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
+     * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
+     * a large batch of nodes at once, which tends to be faster and produce a better tree).
+     *  @param data The data value
+     *  @param bounds The corresponding bounding box
+     *  @param defer Can this insert be deferred? (this may be ignored)
+     */
+    virtual void insert(void* data, const SkIRect& bounds, bool defer = false);
+
+    /**
+     * If any inserts have been deferred, this will add them into the tree
+     */
+    virtual void flushDeferredInserts();
+
+    /**
+     * Given a query rectangle, populates the passed-in array with the elements it intersects
+     */
+    virtual void search(const SkIRect& query, SkTDArray<void*>* results);
+
+    virtual void clear();
+    bool isEmpty() const { return 0 == fCount; }
+    int getDepth() const { return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; }
+
+    /**
+     * This gets the insertion count (rather than the node count)
+     */
+    virtual int getCount() const { return fCount; }
+
+private:
+
+    struct Node;
+
+    /**
+     * A branch of the tree, this may contain a pointer to another interior node, or a data value
+     */
+    struct Branch {
+        union {
+            Node* subtree;
+            void* data;
+        } fChild;
+        SkIRect fBounds;
+    };
+    
+    /**
+     * A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case)
+     */
+    struct Node {
+        uint16_t fNumChildren;
+        uint16_t fLevel;
+        bool isLeaf() { return 0 == fLevel; }
+        // Since we want to be able to pick min/max child counts at runtime, we assume the creator
+        // has allocated sufficient space directly after us in memory, and index into that space
+        Branch* child(size_t index) {
+            return reinterpret_cast<Branch*>(this + 1) + index;
+        }
+    };
+
+    typedef int32_t SkIRect::*SortSide;
+
+    // Helper for sorting our children arrays by sides of their rects
+    static bool RectLessThan(SortSide const& side, const Branch lhs, const Branch rhs) {
+        return lhs.fBounds.*side < rhs.fBounds.*side;
+    }
+
+    static bool RectLessX(int&, const Branch lhs, const Branch rhs) {
+        return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) <
+               ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1);
+    }
+
+    static bool RectLessY(int&, const Branch lhs, const Branch rhs) {
+        return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
+               ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
+    }
+
+    SkRTree(int minChildren, int maxChildren);
+
+    /**
+     * Recursively descend the tree to find an insertion position for 'branch', updates
+     * bounding boxes on the way up.
+     */
+    Branch* insert(Node* root, Branch* branch, uint16_t level = 0);
+
+    int chooseSubtree(Node* root, Branch* branch);
+    SkIRect computeBounds(Node* n);
+    int distributeChildren(Branch* children);
+    void search(Node* root, const SkIRect query, SkTDArray<void*>* results) const;
+
+    /**
+     * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this 
+     * seems to generally produce better, more consistent trees at significantly lower cost than 
+     * repeated insertions.
+     *
+     * This consumes the input array.
+     *
+     * 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).
+     */
+    Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
+
+    void validate();
+    int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false);
+
+    const int fMinChildren;
+    const int fMaxChildren;
+    const size_t fNodeSize;
+
+    // This is the count of data elements (rather than total nodes in the tree)
+    size_t fCount;
+
+    Branch fRoot;
+    SkChunkAlloc fNodes;
+    SkTDArray<Branch> fDeferredInserts;
+
+    Node* allocateNode(uint16_t level);
+
+};
+
+#endif
+