KisRegion Class Reference

#include <KisRegion.h>

Inheritance diagram for KisRegion:

Public Member Functions
QRect	boundingRect () const
bool	isEmpty () const
	KisRegion ()=default
	KisRegion (const KisRegion &rhs)=default
	KisRegion (const QRect &rect)
	KisRegion (const QVector< QRect > &rects)
	creates a region from a set of non-intersecting rectangles
	KisRegion (QVector< QRect > &&rects)
	KisRegion (std::initializer_list< QRect > rects)
KisRegion &	operator&= (const QRect &rect)
KisRegion &	operator= (const KisRegion &rhs)
int	rectCount () const
QVector< QRect >	rects () const
QRegion	toQRegion () const
void	translate (int dx, int dy)
KisRegion	translated (int x, int y) const

Static Public Member Functions
static void	approximateOverlappingRects (QVector< QRect > &rects, int gridSize)
static KisRegion	fromOverlappingRects (const QVector< QRect > &rects, int gridSize)
static KisRegion	fromQRegion (const QRegion &region)
static void	makeGridLikeRectsUnique (QVector< QRect > &rects)
static QVector< QRect >::iterator	mergeSparseRects (QVector< QRect >::iterator beginIt, QVector< QRect >::iterator endIt)
	merge a set of rectangles into a smaller set of bigger rectangles

Private Member Functions
void	mergeAllRects ()

Private Attributes
QVector< QRect >	m_rects

Friends
KRITAGLOBAL_EXPORT bool	operator== (const KisRegion &lhs, const KisRegion &rhs)

Detailed Description

An more efficient (and more limited) replacement for QRegion.

Its main purpose it to be able to merge a huge set of rectangles into a smaller set of bigger rectangles, the same thing that QRegion is supposed to do. The main difference (and limitation) is: all the input rects must be non-intersecting. This requirement is perfectly fine for Krita's tiles, which do never intersect.

Definition at line 25 of file KisRegion.h.

Constructor & Destructor Documentation

KisRegion() [1/6]

KisRegion::KisRegion ( )

default

KisRegion() [2/6]

KisRegion::KisRegion ( const KisRegion & rhs )

default

KisRegion() [3/6]

KisRegion::KisRegion

(

const QRect &

rect

)

Definition at line 285 of file KisRegion.cpp.

{
    m_rects << rect;
}

References m_rects.

KisRegion() [4/6]

KisRegion::KisRegion

(

std::initializer_list< QRect >

rects

)

Definition at line 290 of file KisRegion.cpp.

    : m_rects(rects)
{
}

KisRegion() [5/6]

KisRegion::KisRegion

(

const QVector< QRect > &

rects

)

creates a region from a set of non-intersecting rectangles

Parameters

rects

rectangles that should be merged. Rectangles must not intersect.

Definition at line 295 of file KisRegion.cpp.

    : m_rects(rects)
{
    mergeAllRects();
}

References mergeAllRects().

KisRegion() [6/6]

KisRegion::KisRegion

(

QVector< QRect > &&

rects

)

Definition at line 301 of file KisRegion.cpp.

    : m_rects(rects)
{
    mergeAllRects();
}

References mergeAllRects().

Member Function Documentation

approximateOverlappingRects()

void KisRegion::approximateOverlappingRects ( QVector< QRect > & rects, int gridSize )

static

Simplifies rects in a way that they don't overlap anymore. The actual resulting area may be larger than original rects, but not more than gridSize in any dimension.

Definition at line 240 of file KisRegion.cpp.

{
    using namespace detail;
 
    if (rects.isEmpty()) return;
 
    QVector<QRect> rowsBuf;
    QVector<QRect> intermediate;
    QVector<QRect> tempBuf[2];
 
    splitRects<VerticalSplitPolicy>(rects.begin(), rects.end(),
                                    std::back_inserter(rowsBuf),
                                    tempBuf, gridSize, VoidNoOp());
 
    rects.clear();
    KIS_SAFE_ASSERT_RECOVER_NOOP(tempBuf[0].isEmpty());
    KIS_SAFE_ASSERT_RECOVER_NOOP(tempBuf[1].isEmpty());
 
    auto rowBegin = rowsBuf.begin();
    while (rowBegin != rowsBuf.end()) {
        auto rowEnd = std::upper_bound(rowBegin, rowsBuf.end(),
                                       QRect(rowBegin->x(),
                                             rowBegin->y() + gridSize - 1,
                                             1,1),
                                       VerticalSplitPolicy::rowIsLess);
 
        splitRects<HorizontalSplitPolicy>(rowBegin, rowEnd,
                                          std::back_inserter(intermediate),
                                          tempBuf, gridSize,
                                          MergeRectsOp(intermediate, rects));
        rowBegin = rowEnd;
 
        KIS_SAFE_ASSERT_RECOVER_NOOP(intermediate.isEmpty());
        KIS_SAFE_ASSERT_RECOVER_NOOP(tempBuf[0].isEmpty());
        KIS_SAFE_ASSERT_RECOVER_NOOP(tempBuf[1].isEmpty());
    }
}

References isEmpty(), KIS_SAFE_ASSERT_RECOVER_NOOP, and rects().

boundingRect()

QRect KisRegion::boundingRect

(

)

const

Definition at line 327 of file KisRegion.cpp.

{
    return std::accumulate(m_rects.constBegin(), m_rects.constEnd(), QRect(), std::bit_or<QRect>());
}

References m_rects.

fromOverlappingRects()

KisRegion KisRegion::fromOverlappingRects ( const QVector< QRect > & rects, int gridSize )

static

Approximates a KisRegion from rects, which may overlap. The resulting KisRegion may be larger than the original set of rects, but it is guaranteed to cover it completely.

Definition at line 385 of file KisRegion.cpp.

{
    QVector<QRect> tmp = rects;
    approximateOverlappingRects(tmp, gridSize);
    return KisRegion(tmp);
}

References approximateOverlappingRects(), KisRegion(), and rects().

fromQRegion()

KisRegion KisRegion::fromQRegion ( const QRegion & region )

static

Definition at line 373 of file KisRegion.cpp.

{
    KisRegion result;
    result.m_rects.clear();
    QRegion::const_iterator begin = region.begin();
    while (begin != region.end()) {
        result.m_rects << *begin;
        begin++;
    }
    return result;
}

References m_rects.

isEmpty()

bool KisRegion::isEmpty

(

)

const

Definition at line 342 of file KisRegion.cpp.

{
    return boundingRect().isEmpty();
}

References boundingRect().

makeGridLikeRectsUnique()

void KisRegion::makeGridLikeRectsUnique ( QVector< QRect > & rects )

static

Definition at line 278 of file KisRegion.cpp.

{
    std::sort(rects.begin(), rects.end(), detail::HorizontalMergePolicy::elementIsLess);
    auto it = std::unique(rects.begin(), rects.end());
    rects.erase(it, rects.end());
}

References detail::HorizontalMergePolicy::elementIsLess(), and rects().

mergeAllRects()

void KisRegion::mergeAllRects ( )

private

Definition at line 392 of file KisRegion.cpp.

{
    auto endIt = mergeSparseRects(m_rects.begin(), m_rects.end());
    m_rects.erase(endIt, m_rects.end());
}

References m_rects, and mergeSparseRects().

mergeSparseRects()

QVector< QRect >::iterator KisRegion::mergeSparseRects ( QVector< QRect >::iterator beginIt, QVector< QRect >::iterator endIt )

static

merge a set of rectangles into a smaller set of bigger rectangles

The algorithm does two passes over the rectangles. First it tries to merge all the rectangles horizontally, then vertically. The merge happens in-place, that is, all the merged elements will be moved to the front of the original range.

The final range is defined by [beginIt, retvalIt)

Parameters

beginIt	iterator to the beginning of the source range
endIt	iterator to the end of the source range

Returns

iteration pointing past the last element of the merged range

Definition at line 233 of file KisRegion.cpp.

{
    endIt = detail::mergeRects(beginIt, endIt, detail::HorizontalMergePolicy());
    endIt = detail::mergeRects(beginIt, endIt, detail::VerticalMergePolicy());
    return endIt;
}

References detail::mergeRects().

operator&=()

KisRegion & KisRegion::operator&=

(

const QRect &

rect

)

Definition at line 313 of file KisRegion.cpp.

{
    for (auto it = m_rects.begin(); it != m_rects.end(); /* noop */) {
        *it &= rect;
        if (it->isEmpty()) {
            it = m_rects.erase(it);
        } else {
            ++it;
        }
    }
    mergeAllRects();
    return *this;
}

References m_rects, and mergeAllRects().

operator=()

KisRegion & KisRegion::operator=

(

const KisRegion &

rhs

)

Definition at line 307 of file KisRegion.cpp.

{
    m_rects = rhs.m_rects;
    return *this;
}

References m_rects.

rectCount()

int KisRegion::rectCount

(

)

const

Definition at line 337 of file KisRegion.cpp.

{
    return m_rects.size();
}

References m_rects.

rects()

QVector< QRect > KisRegion::rects

(

)

const

Definition at line 332 of file KisRegion.cpp.

{
    return m_rects;
}

References m_rects.

toQRegion()

QRegion KisRegion::toQRegion

(

)

const

Definition at line 347 of file KisRegion.cpp.

{
    // TODO: utilize QRegion::setRects to make creation of QRegion much
    //       faster. The only reason why we cannot use it "as is", is that our m_rects
    //       do not satisfy the second setRects()'s precondition: "All rectangles with
    //       a given top coordinate must have the same height". We can implement a
    //       simple algorithm for cropping m_rects, and it will be much faster than
    //       constructing QRegion iteratively.
 
    return std::accumulate(m_rects.constBegin(), m_rects.constEnd(), QRegion(), std::bit_or<QRegion>());
}

References m_rects.

translate()

void KisRegion::translate	(	int	dx,
		int	dy )

Definition at line 359 of file KisRegion.cpp.

{
    std::transform(m_rects.begin(), m_rects.end(),
                   m_rects.begin(),
                   [dx, dy] (const QRect &rc) { return rc.translated(dx, dy); });
}

References m_rects.

translated()

KisRegion KisRegion::translated	(	int	x,
		int	y ) const

Definition at line 366 of file KisRegion.cpp.

{
    KisRegion region(*this);
    region.translate(dx, dy);
    return region;
}

References translate().

Friends And Related Symbol Documentation

operator==

KRITAGLOBAL_EXPORT bool operator== ( const KisRegion & lhs, const KisRegion & rhs )

friend

Definition at line 398 of file KisRegion.cpp.

{
    return lhs.m_rects == rhs.m_rects;
}

Member Data Documentation

m_rects

QVector<QRect> KisRegion::m_rects

private

Definition at line 97 of file KisRegion.h.

---

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

• libs/global/KisRegion.h
• libs/global/KisRegion.cpp