SkRTree Class Reference

#include <SkRTree.h>

Inheritance diagram for SkRTree:

Public Member Functions
	SkRTree ()
void	insert (const SkRect[], int N) override
void	search (const SkRect &query, std::vector< int > *results) const override
size_t	bytesUsed () const override
int	getDepth () const
int	getCount () const
Public Member Functions inherited from SkBBoxHierarchy
virtual void	insert (const SkRect[], const Metadata[], int N)
Public Member Functions inherited from SkRefCntBase
	SkRefCntBase ()
virtual	~SkRefCntBase ()
bool	unique () const
void	ref () const
void	unref () const

Static Public Attributes
static const int	kMinChildren = 6
static const int	kMaxChildren = 11

Additional Inherited Members
Protected Member Functions inherited from SkBBoxHierarchy
	SkBBoxHierarchy ()=default
	SkBBoxHierarchy (const SkBBoxHierarchy &)=delete
SkBBoxHierarchy &	operator= (const SkBBoxHierarchy &)=delete

Detailed Description

An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of bounding rectangles.

It only supports bulk-loading, i.e. creation from a batch of bounding rectangles. This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm.

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).

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"

Definition at line 34 of file SkRTree.h.

Constructor & Destructor Documentation

SkRTree()

SkRTree::SkRTree

(

)

Definition at line 13 of file SkRTree.cpp.

: fCount(0) {}

Member Function Documentation

bytesUsed()

size_t SkRTree::bytesUsed ( ) const

overridevirtual

Return approximate size in memory of *this.

Implements SkBBoxHierarchy.

Definition at line 165 of file SkRTree.cpp.

                                {
    size_t byteCount = sizeof(SkRTree);
 
    byteCount += fNodes.capacity() * sizeof(Node);
 
    return byteCount;
}

getCount()

int SkRTree::getCount ( ) const

inline

Definition at line 47 of file SkRTree.h.

{ return fCount; }

getDepth()

int SkRTree::getDepth ( ) const

inline

Definition at line 45 of file SkRTree.h.

{ return fCount ? fRoot.fSubtree->fLevel + 1 : 0; }

insert()

void SkRTree::insert ( const SkRect  [], int  N  )

overridevirtual

Insert N bounding boxes into the hierarchy.

Implements SkBBoxHierarchy.

Definition at line 15 of file SkRTree.cpp.

                                                      {
    SkASSERT(0 == fCount);
 
    std::vector<Branch> branches;
    branches.reserve(N);
 
    for (int i = 0; i < N; i++) {
        const SkRect& bounds = boundsArray[i];
        if (bounds.isEmpty()) {
            continue;
        }
 
        Branch b;
        b.fBounds = bounds;
        b.fOpIndex = i;
        branches.push_back(b);
    }
 
    fCount = (int)branches.size();
    if (fCount) {
        if (1 == fCount) {
            fNodes.reserve(1);
            Node* n = this->allocateNodeAtLevel(0);
            n->fNumChildren = 1;
            n->fChildren[0] = branches[0];
            fRoot.fSubtree = n;
            fRoot.fBounds  = branches[0].fBounds;
        } else {
            fNodes.reserve(CountNodes(fCount));
            fRoot = this->bulkLoad(&branches);
        }
    }
}

search()

void SkRTree::search ( const SkRect &  query, std::vector< int > *  results  ) const

overridevirtual

Populate results with the indices of bounding boxes intersecting that query.

Implements SkBBoxHierarchy.

Definition at line 147 of file SkRTree.cpp.

                                                                       {
    if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) {
        this->search(fRoot.fSubtree, query, results);
    }
}

Member Data Documentation

kMaxChildren

const int SkRTree::kMaxChildren = 11

static

Definition at line 51 of file SkRTree.h.

kMinChildren

const int SkRTree::kMinChildren = 6

static

Definition at line 50 of file SkRTree.h.

---

The documentation for this class was generated from the following files:

• third_party/skia/src/core/SkRTree.h
• third_party/skia/src/core/SkRTree.cpp