1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkQuadTree.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,111 @@
1.4 +/*
1.5 + * Copyright 2014 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#ifndef SkQuadTree_DEFINED
1.12 +#define SkQuadTree_DEFINED
1.13 +
1.14 +#include "SkRect.h"
1.15 +#include "SkTDArray.h"
1.16 +#include "SkBBoxHierarchy.h"
1.17 +#include "SkTInternalSList.h"
1.18 +#include "SkTObjectPool.h"
1.19 +
1.20 +/**
1.21 + * A QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles
1.22 + * in which each internal node has exactly four children.
1.23 + *
1.24 + * For more details see:
1.25 + *
1.26 + * http://en.wikipedia.org/wiki/Quadtree
1.27 + */
1.28 +class SkQuadTree : public SkBBoxHierarchy {
1.29 +public:
1.30 + SK_DECLARE_INST_COUNT(SkQuadTree)
1.31 +
1.32 + /**
1.33 + * Quad tree constructor.
1.34 + * @param bounds The bounding box for the root of the quad tree.
1.35 + * giving the quad tree bounds that fall outside the root
1.36 + * bounds may result in pathological but correct behavior.
1.37 + */
1.38 + SkQuadTree(const SkIRect& bounds);
1.39 +
1.40 + virtual ~SkQuadTree();
1.41 +
1.42 + /**
1.43 + * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
1.44 + * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
1.45 + * a large batch of nodes at once, which tends to be faster and produce a better tree).
1.46 + * @param data The data value
1.47 + * @param bounds The corresponding bounding box
1.48 + * @param defer Can this insert be deferred? (this may be ignored)
1.49 + */
1.50 + virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;
1.51 +
1.52 + /**
1.53 + * If any inserts have been deferred, this will add them into the tree
1.54 + */
1.55 + virtual void flushDeferredInserts() SK_OVERRIDE;
1.56 +
1.57 + /**
1.58 + * Given a query rectangle, populates the passed-in array with the elements it intersects
1.59 + */
1.60 + virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
1.61 +
1.62 + virtual void clear() SK_OVERRIDE;
1.63 +
1.64 + /**
1.65 + * Gets the depth of the tree structure
1.66 + */
1.67 + virtual int getDepth() const SK_OVERRIDE;
1.68 +
1.69 + /**
1.70 + * This gets the insertion count (rather than the node count)
1.71 + */
1.72 + virtual int getCount() const SK_OVERRIDE { return fEntryCount; }
1.73 +
1.74 + virtual void rewindInserts() SK_OVERRIDE;
1.75 +
1.76 +private:
1.77 + struct Entry {
1.78 + Entry() : fData(NULL) {}
1.79 + SkIRect fBounds;
1.80 + void* fData;
1.81 + SK_DECLARE_INTERNAL_SLIST_INTERFACE(Entry);
1.82 + };
1.83 +
1.84 + static const int kChildCount = 4;
1.85 +
1.86 + struct Node {
1.87 + Node() {
1.88 + for (int index=0; index<kChildCount; ++index) {
1.89 + fChildren[index] = NULL;
1.90 + }
1.91 + }
1.92 + SkTInternalSList<Entry> fEntries;
1.93 + SkIRect fBounds;
1.94 + SkIPoint fSplitPoint; // Only valid if the node has children.
1.95 + Node* fChildren[kChildCount];
1.96 + SK_DECLARE_INTERNAL_SLIST_ADAPTER(Node, fChildren[0]);
1.97 + };
1.98 +
1.99 + SkTObjectPool<Entry> fEntryPool;
1.100 + SkTObjectPool<Node> fNodePool;
1.101 + int fEntryCount;
1.102 + Node* fRoot;
1.103 + SkTInternalSList<Entry> fDeferred;
1.104 +
1.105 + Node* pickChild(Node* node, const SkIRect& bounds) const;
1.106 + void insert(Node* node, Entry* entry);
1.107 + void search(Node* node, const SkIRect& query, SkTDArray<void*>* results) const;
1.108 + void clear(Node* node);
1.109 + int getDepth(Node* node) const;
1.110 +
1.111 + typedef SkBBoxHierarchy INHERITED;
1.112 +};
1.113 +
1.114 +#endif
