diff options
author | rileya@google.com <rileya@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2012-09-05 16:10:59 +0000 |
---|---|---|
committer | rileya@google.com <rileya@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2012-09-05 16:10:59 +0000 |
commit | 1f45e934b68a5985b2127ec871ff593c3bfc7c2e (patch) | |
tree | 8d413d8198f65dfba5764283e944728d6194e3aa /src/core/SkBBoxHierarchy.h | |
parent | d6bbbf8a831cc982cda9b91e84c5600c631af5b2 (diff) |
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
Diffstat (limited to 'src/core/SkBBoxHierarchy.h')
-rw-r--r-- | src/core/SkBBoxHierarchy.h | 53 |
1 files changed, 53 insertions, 0 deletions
diff --git a/src/core/SkBBoxHierarchy.h b/src/core/SkBBoxHierarchy.h new file mode 100644 index 0000000000..347871f87b --- /dev/null +++ b/src/core/SkBBoxHierarchy.h @@ -0,0 +1,53 @@ + +/* + * 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 SkBBoxHierarchy_DEFINED +#define SkBBoxHierarchy_DEFINED + +#include "SkRect.h" +#include "SkTDArray.h" + +/** + * Interface for a spatial data structure that associates user data pointers with axis-aligned + * bounding boxes, and allows efficient retrieval of intersections with query rectangles. + */ +class SkBBoxHierarchy { +public: + virtual ~SkBBoxHierarchy() { } + + /** + * Insert a data pointer and corresponding bounding box + * @param data The data pointer, may be NULL + * @param bounds The bounding box, should not be empty + * @param defer Whether or not it is acceptable to delay insertion of this element (building up + * an entire spatial data structure at once is often faster and produces better + * structures than repeated inserts) until flushDeferredInserts is called or the first + * search. + */ + virtual void insert(void* data, const SkIRect& bounds, bool defer = false) = 0; + + /** + * If any insertions have been deferred, this forces them to be inserted + */ + virtual void flushDeferredInserts() = 0; + + /** + * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query' + */ + virtual void search(const SkIRect& query, SkTDArray<void*>* results) = 0; + + virtual void clear() = 0; + + /** + * Gets the number of insertions + */ + virtual int getCount() const = 0; +}; + +#endif + |