Initial QuadTree implementation

src/core/SkQuadTree.cpp

+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkQuadTree.h"
+#include "SkTSort.h"
+#include <stdio.h>
+#include <vector>
+
+class SkQuadTree::QuadTree {

[Justin Novosad, 2014/01/28 21:26:13]

I find SkQuadTree vs. QuadTree confusing.  Why is this separated into two
classes? I don<t see why we would need an internal class given that the header
is not public.

[sugoi1, 2014/01/29 15:29:08]

Renamed to QuadTreeNode

+public:
+    QuadTree(const SkIRect& boundary)
+     : fBoundary(boundary)
+     , fNorthWest(NULL)

[Justin Novosad, 2014/01/28 21:26:13]

We use top/left/right/bottom in skia.

[sugoi1, 2014/01/29 15:29:08]

Done.

+     , fNorthEast(NULL)
+     , fSouthWest(NULL)
+     , fSouthEast(NULL)
+     , fCanSubdivide((fBoundary.width() * fBoundary.height()) > 0) {}
+
+    ~QuadTree() {
+        clear();
+    }
+    
+    void clear() {
+        SkDELETE(fNorthWest);
+        fNorthWest = NULL;
+        SkDELETE(fNorthEast);
+        fNorthEast = NULL;
+        SkDELETE(fSouthWest);
+        fSouthWest = NULL;
+        SkDELETE(fSouthEast);
+        fSouthEast = NULL;
+        fData.reset();
+    }
+
+    const SkIRect& getBoundary() const { return fBoundary; }

[Justin Novosad, 2014/01/28 21:26:13]

Bondary -> Bounds, to be consistent with rest of skia

[sugoi1, 2014/01/29 15:29:08]

Done.

+
+    // Insert data into the QuadTree
+    bool insert(SkQuadTree::Data& data) {
+        // Ignore objects which do not belong in this quad tree
+        return data.fInnerBounds.intersect(fBoundary) && doInsert(data);
+    }
+
+    // Find all data which appear within a range
+    void queryRange(const SkIRect& range, SkTDArray<void*>* dataInRange) const {
+        // Automatically abort if the range does not collide with this quad
+        if (!SkIRect::Intersects(fBoundary, range)) {
+            return; // nothing added to the list
+        }
+
+        // Check objects at this quad level
+        for (int p = 0; p < fData.count(); ++p) {
+            if (SkIRect::Intersects(fData[p].fBounds, range)) {
+                dataInRange->push(fData[p].fData);
+            }
+        }
+
+        // Terminate here, if there are no children
+        if (!hasChildren()) {
+            return;
+        }
+
+        // Otherwise, add the data from the children
+        fNorthWest->queryRange(range, dataInRange);
+        fNorthEast->queryRange(range, dataInRange);
+        fSouthWest->queryRange(range, dataInRange);
+        fSouthEast->queryRange(range, dataInRange);
+    }
+
+    int getDepth(int i = 1) const {
+        if (hasChildren()) {
+            int depthNW = fNorthWest->getDepth(++i);
+            int depthNE = fNorthWest->getDepth(i);
+            int depthSW = fNorthWest->getDepth(i);
+            int depthSE = fNorthWest->getDepth(i);
+            return SkTMax(SkTMax(depthNW, depthNE), SkTMax(depthSW, depthSE));
+        }
+        return i;
+    }
+
+private:
+    // create four children which fully divide this quad into four quads of equal area
+    void subdivide() {
+        if (!hasChildren() && fCanSubdivide) {
+            SkPoint center = SkPoint::Make(fBoundary.centerX(), fBoundary.centerY());
+            fNorthWest = SkNEW_ARGS(QuadTree, (SkIRect::MakeLTRB(
+                fBoundary.fLeft, fBoundary.fTop, center.fX, center.fY)));
+            fNorthEast = SkNEW_ARGS(QuadTree, (SkIRect::MakeLTRB(
+                center.fX, fBoundary.fTop, fBoundary.fRight, center.fY)));
+            fSouthWest = SkNEW_ARGS(QuadTree, (SkIRect::MakeLTRB(
+                fBoundary.fLeft, center.fY, center.fX, fBoundary.fBottom)));
+            fSouthEast = SkNEW_ARGS(QuadTree, (SkIRect::MakeLTRB(
+                center.fX, center.fY, fBoundary.fRight, fBoundary.fBottom)));
+
+            // If any of the data can fit entirely into a subregion, move it down now
+            for (int i = fData.count() - 1; i >= 0; --i) {
+                // If the data fits entirely into one of the 4 subregions, move that data
+                // down to that subregion.
+                if (fNorthWest->doInsert(fData[i]) ||
+                    fNorthEast->doInsert(fData[i]) ||
+                    fSouthWest->doInsert(fData[i]) ||
+                    fSouthEast->doInsert(fData[i])) {
+                    fData.remove(i);
+                }
+            }
+        }
+    }
+
+    bool doInsert(const SkQuadTree::Data& data) {
+        if (!fBoundary.contains(data.fInnerBounds)) {
+            return false;
+        }
+
+        if (fData.count() > QT_NODE_CAPACITY) {
+            subdivide();
+        }
+
+        // If there is space in this quad tree, add the object here
+        // If this quadtree can't be subdivided, we have no choice but to add it here
+        if ((fData.count() <= QT_NODE_CAPACITY) || !fCanSubdivide) {
+            if (fData.isEmpty()) {
+                fData.setReserve(QT_NODE_CAPACITY);
+            }
+            fData.push(data);
+        } else if (!fNorthWest->doInsert(data) && !fNorthEast->doInsert(data) &&
+                   !fSouthWest->doInsert(data) && !fSouthEast->doInsert(data)) {
+            // Can't be pushed down to children ? keep it here
+            fData.push(data);
+        }
+
+        return true;
+    }
+
+    bool hasChildren() const {
+        return (NULL != fNorthWest);
+    }
+
+    // Arbitrary constant to indicate how many elements can be stored in this quad tree node
+    static const int QT_NODE_CAPACITY = 4;
+
+    // Axis-aligned bounding box stored as a center with half-dimensions
+    // to represent the boundaries of this quad tree
+    SkIRect fBoundary;
+
+    // Data in this quad tree node
+    SkTDArray<SkQuadTree::Data> fData;
+
+    // Children
+    QuadTree* fNorthWest;
+    QuadTree* fNorthEast;
+    QuadTree* fSouthWest;
+    QuadTree* fSouthEast;
+    bool fCanSubdivide;
+};
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+SkQuadTree* SkQuadTree::Create(const SkIRect& bounds) {
+    return new SkQuadTree(bounds);
+}
+
+SkQuadTree::SkQuadTree(const SkIRect& bounds)
+    : fCount(0)
+    , fQuadTree(SkNEW_ARGS(QuadTree, (bounds))) {
+    SkASSERT((bounds.width() * bounds.height()) > 0);
+}
+
+SkQuadTree::~SkQuadTree() {
+}
+
+void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
+    if (bounds.isEmpty()) {
+        SkASSERT(false);
+        return;
+    }
+
+    SkQuadTree::Data quadTreeData(bounds, data);
+    fQuadTree->insert(quadTreeData);
+    ++fCount;
+}
+
+void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
+    SkASSERT(NULL != results);
+    fQuadTree->queryRange(query, results);
+}
+
+void SkQuadTree::clear() {
+    fCount = 0;
+    fQuadTree->clear();
+}
+
+int SkQuadTree::getDepth() const {
+    return fQuadTree->getDepth();
+}