KisSpatialContainer Class Reference

#include <KisSpatialContainer.h>

Classes
struct	SpatialNode

Public Member Functions
void	addPoint (int index, QPointF position)
void	clear ()
int	count ()
void	debugWriteOut ()
QRectF	exactBounds ()
void	findAllInRange (QVector< int > &indexes, QPointF center, qreal range)
QPointF	getTopLeft ()
void	initializeFor (int numPoints, QRectF startArea)
void	initializeWith (const QVector< QPointF > &points)
void	initializeWithGridPoints (QRectF gridRect, int pixelPrecision)
	KisSpatialContainer (const KisSpatialContainer &rhs)
	KisSpatialContainer (QRectF startArea, int maxPointsInDict=100)
	KisSpatialContainer (QRectF startArea, QVector< QPointF > &points)
void	movePoint (int index, QPointF positionBefore, QPointF positionAfter)
void	removePoint (int index, QPointF position)
QVector< QPointF >	toVector ()
	~KisSpatialContainer ()

Private Member Functions
void	addPointRec (int index, QPointF position, SpatialNode *node)
void	clearRec (SpatialNode *node)
SpatialNode *	createNodeForPoint (int index, QPointF position)
void	debugWriteOutRec (SpatialNode *node, QString prefix)
void	deepCopyData (SpatialNode *node, const SpatialNode *from)
void	findAllInRangeRec (QVector< int > &indexes, QPointF center, qreal range, SpatialNode *node)
void	gatherDataRec (QVector< QPointF > &vector, SpatialNode *node)
std::optional< qreal >	getBoundaryOnAxis (bool positive, bool xAxis, SpatialNode *node)
QPointF	getBoundaryPoint (bool left, bool top)
void	initializeLevels (SpatialNode *node, int levelsLeft, QRectF area)
void	initializeWithGridPointsRec (QRectF gridRect, int pixelPrecision, SpatialNode *node, int startRow, int startColumn, int columnCount)
void	movePointRec (int index, QPointF positionBefore, QPointF positionAfter, SpatialNode *node)
void	removePointRec (int index, QPointF position, SpatialNode *node)

Private Attributes
int	m_count {0}
int	m_maxPointsInDict = {100}
int	m_nextNodeId = {0}
SpatialNode *	m_root {nullptr}

Friends
class	KisSpatialContainerTest

Detailed Description

Definition at line 23 of file KisSpatialContainer.h.

Constructor & Destructor Documentation

KisSpatialContainer() [1/3]

KisSpatialContainer::KisSpatialContainer	(	QRectF	startArea,
		int	maxPointsInDict = 100 )

Definition at line 83 of file KisSpatialContainer.cpp.

    : m_maxPointsInDict(maxPointsInDict)
{
    m_root = new KisSpatialContainer::SpatialNode();
    m_root->xPartition = startArea.x() + startArea.width()/2.0;
    m_root->yPartition = startArea.y() + startArea.height()/2.0;
    m_root->nodeId = m_nextNodeId++;
}

References m_nextNodeId, m_root, KisSpatialContainer::SpatialNode::nodeId, KisSpatialContainer::SpatialNode::xPartition, and KisSpatialContainer::SpatialNode::yPartition.

KisSpatialContainer() [2/3]

KisSpatialContainer::KisSpatialContainer	(	QRectF	startArea,
		QVector< QPointF > &	points )

Definition at line 92 of file KisSpatialContainer.cpp.

{
    m_root = new KisSpatialContainer::SpatialNode();
    m_root->xPartition = startArea.x() + startArea.width()/2.0;
    m_root->yPartition = startArea.y() + startArea.height()/2.0;
    m_root->nodeId = m_nextNodeId++;
 
    initializeWith(points);
}

References initializeWith(), m_nextNodeId, m_root, KisSpatialContainer::SpatialNode::nodeId, KisSpatialContainer::SpatialNode::xPartition, and KisSpatialContainer::SpatialNode::yPartition.

KisSpatialContainer() [3/3]

KisSpatialContainer::KisSpatialContainer

(

const KisSpatialContainer &

rhs

)

Definition at line 102 of file KisSpatialContainer.cpp.

{
    m_root = rhs.m_root;
    m_root = new SpatialNode();
    m_maxPointsInDict = rhs.m_maxPointsInDict;
    m_count = rhs.m_count;
    m_nextNodeId = rhs.m_nextNodeId;
    deepCopyData(m_root, rhs.m_root);
}

References deepCopyData(), m_count, m_maxPointsInDict, m_nextNodeId, and m_root.

~KisSpatialContainer()

KisSpatialContainer::~KisSpatialContainer

(

)

Definition at line 112 of file KisSpatialContainer.cpp.

{
    clear();
    delete m_root;
    m_root = nullptr;
}

References clear(), and m_root.

Member Function Documentation

addPoint()

void KisSpatialContainer::addPoint	(	int	index,
		QPointF	position )

Definition at line 151 of file KisSpatialContainer.cpp.

{
    addPointRec(index, position, m_root);
}

References addPointRec(), and m_root.

addPointRec()

void KisSpatialContainer::addPointRec ( int index, QPointF position, SpatialNode * node )

private

Definition at line 212 of file KisSpatialContainer.cpp.

{
    if (!node) return;
    if (node->isLeaf) { // leaf
        SpatialNodeData childData(index, position);
 
        node->pointsData << childData;
        KisAlgebra2D::accumulateBounds(position, &node->maximumArea);
        m_count++;
 
        if (node->pointsCount == m_maxPointsInDict) {
            // gotta make it into a parent node
            node->xPartition = node->maximumArea.x() + node->maximumArea.width()/2.0;
            node->yPartition = node->maximumArea.y() + node->maximumArea.height()/2.0;
            node->children = QVector<SpatialNode*> {nullptr, nullptr, nullptr, nullptr};
            node->isLeaf = false;
 
 
            QVector<SpatialNodeData>::iterator it = node->pointsData.begin();
            QVector<SpatialNodeData>::iterator end = node->pointsData.end();
 
            for (; it != end; ++it) {
                int childIndex = node->childIndexForPoint(it->position);
                if (!node->children[childIndex]) {
                    node->children[childIndex] = createNodeForPoint(it->index, it->position);
                } else {
                    addPointRec(it->index, it->position, node->children[childIndex]);
                }
            }
            node->pointsData.clear();
            node->pointsCount = 0;
 
        } else {
            node->pointsCount++;
        }
    } else { // inner node
        int childIndex = node->childIndexForPoint(position);
        if (!node->children[childIndex]) { // no node for points there yet
            SpatialNode* newChild = createNodeForPoint(index, position);
            node->children[childIndex] = newChild;
        } else {
            addPointRec(index, position, node->children[childIndex]);
        }
    }
}

References KisAlgebra2D::accumulateBounds(), addPointRec(), KisSpatialContainer::SpatialNode::childIndexForPoint(), KisSpatialContainer::SpatialNode::children, createNodeForPoint(), KisSpatialContainer::SpatialNode::isLeaf, m_count, m_maxPointsInDict, KisSpatialContainer::SpatialNode::maximumArea, KisSpatialContainer::SpatialNode::pointsCount, KisSpatialContainer::SpatialNode::pointsData, KisSpatialContainer::SpatialNode::xPartition, and KisSpatialContainer::SpatialNode::yPartition.

clear()

void KisSpatialContainer::clear

(

)

Definition at line 201 of file KisSpatialContainer.cpp.

{
    clearRec(m_root);
 
    // now clean up root
    m_root->isLeaf = true;
    m_root->children = {};
    m_root->pointsCount = 0;
    m_root->pointsData = {};
}

References KisSpatialContainer::SpatialNode::children, clearRec(), KisSpatialContainer::SpatialNode::isLeaf, m_root, KisSpatialContainer::SpatialNode::pointsCount, and KisSpatialContainer::SpatialNode::pointsData.

clearRec()

void KisSpatialContainer::clearRec ( SpatialNode * node )

private

Definition at line 675 of file KisSpatialContainer.cpp.

{
    if (!node) return;
    bool hadChildren = false;
    for (int i = 0; i < node->children.length(); i++) {
        if (node->children[i]) {
            hadChildren = true;
 
            clearRec(node->children[i]);
 
            delete node->children[i];
            node->children[i] = nullptr;
        }
    }
    KIS_SAFE_ASSERT_RECOVER_RETURN(!node->isLeaf || !hadChildren);
}

References KisSpatialContainer::SpatialNode::children, clearRec(), KisSpatialContainer::SpatialNode::isLeaf, and KIS_SAFE_ASSERT_RECOVER_RETURN.

count()

int KisSpatialContainer::count

(

)

Definition at line 184 of file KisSpatialContainer.cpp.

{
    return m_count;
}

References m_count.

createNodeForPoint()

KisSpatialContainer::SpatialNode * KisSpatialContainer::createNodeForPoint ( int index, QPointF position )

private

Definition at line 334 of file KisSpatialContainer.cpp.

{
    SpatialNode* newChild = new SpatialNode();
    newChild->pointsCount = 1;
    newChild->pointsData = QVector<SpatialNodeData> {SpatialNodeData(index, position)};
    newChild->maximumArea = QRectF(position, position);
    newChild->nodeId = m_nextNodeId++;
    return newChild;
}

References m_nextNodeId, KisSpatialContainer::SpatialNode::maximumArea, KisSpatialContainer::SpatialNode::nodeId, KisSpatialContainer::SpatialNode::pointsCount, and KisSpatialContainer::SpatialNode::pointsData.

debugWriteOut()

void KisSpatialContainer::debugWriteOut

(

)

Definition at line 393 of file KisSpatialContainer.cpp.

{
    debugWriteOutRec(m_root, "");
}

References debugWriteOutRec(), and m_root.

debugWriteOutRec()

void KisSpatialContainer::debugWriteOutRec ( SpatialNode * node, QString prefix )

private

Definition at line 398 of file KisSpatialContainer.cpp.

{
    if (!node) {
        return;
    }
    if (node->isLeaf) {
        qCritical() << prefix << "* (" << node->nodeId << ") is Leaf?" << node->isLeaf << ppVar(node->pointsCount) << ppVar(node->pointsData.length());
        for (int i = 0; i < node->pointsCount; i++) {
            qCritical() << prefix << " - " << node->pointsData[i].index << " | " << node->pointsData[i].position;
        }
    } else {
        qCritical() << prefix << "* (" << node->nodeId << ") is Leaf?" << node->isLeaf << ppVar(node->xPartition) << ppVar(node->yPartition);
 
        qCritical() << prefix << "0: ";
        debugWriteOutRec(node->children[0], prefix + "0.");
        qCritical() << prefix << "1: ";
        debugWriteOutRec(node->children[1], prefix + "1.");
        qCritical() << prefix << "2: ";
        debugWriteOutRec(node->children[2], prefix + "2.");
        qCritical() << prefix << "3: ";
        debugWriteOutRec(node->children[3], prefix + "3.");
    }
}

References KisSpatialContainer::SpatialNode::children, debugWriteOutRec(), KisSpatialContainer::SpatialNode::isLeaf, KisSpatialContainer::SpatialNode::nodeId, KisSpatialContainer::SpatialNode::pointsCount, KisSpatialContainer::SpatialNode::pointsData, ppVar, KisSpatialContainer::SpatialNode::xPartition, and KisSpatialContainer::SpatialNode::yPartition.

deepCopyData()

void KisSpatialContainer::deepCopyData ( SpatialNode * node, const SpatialNode * from )

private

Definition at line 692 of file KisSpatialContainer.cpp.

{
    node->isLeaf = from->isLeaf;
    node->maximumArea = from->maximumArea;
    node->nodeId = from->nodeId;
    node->pointsCount = from->pointsCount;
    node->pointsData = from->pointsData;
    node->xPartition = from->xPartition;
    node->yPartition = from->yPartition;
 
    if (!from->isLeaf) {
        node->children = {nullptr, nullptr, nullptr, nullptr};
        for (int i = 0; i < node->children.size(); i++) {
            if (from->children[i]) {
                node->children[i] = new SpatialNode();
                deepCopyData(node->children[i], from->children[i]);
            }
        }
    }
}

References KisSpatialContainer::SpatialNode::children, deepCopyData(), KisSpatialContainer::SpatialNode::isLeaf, KisSpatialContainer::SpatialNode::maximumArea, KisSpatialContainer::SpatialNode::nodeId, KisSpatialContainer::SpatialNode::pointsCount, KisSpatialContainer::SpatialNode::pointsData, KisSpatialContainer::SpatialNode::xPartition, and KisSpatialContainer::SpatialNode::yPartition.

exactBounds()

QRectF KisSpatialContainer::exactBounds

(

)

Definition at line 194 of file KisSpatialContainer.cpp.

{
    QPointF topLeft = getTopLeft();
    QPointF bottomRight = getBoundaryPoint(true, true);
    return QRectF(topLeft, bottomRight);
}

References getBoundaryPoint(), and getTopLeft().

findAllInRange()

void KisSpatialContainer::findAllInRange	(	QVector< int > &	indexes,
		QPointF	center,
		qreal	range )

Definition at line 179 of file KisSpatialContainer.cpp.

{
    findAllInRangeRec(indexes, center, range, m_root);
}

References findAllInRangeRec(), and m_root.

findAllInRangeRec()

void KisSpatialContainer::findAllInRangeRec ( QVector< int > & indexes, QPointF center, qreal range, SpatialNode * node )

private

Definition at line 354 of file KisSpatialContainer.cpp.

{
    if (!node) return;
    if (node->isLeaf) {
        for (int i = 0; i < node->pointsCount; i++) {
            if (isInRange(center, range, node->pointsData[i])) {
                indexes.append(node->pointsData[i].index);
            }
        }
    } else {
        QList<int> childrenToVisit;
        childrenToVisit << node->childIndexForPoint(center + QPointF(range, range));
        childrenToVisit << node->childIndexForPoint(center + QPointF(range, -range));
        childrenToVisit << node->childIndexForPoint(center + QPointF(-range, range));
        childrenToVisit << node->childIndexForPoint(center + QPointF(-range, -range));
 
        for (int i = 0; i < node->children.length(); i++) {
            if (childrenToVisit.contains(i)) { // that eliminates all the leaves outside of the area
                findAllInRangeRec(indexes, center, range, node->children[i]);
            }
        }
    }
}

References KisSpatialContainer::SpatialNode::childIndexForPoint(), KisSpatialContainer::SpatialNode::children, findAllInRangeRec(), isInRange(), KisSpatialContainer::SpatialNode::isLeaf, KisSpatialContainer::SpatialNode::pointsCount, and KisSpatialContainer::SpatialNode::pointsData.

gatherDataRec()

void KisSpatialContainer::gatherDataRec ( QVector< QPointF > & vector, SpatialNode * node )

private

Definition at line 378 of file KisSpatialContainer.cpp.

{
    if (!node) return;
    if (node->isLeaf) {
        for (int i = 0; i < node->pointsData.size(); i++) {
            KIS_SAFE_ASSERT_RECOVER(node->pointsData[i].index < vector.length()) { continue; };
            vector[node->pointsData[i].index] = node->pointsData[i].position;
        }
    } else {
        for (int i = 0; i < node->children.length(); i++) {
            gatherDataRec(vector, node->children[i]);
        }
    }
}

References KisSpatialContainer::SpatialNode::children, gatherDataRec(), KisSpatialContainer::SpatialNode::isLeaf, KIS_SAFE_ASSERT_RECOVER, and KisSpatialContainer::SpatialNode::pointsData.

getBoundaryOnAxis()

std::optional< qreal > KisSpatialContainer::getBoundaryOnAxis ( bool positive, bool xAxis, SpatialNode * node )

private

Definition at line 422 of file KisSpatialContainer.cpp.

{
    if (!node) {
        return std::nullopt;
    }
 
    if (node->isLeaf) {
        if (node->pointsData.length() == 0) {
            return std::nullopt;
        }
 
        auto getNum = [xAxis] (const SpatialNodeData& a, const SpatialNodeData& b) {
            if (xAxis) {
                return a.position.x() < b.position.x();
            } else {
                return a.position.y() < b.position.y();
            }
        };
        if (positive) {
            QVector<SpatialNodeData>::iterator data = std::max_element(node->pointsData.begin(), node->pointsData.end(), getNum);
            if (data != node->pointsData.end()) {
                if (xAxis) {
                    return data->position.x();
                } else {
                    return data->position.y();
                }
            }
        } else {
            QVector<SpatialNodeData>::iterator data = std::min_element(node->pointsData.begin(), node->pointsData.end(), getNum);
 
            if (data != node->pointsData.end()) {
                if (xAxis) {
                    return data->position.x();
                } else {
                    return data->position.y();
                }
            }
        }
        return std::nullopt;
 
    } else {
        int diff = positive? 1 : -1;
        int childIndex1, childIndex2;
        if (xAxis) {
            childIndex1 = node->childIndexForPoint(QPointF(node->xPartition + diff, node->yPartition + 1));
            childIndex2 = node->childIndexForPoint(QPointF(node->xPartition + diff, node->yPartition - 1));
        } else {
            childIndex1 = node->childIndexForPoint(QPointF(node->xPartition + 1, node->yPartition + diff));
            childIndex2 = node->childIndexForPoint(QPointF(node->xPartition - 1, node->yPartition + diff));
        }
        std::optional<qreal> response1 = getBoundaryOnAxis(positive, xAxis, node->children[childIndex1]);
        std::optional<qreal> response2 = getBoundaryOnAxis(positive, xAxis, node->children[childIndex2]);
 
        if (!response1.has_value() && !response2.has_value()) {
            // gotta check the other two
            diff = -diff;
            if (xAxis) {
                childIndex1 = node->childIndexForPoint(QPointF(node->xPartition + diff, node->yPartition + 1));
                childIndex2 = node->childIndexForPoint(QPointF(node->xPartition + diff, node->yPartition - 1));
            } else {
                childIndex1 = node->childIndexForPoint(QPointF(node->xPartition + 1, node->yPartition + diff));
                childIndex2 = node->childIndexForPoint(QPointF(node->xPartition - 1, node->yPartition + diff));
            }
            response1 = getBoundaryOnAxis(positive, xAxis, node->children[childIndex1]);
            response2 = getBoundaryOnAxis(positive, xAxis, node->children[childIndex2]);
        }
 
 
        if (!response1.has_value()) {
            return response2;
        }
        if (!response2.has_value()) {
            return response1;
        }
 
        if (positive) {
            return qMax(response1.value(), response2.value());
        } else {
            return qMin(response1.value(), response2.value());
        }
    }
}

References KisSpatialContainer::SpatialNode::childIndexForPoint(), KisSpatialContainer::SpatialNode::children, getBoundaryOnAxis(), KisSpatialContainer::SpatialNode::isLeaf, KisSpatialContainer::SpatialNode::pointsData, KisSpatialContainer::SpatialNode::SpatialNodeData::position, KisSpatialContainer::SpatialNode::xPartition, and KisSpatialContainer::SpatialNode::yPartition.

getBoundaryPoint()

QPointF KisSpatialContainer::getBoundaryPoint ( bool left, bool top )

private

Definition at line 505 of file KisSpatialContainer.cpp.

{
    std::optional<qreal> x = getBoundaryOnAxis(left, true, m_root);
    std::optional<qreal> y = getBoundaryOnAxis(top, false, m_root);
 
    QPointF response = QPointF();
    if (x.has_value()) {
        response.setX(x.value());
    }
    if (y.has_value()) {
        response.setY(y.value());
    }
 
    return response;
}

References getBoundaryOnAxis(), and m_root.

getTopLeft()

QPointF KisSpatialContainer::getTopLeft

(

)

Definition at line 189 of file KisSpatialContainer.cpp.

{
    return getBoundaryPoint(false, false);
}

References getBoundaryPoint().

initializeFor()

void KisSpatialContainer::initializeFor	(	int	numPoints,
		QRectF	startArea )

Definition at line 119 of file KisSpatialContainer.cpp.

{
    clear();
 
    int levels = 1;
    int leaves = (int)qCeil(numPoints/(double)m_maxPointsInDict);
    int nodes = leaves;
    while (nodes > 0) {
        nodes >>= 2;
        levels++;
    }
 
    initializeLevels(m_root, levels, startArea);
 
}

References clear(), initializeLevels(), m_maxPointsInDict, and m_root.

initializeLevels()

void KisSpatialContainer::initializeLevels ( SpatialNode * node, int levelsLeft, QRectF area )

private

Definition at line 521 of file KisSpatialContainer.cpp.

{
    KIS_SAFE_ASSERT_RECOVER_RETURN(node);
 
    if (levelsLeft > 1) {
 
        node->xPartition = area.x() + area.width();
        node->yPartition = area.y() + area.height();
        QPointF center = QPointF(node->xPartition, node->yPartition);
        node->isLeaf = false;
        node->children = {nullptr, nullptr, nullptr, nullptr};
        for (int i = 0; i < node->children.length(); i++) {
            node->children[i] = new SpatialNode();
            node->children[i]->nodeId = m_nextNodeId++;
        }
 
        int topLeftChild = node->childIndexForPoint(center + QPointF(-1, -1));
        initializeLevels(node->children[topLeftChild], levelsLeft - 1, QRectF(area.topLeft(), center));
 
        int topRightChild = node->childIndexForPoint(center + QPointF(1, -1));
        initializeLevels(node->children[topRightChild], levelsLeft - 1, QRectF(QPointF(node->xPartition, area.top()), QPointF(area.right(), node->yPartition)));
 
        int bottomLeftChild = node->childIndexForPoint(center + QPointF(-1, 1));
        initializeLevels(node->children[bottomLeftChild], levelsLeft - 1, QRectF(QPointF(area.left(), node->yPartition), QPointF(node->xPartition, area.bottom())));
 
        int bottomRightChild = node->childIndexForPoint(center + QPointF(1, 1));
        initializeLevels(node->children[bottomRightChild], levelsLeft - 1, QRectF(QPointF(node->xPartition, node->yPartition), QPointF(area.right(), area.bottom())));
 
    } else {
        node->isLeaf = true;
        node->children = {};
    }
 
 
}

References KisSpatialContainer::SpatialNode::childIndexForPoint(), KisSpatialContainer::SpatialNode::children, initializeLevels(), KisSpatialContainer::SpatialNode::isLeaf, KIS_SAFE_ASSERT_RECOVER_RETURN, m_nextNodeId, KisSpatialContainer::SpatialNode::xPartition, and KisSpatialContainer::SpatialNode::yPartition.

initializeWith()

void KisSpatialContainer::initializeWith

(

const QVector< QPointF > &

points

)

Definition at line 135 of file KisSpatialContainer.cpp.

{
    clear();
 
    for (int i = 0; i < points.length(); i++) {
        addPoint(i, points[i]);
    }
}

References addPoint(), and clear().

initializeWithGridPoints()

void KisSpatialContainer::initializeWithGridPoints	(	QRectF	gridRect,
		int	pixelPrecision )

Definition at line 144 of file KisSpatialContainer.cpp.

{
    clear();
    int columnsNum = GridIterationTools::calcGridSize(gridRect.toRect(), pixelPrecision).width();
    initializeWithGridPointsRec(gridRect, pixelPrecision, m_root, 0, 0, columnsNum);
}

References GridIterationTools::calcGridSize(), clear(), initializeWithGridPointsRec(), and m_root.

initializeWithGridPointsRec()

void KisSpatialContainer::initializeWithGridPointsRec ( QRectF gridRect, int pixelPrecision, SpatialNode * node, int startRow, int startColumn, int columnCount )

private

Definition at line 557 of file KisSpatialContainer.cpp.

{
    node->maximumArea = gridRect;
 
    QSize size = GridIterationTools::calcGridSize(gridRect.toRect(), pixelPrecision);
    int width = size.width();
    int height = size.height();
 
    int marginX = int(gridRect.left())%pixelPrecision;
    marginX = marginX == 0 ? 0 : pixelPrecision - marginX;
    int marginY = int(gridRect.top())%pixelPrecision;
    marginY = marginY == 0 ? 0 : pixelPrecision - marginY;
 
    // ceiling will always be on the corner or outside
    // floor will always be on the corner or inside
    QPoint topLeftDividableCeiling = QPoint((qCeil(gridRect.left()/(qreal)pixelPrecision))*pixelPrecision, (qCeil(gridRect.top()/(qreal)pixelPrecision))*pixelPrecision);
    QPoint topLeftDividableFloor = QPoint((qFloor(gridRect.left()/(qreal)pixelPrecision))*pixelPrecision, (qFloor(gridRect.top()/(qreal)pixelPrecision))*pixelPrecision);
 
 
    if (width * height <= m_maxPointsInDict) {
        node->isLeaf = true;
        node->pointsData.reserve(width * height);
 
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
 
                int pointIndex = (startRow + j)*columnCount + (startColumn + i);
 
                QPointF nextPoint = QPointF(topLeftDividableFloor.x() + i * pixelPrecision, topLeftDividableFloor.y() + j * pixelPrecision);
                if (i == 0) {
                    nextPoint.setX(gridRect.x());
                }
                if (j == 0) {
                    nextPoint.setY(gridRect.y());
                }
 
                // must be -1, because it's actually last included pixels and gridRect here is QRectF, not QRect
                if (nextPoint.x() > gridRect.right() - 1) {
                    nextPoint.setX(gridRect.right() - 1);
                }
                if (nextPoint.y() > gridRect.bottom() - 1) {
                    nextPoint.setY(gridRect.bottom() - 1);
                }
 
                node->pointsData << SpatialNodeData(pointIndex, nextPoint);
            }
        }
        node->pointsCount = node->pointsData.count();
        m_count += node->pointsCount;
        node->maximumArea = gridRect;
 
    } else {
 
        node->isLeaf = false;
 
        QPoint bottomRightDividable = QPoint((qFloor(gridRect.right()/(qreal)pixelPrecision))*pixelPrecision, (qFloor(gridRect.bottom()/(qreal)pixelPrecision))*pixelPrecision);
        QPoint topLeftDividable = topLeftDividableCeiling;
 
        QPoint sizeDividable = QPoint(bottomRightDividable - topLeftDividable);
        int xLeftDividable = (sizeDividable.x()) / pixelPrecision / 2;
        int yTopDividable = (sizeDividable.y()) / pixelPrecision / 2;
 
        qreal xLeftCenter = topLeftDividable.x() + xLeftDividable*pixelPrecision;
        qreal yTopCenter = topLeftDividable.y() + yTopDividable*pixelPrecision;
 
        qreal xRightCenter = topLeftDividable.x() + (xLeftDividable + 1)*pixelPrecision;
        qreal yBottomCenter = topLeftDividable.y() + (yTopDividable + 1)*pixelPrecision;
 
 
        int xLeft = width/2;
        int yTop = height/2;
 
        if (bottomRightDividable.x() <= topLeftDividable.x()) {
            // shouldn't really happen for Liquify, but let's have sane values
            xLeftCenter = gridRect.left() + xLeft*pixelPrecision;
            xRightCenter = gridRect.left() + (xLeft + 1)*pixelPrecision;
        }
 
        if (bottomRightDividable.y() <= topLeftDividable.y()) {
            yTopCenter = gridRect.top() + yTop*pixelPrecision;
            yBottomCenter = gridRect.top() + (yTop + 1)*pixelPrecision;
        }
 
 
        node->xPartition = (xLeftCenter + xRightCenter)/2;
        node->yPartition = (yTopCenter + yBottomCenter)/2;
 
        node->children = {nullptr, nullptr, nullptr, nullptr};
        for (int i = 0; i < node->children.count(); i++) {
            node->children[i] = new SpatialNode();
            node->children[i]->nodeId = m_nextNodeId++;
        }
 
        QPointF center = QPointF(node->xPartition, node->yPartition);
 
        int topLeftChild = node->childIndexForPoint(center + QPointF(-1, -1));
 
        initializeWithGridPointsRec(QRectF(gridRect.topLeft(), QPointF(xLeftCenter + 1, yTopCenter + 1)), pixelPrecision, node->children[topLeftChild], startRow, startColumn, columnCount);
 
        int rightStartColumn = startColumn + xLeftDividable + 1 + (topLeftDividableCeiling.x() > gridRect.left() ? 1 : 0);
        int bottomStartRow = startRow + yTopDividable + 1 + (topLeftDividableCeiling.y() > gridRect.top() ? 1 : 0);
 
        int topRightChild = node->childIndexForPoint(center + QPointF(1, -1));
        initializeWithGridPointsRec(QRectF(QPointF(xRightCenter, gridRect.top()), QPointF(gridRect.right(), yTopCenter + 1)), pixelPrecision,
                                    node->children[topRightChild], startRow, rightStartColumn, columnCount);
 
        int bottomLeftChild = node->childIndexForPoint(center + QPointF(-1, 1));
        initializeWithGridPointsRec(QRectF(QPointF(gridRect.left(), yBottomCenter), QPointF(xLeftCenter + 1, gridRect.bottom())), pixelPrecision,
                                    node->children[bottomLeftChild], bottomStartRow, startColumn, columnCount);
 
        int bottomRightChild = node->childIndexForPoint(center + QPointF(1, 1));
        initializeWithGridPointsRec(QRectF(QPointF(xRightCenter, yBottomCenter), QPointF(gridRect.right(), gridRect.bottom())), pixelPrecision,
                                    node->children[bottomRightChild], bottomStartRow, rightStartColumn, columnCount);
 
    }
 
}

References GridIterationTools::calcGridSize(), KisSpatialContainer::SpatialNode::childIndexForPoint(), KisSpatialContainer::SpatialNode::children, initializeWithGridPointsRec(), KisSpatialContainer::SpatialNode::isLeaf, m_count, m_maxPointsInDict, m_nextNodeId, KisSpatialContainer::SpatialNode::maximumArea, KisSpatialContainer::SpatialNode::pointsCount, KisSpatialContainer::SpatialNode::pointsData, KisSpatialContainer::SpatialNode::xPartition, and KisSpatialContainer::SpatialNode::yPartition.

movePoint()

void KisSpatialContainer::movePoint	(	int	index,
		QPointF	positionBefore,
		QPointF	positionAfter )

Definition at line 161 of file KisSpatialContainer.cpp.

{
    movePointRec(index, positionBefore, positionAfter, m_root);
}

References m_root, and movePointRec().

movePointRec()

void KisSpatialContainer::movePointRec ( int index, QPointF positionBefore, QPointF positionAfter, SpatialNode * node )

private

Definition at line 306 of file KisSpatialContainer.cpp.

{
    if (!node) {
        return;
    }
    if (node->isLeaf) {
        for (int i = 0; i < node->pointsCount; i++) {
            if(node->pointsData[i].index == index) {
                node->pointsData[i].position = positionAfter;
            }
        }
        KisAlgebra2D::accumulateBounds(positionAfter, &node->maximumArea);
    } else {
        int childBefore = node->childIndexForPoint(positionBefore);
        int childAfter = node->childIndexForPoint(positionAfter);
        if (childBefore == childAfter) {
            movePointRec(index, positionBefore, positionAfter, node->children[childBefore]);
        } else {
            removePointRec(index, positionBefore, node->children[childBefore]);
            if (!node->children[childAfter]) {
                node->children[childAfter] = createNodeForPoint(index, positionAfter);
            } else {
                addPointRec(index, positionAfter, node->children[childAfter]);
            }
        }
    }
}

References KisAlgebra2D::accumulateBounds(), addPointRec(), KisSpatialContainer::SpatialNode::childIndexForPoint(), KisSpatialContainer::SpatialNode::children, createNodeForPoint(), KisSpatialContainer::SpatialNode::isLeaf, KisSpatialContainer::SpatialNode::maximumArea, movePointRec(), KisSpatialContainer::SpatialNode::pointsCount, KisSpatialContainer::SpatialNode::pointsData, and removePointRec().

removePoint()

void KisSpatialContainer::removePoint	(	int	index,
		QPointF	position )

Definition at line 156 of file KisSpatialContainer.cpp.

{
    removePointRec(index, position, m_root);
}

References m_root, and removePointRec().

removePointRec()

void KisSpatialContainer::removePointRec ( int index, QPointF position, SpatialNode * node )

private

Definition at line 258 of file KisSpatialContainer.cpp.

{
    if (!node) return;
    if (node->isLeaf) {
 
        auto sameIndex = [index] (const SpatialNodeData& item) {
            return item.index == index;
        };
        // quickest way: move the last item into the place where the found item was; keeping the order isn't necessary
        QVector<SpatialNodeData>::iterator foundItem = std::find_if(node->pointsData.begin(), node->pointsData.end(), sameIndex);
        if (foundItem != node->pointsData.end()) {
            QVector<SpatialNodeData>::reverse_iterator lastItem = node->pointsData.rbegin();
            *foundItem = *lastItem;
            node->pointsData.removeLast();
            node->pointsCount--;
        }
 
    } else {
        int childIndex = node->childIndexForPoint(position);
        SpatialNode* child = node->children[childIndex];
        if (child) {
            removePointRec(index, position, child);
            // this below isn't really necessary but keeps the tree tidy by removing no longer needed nodes
            if (child->isLeaf) {
                if (child->pointsCount == 0) {
                    // child = empty leaf
                    delete node->children[childIndex];
                    node->children[childIndex] = nullptr;
                    child = nullptr;
                }
            } else {
                bool foundExistingGrandChild = false;
                for (int i = 0; i < child->children.length(); i++) {
                    if (child->children[i]) {
                        foundExistingGrandChild = true;
                    }
                }
                if (!foundExistingGrandChild) {
                    // child = empty parent node
                    delete node->children[childIndex];
                    node->children[childIndex] = nullptr;
                    child = nullptr;
                }
            }
        }
    }
}

References KisSpatialContainer::SpatialNode::childIndexForPoint(), KisSpatialContainer::SpatialNode::children, KisSpatialContainer::SpatialNode::isLeaf, KisSpatialContainer::SpatialNode::pointsCount, KisSpatialContainer::SpatialNode::pointsData, and removePointRec().

toVector()

QVector< QPointF > KisSpatialContainer::toVector

(

)

Definition at line 166 of file KisSpatialContainer.cpp.

{
    if (m_count == 0) {
        return QVector<QPointF>();
    }
 
    QVector<QPointF> response;
    response.resize(m_count);
    gatherDataRec(response, m_root);
    return response;
 
}

References gatherDataRec(), m_count, and m_root.

Friends And Related Symbol Documentation

KisSpatialContainerTest

friend class KisSpatialContainerTest

friend

Definition at line 101 of file KisSpatialContainer.h.

Member Data Documentation

m_count

int KisSpatialContainer::m_count {0}

private

Definition at line 96 of file KisSpatialContainer.h.

{0};

m_maxPointsInDict

int KisSpatialContainer::m_maxPointsInDict = {100}

private

Definition at line 97 of file KisSpatialContainer.h.

{100};

m_nextNodeId

int KisSpatialContainer::m_nextNodeId = {0}

private

Definition at line 98 of file KisSpatialContainer.h.

{0}; // just for debug

m_root

SpatialNode* KisSpatialContainer::m_root {nullptr}

private

Definition at line 99 of file KisSpatialContainer.h.

{nullptr};

---

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

• libs/image/KisSpatialContainer.h
• libs/image/KisSpatialContainer.cpp