KoRTree< T > Class Template Reference

The KoRTree class is a template class that provides a R-tree. More...

#include <KoRTree.h>

Classes
class	LeafNode
class	Node
class	NonLeafNode

Public Member Functions
virtual void	clear ()
QList< T >	contained (const QRectF &point) const
	Find all data item which contain the point The items are sorted by insertion time in ascending order.
QList< T >	contains (const QPointF &point) const
	Find all data item which contain the point The items are sorted by insertion time in ascending order.
bool	contains (const T &data)
	Show if a shape is a part of the tree.
virtual void	insert (const QRectF &bb, const T &data)
	Insert data item into the tree.
virtual QList< T >	intersects (const QRectF &rect) const
	Find all data items which intersects rect The items are sorted by insertion time in ascending order.
QList< QRectF >	keys () const
	Find all data rectangles The order is NOT guaranteed to be the same as that used by values().
	KoRTree (int capacity, int minimum)
	Constructor.
void	remove (const T &data)
	Remove a data item from the tree.
QList< T >	values () const
	Find all data items The order is NOT guaranteed to be the same as that used by keys().
virtual	~KoRTree ()
	Destructor.

Protected Member Functions
virtual void	adjustTree (Node *node1, Node *node2)
virtual void	condenseTree (Node *node, QVector< Node * > &reinsert)
virtual LeafNode *	createLeafNode (int capacity, int level, Node *parent)
virtual NonLeafNode *	createNonLeafNode (int capacity, int level, Node *parent)
void	insert (Node *node)
void	insertHelper (const QRectF &bb, const T &data, int id)
QPair< int, int >	pickNext (Node *node, QVector< bool > &marker, Node *group1, Node *group2)
QPair< int, int >	pickSeeds (Node *node)
QPair< Node *, Node * >	splitNode (Node *node)

Protected Attributes
int	m_capacity
QMap< T, LeafNode * >	m_leafMap
int	m_minimum
Node *	m_root

Detailed Description

template<typename T>
class KoRTree< T >

The KoRTree class is a template class that provides a R-tree.

This class implements a R-tree as described in "R-TREES. A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING" by Antonin Guttman

It only supports 2 dimensional bounding boxes which are represented by a QRectF. For node splitting the Quadratic-Cost Algorithm is used as described by Guttman.

Definition at line 38 of file KoRTree.h.

Constructor & Destructor Documentation

KoRTree()

template<typename T >

KoRTree< T >::KoRTree	(	int	capacity,
		int	minimum )

Constructor.

Parameters

capacity	the capacity a node can take
minimum	the minimum filling of a node max 0.5 * capacity

Definition at line 342 of file KoRTree.h.

        : m_capacity(capacity)
        , m_minimum(minimum)
        , m_root(createLeafNode(m_capacity + 1, 0, 0))
{
    if (minimum > capacity / 2)
        qFatal("KoRTree::KoRTree minimum can be maximal capacity/2");
    //debugFlake << "root node " << m_root->nodeId();
}

~KoRTree()

template<typename T >

KoRTree< T >::~KoRTree ( )

virtual

Destructor.

Definition at line 353 of file KoRTree.h.

{
    delete m_root;
}

Member Function Documentation

adjustTree()

template<typename T >

void KoRTree< T >::adjustTree ( Node * node1, Node * node2 )

protectedvirtual

Definition at line 673 of file KoRTree.h.

{
    //debugFlake << "KoRTree::adjustTree";
    if (node1->isRoot()) {
        //debugFlake << "  root";
        if (node2) {
            NonLeafNode * newRoot = createNonLeafNode(m_capacity + 1, node1->level() + 1, 0);
            newRoot->insert(node1->boundingBox(), node1);
            newRoot->insert(node2->boundingBox(), node2);
            m_root = newRoot;
            //debugFlake << "new root" << m_root->nodeId();
        }
    } else {
        NonLeafNode * parent = dynamic_cast<NonLeafNode *>(node1->parent());
        if (!parent) {
            qFatal("KoRTree::adjustTree: no parent node found!");
            return;
        }
        //QRectF pbbold( parent->boundingBox() );
        parent->setChildBoundingBox(node1->place(), node1->boundingBox());
        parent->updateBoundingBox();
        //debugFlake << "  bb1 =" << node1->boundingBox() << node1->place() << pbbold << "->" << parent->boundingBox() << parent->nodeId();
 
        if (!node2) {
            //debugFlake << "  update";
            adjustTree(parent, 0);
        } else {
            if (parent->childCount() < m_capacity) {
                //debugFlake << "  no split needed";
                parent->insert(node2->boundingBox(), node2);
                adjustTree(parent, 0);
            } else {
                //debugFlake << "  split again";
                parent->insert(node2->boundingBox(), node2);
                QPair<Node *, Node *> newNodes = splitNode(parent);
                adjustTree(newNodes.first, newNodes.second);
            }
        }
    }
}

References KoRTree< T >::Node::boundingBox(), KoRTree< T >::NonLeafNode::insert(), KoRTree< T >::Node::isRoot(), KoRTree< T >::Node::level(), KoRTree< T >::Node::parent(), and KoRTree< T >::Node::place().

clear()

template<typename T >

virtual void KoRTree< T >::clear ( )

inlinevirtual

Definition at line 127 of file KoRTree.h.

                         {
        delete m_root;
        m_root = createLeafNode(m_capacity + 1, 0, 0);
        m_leafMap.clear();
    }

References KoRTree< T >::createLeafNode(), KoRTree< T >::m_capacity, KoRTree< T >::m_leafMap, and KoRTree< T >::m_root.

condenseTree()

template<typename T >

void KoRTree< T >::condenseTree ( Node * node, QVector< Node * > & reinsert )

protectedvirtual

WARNING: here we leave the tree in an inconsistent state! 'reinsert' nodes may still be kept in m_leafMap structure, but we will not remove them for the efficiency reasons. They are guaranteed to be readded in remove().

Definition at line 715 of file KoRTree.h.

{
    //debugFlake << "KoRTree::condenseTree begin reinsert.size()" << reinsert.size();
    if (!node->isRoot()) {
        Node * parent = node->parent();
        //debugFlake << " !node->isRoot us" << node->childCount();
 
        if (node->childCount() < m_minimum) {
            //debugFlake << "  remove node";
            parent->remove(node->place());
            reinsert.push_back(node);
 
        } else {
            //debugFlake << "  update BB parent is root" << parent->isRoot();
            parent->setChildBoundingBox(node->place(), node->boundingBox());
            parent->updateBoundingBox();
        }
        condenseTree(parent, reinsert);
    } else {
        //debugFlake << " node->isRoot us" << node->childCount();
        if (node->childCount() == 1 && !node->isLeaf()) {
            //debugFlake << "  usedSpace = 1";
            NonLeafNode * n = dynamic_cast<NonLeafNode *>(node);
            if (n) {
                Node * kid = n->getNode(0);
                // clear is needed as the data items are not removed
                m_root->clear();
                delete m_root;
                m_root = kid;
                m_root->setParent(0);
                //debugFlake << " new root" << m_root;
            } else {
                qFatal("KoRTree::condenseTree cast to NonLeafNode failed");
            }
        }
    }
    //debugFlake << "KoRTree::condenseTree end reinsert.size()" << reinsert.size();
}

References KoRTree< T >::Node::boundingBox(), KoRTree< T >::Node::childCount(), KoRTree< T >::Node::clear(), KoRTree< T >::NonLeafNode::getNode(), KoRTree< T >::Node::isLeaf(), KoRTree< T >::Node::isRoot(), KoRTree< T >::Node::parent(), KoRTree< T >::Node::place(), and KoRTree< T >::Node::setParent().

contained()

template<typename T >

QList< T > KoRTree< T >::contained

(

const QRectF &

point

)

const

Find all data item which contain the point The items are sorted by insertion time in ascending order.

Parameters

point

which should be contained in the objects

Returns

objects which contain the point

Definition at line 502 of file KoRTree.h.

{
    QMap<int, T> found;
    m_root->contained(rect, found);
    return found.values();
}

contains() [1/2]

template<typename T >

QList< T > KoRTree< T >::contains

(

const QPointF &

point

)

const

Find all data item which contain the point The items are sorted by insertion time in ascending order.

Parameters

point

which should be contained in the objects

Returns

objects which contain the point

Definition at line 494 of file KoRTree.h.

{
    QMap<int, T> found;
    m_root->contains(point, found);
    return found.values();
}

contains() [2/2]

template<typename T >

bool KoRTree< T >::contains

(

const T &

data

)

Show if a shape is a part of the tree.

Parameters

data

Definition at line 433 of file KoRTree.h.

{
    return m_leafMap[data];
}

createLeafNode()

template<typename T >

virtual LeafNode * KoRTree< T >::createLeafNode ( int capacity, int level, Node * parent )

inlineprotectedvirtual

Definition at line 317 of file KoRTree.h.

                                                                             {
        return new LeafNode(capacity, level, parent);
    }

createNonLeafNode()

template<typename T >

virtual NonLeafNode * KoRTree< T >::createNonLeafNode ( int capacity, int level, Node * parent )

inlineprotectedvirtual

Definition at line 320 of file KoRTree.h.

                                                                                   {
        return new NonLeafNode(capacity, level, parent);
    }

insert() [1/2]

template<typename T >

void KoRTree< T >::insert ( const QRectF & bb, const T & data )

virtual

Insert data item into the tree.

This will insert a data item into the tree. If necessary the tree will adjust itself.

Parameters

data
bb

Definition at line 359 of file KoRTree.h.

{
    // check if the shape is not already registered
    KIS_SAFE_ASSERT_RECOVER_NOOP(!m_leafMap[data]);
 
    insertHelper(bb, data, LeafNode::dataIdCounter++);
}

References KIS_SAFE_ASSERT_RECOVER_NOOP.

insert() [2/2]

template<typename T >

void KoRTree< T >::insert ( Node * node )

protected

Definition at line 414 of file KoRTree.h.

{
    if (node->level() == m_root->level()) {
        adjustTree(m_root, node);
    } else {
        QRectF bb(node->boundingBox());
        NonLeafNode * newParent = m_root->chooseNode(bb, node->level() + 1);
 
        newParent->insert(bb, node);
 
        QPair<Node *, Node *> newNodes(node, 0);
        if (newParent->childCount() > m_capacity) {
            newNodes = splitNode(newParent);
        }
        adjustTree(newNodes.first, newNodes.second);
    }
}

References KoRTree< T >::Node::boundingBox(), KoRTree< T >::Node::childCount(), KoRTree< T >::NonLeafNode::chooseNode(), KoRTree< T >::NonLeafNode::insert(), and KoRTree< T >::Node::level().

insertHelper()

template<typename T >

void KoRTree< T >::insertHelper ( const QRectF & bb, const T & data, int id )

protected

Definition at line 368 of file KoRTree.h.

{
    QRectF nbb(bb.normalized());
    // This has to be done as it is not possible to use QRectF::united() with a isNull()
    if (nbb.isNull()) {
        qWarning() <<  "KoRTree::insert boundingBox isNull setting size to" << nbb.size();
 
        nbb.setWidth(0.0001);
        nbb.setHeight(0.0001);
    }
    else {
        // This has to be done as QRectF::intersects() return false if the rect does not have any area overlapping.
        // If there is no width or height there is no area and therefore no overlapping.
        if ( nbb.width() == 0 ) {
            nbb.setWidth(0.0001);
        }
        if ( nbb.height() == 0 ) {
            nbb.setHeight(0.0001);
        }
    }
 
    LeafNode * leaf = m_root->chooseLeaf(nbb);
    //debugFlake << " leaf" << leaf->nodeId() << nbb;
 
    if (leaf->childCount() < m_capacity) {
        leaf->insert(nbb, data, id);
        m_leafMap[data] = leaf;
        adjustTree(leaf, 0);
    } else {
        leaf->insert(nbb, data, id);
        m_leafMap[data] = leaf;
        QPair<Node *, Node *> newNodes = splitNode(leaf);
        LeafNode * l = dynamic_cast<LeafNode *>(newNodes.first);
        if (l)
            for (int i = 0; i < l->childCount(); ++i)
                m_leafMap[l->getData(i)] = l;
        l = dynamic_cast<LeafNode *>(newNodes.second);
        if (l)
            for (int i = 0; i < l->childCount(); ++i)
                m_leafMap[l->getData(i)] = l;
 
        adjustTree(newNodes.first, newNodes.second);
    }
}

References KoRTree< T >::Node::childCount(), KoRTree< T >::LeafNode::chooseLeaf(), KoRTree< T >::LeafNode::getData(), and KoRTree< T >::LeafNode::insert().

intersects()

template<typename T >

QList< T > KoRTree< T >::intersects ( const QRectF & rect ) const

virtual

Find all data items which intersects rect The items are sorted by insertion time in ascending order.

Parameters

rect	where the objects have to be in

Returns

objects intersecting the rect

Definition at line 486 of file KoRTree.h.

{
    QMap<int, T> found;
    m_root->intersects(rect, found);
    return found.values();
}

keys()

template<typename T >

QList< QRectF > KoRTree< T >::keys

(

)

const

Find all data rectangles The order is NOT guaranteed to be the same as that used by values().

Returns

a list containing all the data rectangles used in the tree

Definition at line 511 of file KoRTree.h.

{
    QList<QRectF> found;
    m_root->keys(found);
    return found;
}

pickNext()

template<typename T >

QPair< int, int > KoRTree< T >::pickNext ( Node * node, QVector< bool > & marker, Node * group1, Node * group2 )

protected

Definition at line 641 of file KoRTree.h.

{
    //debugFlake << "KoRTree::pickNext" << marker;
    qreal max = -1.0;
    int select = 0;
    int group = 0;
    for (int i = 0; i < m_capacity + 1; ++i) {
        if (marker[i] == false) {
            QRectF bb1 = group1->boundingBox().united(node->childBoundingBox(i));
            QRectF bb2 = group2->boundingBox().united(node->childBoundingBox(i));
            qreal d1 = bb1.width() * bb1.height() - group1->boundingBox().width() * group1->boundingBox().height();
            qreal d2 = bb2.width() * bb2.height() - group2->boundingBox().width() * group2->boundingBox().height();
            qreal diff = qAbs(d1 - d2);
            //debugFlake << " diff" << diff << i << d1 << d2;
            if (diff > max) {
                max = diff;
                select = i;
                //debugFlake << "  i =" <<  i;
                if (qAbs(d1) > qAbs(d2)) {
                    group = 1;
                } else {
                    group = 0;
                }
                //debugFlake << "  group =" << group;
            }
        }
    }
    marker[select] = true;
    return qMakePair(group, select);
}

References KoRTree< T >::Node::boundingBox(), and KoRTree< T >::Node::childBoundingBox().

pickSeeds()

template<typename T >

QPair< int, int > KoRTree< T >::pickSeeds ( Node * node )

protected

Definition at line 616 of file KoRTree.h.

{
    int s1 = 0;
    int s2 = 1;
    qreal max = 0;
    for (int i = 0; i < m_capacity + 1; ++i) {
        for (int j = i+1; j < m_capacity + 1; ++j) {
            if (i != j) {
                QRectF bb1(node->childBoundingBox(i));
                QRectF bb2(node->childBoundingBox(j));
                QRectF comp(node->childBoundingBox(i).united(node->childBoundingBox(j)));
                qreal area = comp.width() * comp.height() - bb1.width() * bb1.height() - bb2.width() * bb2.height();
                //debugFlake << " ps" << i << j << area;
                if (area > max) {
                    max = area;
                    s1 = i;
                    s2 = j;
                }
            }
        }
    }
    return qMakePair(s1, s2);
}

References KoRTree< T >::Node::childBoundingBox(), s1, and s2.

remove()

template<typename T >

void KoRTree< T >::remove

(

const T &

data

)

Remove a data item from the tree.

This removed a data item from the tree. If necessary the tree will adjust itself.

Parameters

data

WARNING: after calling condenseTree() the temporary enters an inconsistent state! m_leafMap still points to the nodes now stored in 'reinsert' list, although they are not a part of the hierarchy. This state does not cause any use visible changes, but should be considered while implementing sanity checks.

Definition at line 440 of file KoRTree.h.

{
    //debugFlake << "KoRTree remove";
    LeafNode * leaf = m_leafMap[data];
 
    // Trying to remove inexistent leaf. Most probably, this leaf hasn't been added
    // to the shape manager correctly
    KIS_SAFE_ASSERT_RECOVER_RETURN(leaf);
 
    m_leafMap.remove(data);
    leaf->remove(data);
 
    QVector<Node *> reinsert;
    condenseTree(leaf, reinsert);
 
    for (int i = 0; i < reinsert.size(); ++i) {
        if (reinsert[i]->isLeaf()) {
            LeafNode * leaf = dynamic_cast<LeafNode *>(reinsert[i]);
            KIS_SAFE_ASSERT_RECOVER(leaf) { reinsert[i]->clear(); delete reinsert[i]; continue; } // mostly for the sake of Coverity
            for (int j = 0; j < leaf->childCount(); ++j) {
                insertHelper(leaf->childBoundingBox(j), leaf->getData(j), leaf->getDataId(j));
            }
            // clear is needed as the data items are not removed when insert into a new node
            leaf->clear();
            delete leaf;
        } else {
            NonLeafNode * node = dynamic_cast<NonLeafNode *>(reinsert[i]);
            KIS_SAFE_ASSERT_RECOVER(node) { reinsert[i]->clear(); delete reinsert[i]; continue; } // mostly for the sake of Coverity
            for (int j = 0; j < node->childCount(); ++j) {
                insert(node->getNode(j));
            }
            // clear is needed as the data items are not removed when insert into a new node
            node->clear();
            delete node;
        }
    }
}

References KoRTree< T >::Node::childBoundingBox(), KoRTree< T >::Node::childCount(), KoRTree< T >::Node::clear(), KoRTree< T >::LeafNode::getData(), KoRTree< T >::LeafNode::getDataId(), KoRTree< T >::NonLeafNode::getNode(), KIS_SAFE_ASSERT_RECOVER, KIS_SAFE_ASSERT_RECOVER_RETURN, and KoRTree< T >::LeafNode::remove().

splitNode()

template<typename T >

QPair< typename KoRTree< T >::Node *, typename KoRTree< T >::Node * > KoRTree< T >::splitNode ( Node * node )

protected

Definition at line 544 of file KoRTree.h.

{
    //debugFlake << "KoRTree::splitNode" << node;
    Node * n1;
    Node * n2;
    if (node->isLeaf()) {
        n1 = createLeafNode(m_capacity + 1, node->level(), node->parent());
        n2 = createLeafNode(m_capacity + 1, node->level(), node->parent());
    } else {
        n1 = createNonLeafNode(m_capacity + 1, node->level(), node->parent());
        n2 = createNonLeafNode(m_capacity + 1, node->level(), node->parent());
    }
    //debugFlake << " n1" << n1 << n1->nodeId();
    //debugFlake << " n2" << n2 << n2->nodeId();
 
    QVector<bool> marker(m_capacity + 1);
 
    QPair<int, int> seeds(pickSeeds(node));
 
    n1->move(node, seeds.first);
    n2->move(node, seeds.second);
 
    marker[seeds.first] = true;
    marker[seeds.second] = true;
 
    // There is one more in a node to split than the capacity and as we
    // already put the seeds in the new nodes subtract them.
    int remaining = m_capacity + 1 - 2;
 
    while (remaining > 0) {
        if (m_minimum - n1->childCount() == remaining) {
            for (int i = 0; i < m_capacity + 1; ++i) {
                if (!marker[i]) {
                    n1->move(node, i);
                    --remaining;
                }
            }
        } else if (m_minimum - n2->childCount() == remaining) {
            for (int i = 0; i < m_capacity + 1; ++i) {
                if (!marker[i]) {
                    n2->move(node, i);
                    --remaining;
                }
            }
        } else {
            QPair<int, int> next(pickNext(node, marker, n1, n2));
 
            if (next.first == 0) {
                n1->move(node, next.second);
            } else {
                n2->move(node, next.second);
            }
            --remaining;
        }
    }
    Q_ASSERT(n1->childCount() + n2->childCount() == node->childCount());
 
    // move the data back to the old node
    // this has to be done as the current node is already in the tree.
    node->clear();
    for (int i = 0; i < n1->childCount(); ++i) {
        node->move(n1, i);
    }
 
    //debugFlake << " delete n1" << n1 << n1->nodeId();
    // clear is needed as the data items are not removed
    n1->clear();
    delete n1;
    return qMakePair(node, n2);
}

References KoRTree< T >::Node::childCount(), KoRTree< T >::Node::clear(), KoRTree< T >::Node::isLeaf(), KoRTree< T >::Node::level(), KoRTree< T >::Node::move(), and KoRTree< T >::Node::parent().

values()

template<typename T >

QList< T > KoRTree< T >::values

(

)

const

Find all data items The order is NOT guaranteed to be the same as that used by keys().

Returns

a list containing all the data used in the tree

Definition at line 519 of file KoRTree.h.

{
    QMap<int, T> found;
    m_root->values(found);
    return found.values();
}

Member Data Documentation

m_capacity

template<typename T >

int KoRTree< T >::m_capacity

protected

Definition at line 335 of file KoRTree.h.

m_leafMap

template<typename T >

QMap<T, LeafNode *> KoRTree< T >::m_leafMap

protected

Definition at line 338 of file KoRTree.h.

m_minimum

template<typename T >

int KoRTree< T >::m_minimum

protected

Definition at line 336 of file KoRTree.h.

m_root

template<typename T >

Node* KoRTree< T >::m_root

protected

Definition at line 337 of file KoRTree.h.

---

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

• libs/flake/KoRTree.h