src/gui/painting/qregion_unix.cpp File Reference

#include "qregion.h"
#include "qpainterpath.h"
#include "qpolygon.h"
#include "qbuffer.h"
#include "qimage.h"
#include <qdebug.h>
#include "qbitmap.h"
#include <stdlib.h>
#include "qregion_x11.cpp"
#include <limits.h>

Include dependency graph for qregion_unix.cpp:

Go to the source code of this file.

Classes
struct	QRegionPrivate
struct	_POINTBLOCK
struct	BRESINFO
struct	_EdgeTableEntry
struct	_ScanLineList
struct	EdgeTable
struct	_ScanLineListBlock
Defines
#define	RectangleOut   0
#define	RectangleIn   1
#define	RectanglePart   2
#define	EvenOddRule   0
#define	WindingRule   1
#define	EXTENTCHECK(r1, r2)
#define	EXTENTS(r, idRect)
#define	MEMCHECK(dest, rect, firstrect)
#define	NUMPTSTOBUFFER   200
#define	MERGERECT(r)
#define	BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2)
#define	BRESINCRPGON(d, minval, m, m1, incr1, incr2)
#define	BRESINITPGONSTRUCT(dmaj, min1, min2, bres)
#define	BRESINCRPGONSTRUCT(bres)   BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
#define	CLOCKWISE   1
#define	COUNTERCLOCKWISE   -1
#define	SLLSPERBLOCK   25
#define	EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
#define	EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
#define	LARGE_COORDINATE   1000000
#define	SMALL_COORDINATE   -LARGE_COORDINATE
#define	AddSpan
Typedefs
typedef void(*)	OverlapFunc (register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End, register const QRect *r2, const QRect *r2End, register int y1, register int y2)
typedef void(*)	NonOverlapFunc (register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
typedef _POINTBLOCK	POINTBLOCK
typedef _EdgeTableEntry	EdgeTableEntry
typedef _ScanLineList	ScanLineList
typedef _ScanLineListBlock	ScanLineListBlock
Functions
static bool	isEmpty (const QRegionPrivate *preg)
static bool	EqualRegion (const QRegionPrivate *r1, const QRegionPrivate *r2)
static void	UnionRegion (const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest)
static void	miRegionOp (register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2, OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func, NonOverlapFunc nonOverlap2Func)
static void	UnionRectWithRegion (register const QRect *rect, const QRegionPrivate *source, QRegionPrivate &dest)
static void	miSetExtents (QRegionPrivate &dest)
static void	OffsetRegion (register QRegionPrivate &region, register int x, register int y)
static void	miIntersectO (register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End, register const QRect *r2, const QRect *r2End, int y1, int y2)
static int	miCoalesce (register QRegionPrivate &dest, int prevStart, int curStart)
static void	miUnionNonO (register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
static void	miUnionO (register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End, register const QRect *r2, const QRect *r2End, register int y1, register int y2)
static void	miSubtractNonO1 (register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
static void	miSubtractO (register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End, register const QRect *r2, const QRect *r2End, register int y1, register int y2)
static void	SubtractRegion (QRegionPrivate *regM, QRegionPrivate *regS, register QRegionPrivate &dest)
static void	XorRegion (QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest)
static bool	PointInRegion (QRegionPrivate *pRegion, int x, int y)
static bool	RectInRegion (register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
static void	InsertEdgeInET (EdgeTable *ET, EdgeTableEntry *ETE, int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock)
static void	CreateETandAET (register int count, register const QPoint *pts, EdgeTable *ET, EdgeTableEntry *AET, register EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
static void	loadAET (register EdgeTableEntry *AET, register EdgeTableEntry *ETEs)
static void	computeWAET (register EdgeTableEntry *AET)
static int	InsertionSort (register EdgeTableEntry *AET)
static void	FreeStorage (register ScanLineListBlock *pSLLBlock)
static void	PtsToRegion (register int numFullPtBlocks, register int iCurPtBlock, POINTBLOCK *FirstPtBlock, QRegionPrivate *reg)
static QRegionPrivate *	PolygonRegion (const QPoint *Pts, int Count, int rule)
QRegionPrivate *	qt_bitmapToRegion (const QBitmap &bitmap)

---

Define Documentation

#define AddSpan

Value:

{ \
            xr.setCoords(prev1, y, x-1, y); \
            UnionRectWithRegion(&xr, region, *region); \
        }

#define BRESINCRPGON	(	d,
		minval,
		m,
		m1,
		incr1,
		incr2		)

Value:

{ \
    if (m1 > 0) { \
        if (d > 0) { \
            minval += m1; \
            d += incr1; \
        } \
        else { \
            minval += m; \
            d += incr2; \
        } \
    } else {\
        if (d >= 0) { \
            minval += m1; \
            d += incr1; \
        } \
        else { \
            minval += m; \
            d += incr2; \
        } \
    } \
}

Definition at line 1528 of file qregion_unix.cpp.

#define BRESINCRPGONSTRUCT

(

bres

)

BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)

Definition at line 1570 of file qregion_unix.cpp.

#define BRESINITPGON	(	dy,
		x1,
		x2,
		xStart,
		d,
		m,
		m1,
		incr1,
		incr2		)

Value:

{ \
    int dx;      /* local storage */ \
\
    /* \
     *  if the edge is horizontal, then it is ignored \
     *  and assumed not to be processed.  Otherwise, do this stuff. \
     */ \
    if ((dy) != 0) { \
        xStart = (x1); \
        dx = (x2) - xStart; \
        if (dx < 0) { \
            m = dx / (dy); \
            m1 = m - 1; \
            incr1 = -2 * dx + 2 * (dy) * m1; \
            incr2 = -2 * dx + 2 * (dy) * m; \
            d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
        } else { \
            m = dx / (dy); \
            m1 = m + 1; \
            incr1 = 2 * dx - 2 * (dy) * m1; \
            incr2 = 2 * dx - 2 * (dy) * m; \
            d = -2 * m * (dy) + 2 * dx; \
        } \
    } \
}

Definition at line 1505 of file qregion_unix.cpp.

#define BRESINITPGONSTRUCT	(	dmaj,
		min1,
		min2,
		bres		)

Value:

BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
                     bres.m, bres.m1, bres.incr1, bres.incr2)

Definition at line 1566 of file qregion_unix.cpp.

Referenced by CreateETandAET().

#define CLOCKWISE   1

Definition at line 1624 of file qregion_unix.cpp.

#define COUNTERCLOCKWISE   -1

Definition at line 1625 of file qregion_unix.cpp.

#define EVALUATEEDGEEVENODD	(	pAET,
		pPrevAET,
		y		)

Value:

{ \
   if (pAET->ymax == y) {          /* leaving this edge */ \
      pPrevAET->next = pAET->next; \
      pAET = pPrevAET->next; \
      if (pAET) \
         pAET->back = pPrevAET; \
   } \
   else { \
      BRESINCRPGONSTRUCT(pAET->bres) \
      pPrevAET = pAET; \
      pAET = pAET->next; \
   } \
}

Definition at line 1701 of file qregion_unix.cpp.

Referenced by PolygonRegion().

#define EVALUATEEDGEWINDING	(	pAET,
		pPrevAET,
		y,
		fixWAET		)

Value:

{ \
   if (pAET->ymax == y) {          /* leaving this edge */ \
      pPrevAET->next = pAET->next; \
      pAET = pPrevAET->next; \
      fixWAET = 1; \
      if (pAET) \
         pAET->back = pPrevAET; \
   } \
   else { \
      BRESINCRPGONSTRUCT(pAET->bres) \
      pPrevAET = pAET; \
      pAET = pAET->next; \
   } \
}

Definition at line 1678 of file qregion_unix.cpp.

Referenced by PolygonRegion().

#define EvenOddRule   0

Definition at line 193 of file qregion_unix.cpp.

Referenced by QX11PaintEnginePrivate::fillPolygon_dev(), and PolygonRegion().

#define EXTENTCHECK	(	r1,
		r2		)

Value:

((r1)->right() >= (r2)->left() && \
         (r1)->left() <= (r2)->right() && \
         (r1)->bottom() >= (r2)->top() && \
         (r1)->top() <= (r2)->bottom())

Definition at line 255 of file qregion_unix.cpp.

Referenced by RectInRegion(), and SubtractRegion().

#define EXTENTS	(	r,
		idRect		)

Value:

{\
            if((r)->left() < (idRect)->extents.left())\
              (idRect)->extents.setLeft((r)->left());\
            if((r)->top() < (idRect)->extents.top())\
              (idRect)->extents.setTop((r)->top());\
            if((r)->right() > (idRect)->extents.right())\
              (idRect)->extents.setRight((r)->right());\
            if((r)->bottom() > (idRect)->extents.bottom())\
              (idRect)->extents.setBottom((r)->bottom());\
        }

Definition at line 264 of file qregion_unix.cpp.

#define LARGE_COORDINATE   1000000

Definition at line 1766 of file qregion_unix.cpp.

Referenced by CreateETandAET().

#define MEMCHECK	(	dest,
		rect,
		firstrect		)

Value:

{\
        if ((dest).numRects >= ((dest).rects.size()-1)){\
          firstrect.resize(firstrect.size() * 2); \
          (rect) = (firstrect).data() + (dest).numRects;\
        }\
      }

Definition at line 278 of file qregion_unix.cpp.

Referenced by miIntersectO(), miSubtractNonO1(), miSubtractO(), and miUnionNonO().

#define MERGERECT

(

r

)

Value:

if ((dest.numRects != 0) &&  \
        (pNextRect[-1].top() == y1) &&  \
        (pNextRect[-1].bottom() == y2) &&  \
        (pNextRect[-1].right() >= r->left()-1)) { \
        if (pNextRect[-1].right() < r->right()) { \
            pNextRect[-1].setRight(r->right());  \
            Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
        }  \
    } else { \
        MEMCHECK(dest, pNextRect, dest.rects)  \
        pNextRect->setCoords(r->left(), y1, r->right(), y2); \
        dest.numRects++;  \
        pNextRect++;  \
    }  \
    r++;

Referenced by miUnionO().

#define NUMPTSTOBUFFER   200

Definition at line 290 of file qregion_unix.cpp.

Referenced by PolygonRegion(), and PtsToRegion().

#define RectangleIn   1

Definition at line 191 of file qregion_unix.cpp.

Referenced by RectInRegion().

#define RectangleOut   0

Definition at line 190 of file qregion_unix.cpp.

Referenced by RectInRegion().

#define RectanglePart   2

Definition at line 192 of file qregion_unix.cpp.

Referenced by RectInRegion().

#define SLLSPERBLOCK   25

Definition at line 1656 of file qregion_unix.cpp.

Referenced by InsertEdgeInET(), and miInsertEdgeInET().

#define SMALL_COORDINATE   -LARGE_COORDINATE

Definition at line 1767 of file qregion_unix.cpp.

Referenced by CreateETandAET().

#define WindingRule   1

Definition at line 194 of file qregion_unix.cpp.

Referenced by QX11PaintEnginePrivate::fillPolygon_dev().

---

Typedef Documentation

typedef struct _EdgeTableEntry EdgeTableEntry

typedef void(*) NonOverlapFunc(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)

Definition at line 181 of file qregion_unix.cpp.

typedef void(*) OverlapFunc(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End, register const QRect *r2, const QRect *r2End, register int y1, register int y2)

Definition at line 179 of file qregion_unix.cpp.

typedef struct _POINTBLOCK POINTBLOCK

typedef struct _ScanLineList ScanLineList

typedef struct _ScanLineListBlock ScanLineListBlock

---

Function Documentation

static void computeWAET

(

register EdgeTableEntry *

AET

)

[static]

Definition at line 1989 of file qregion_unix.cpp.

References _EdgeTableEntry::next, and _EdgeTableEntry::nextWETE.

Referenced by PolygonRegion().

{
    register EdgeTableEntry *pWETE;
    register int inside = 1;
    register int isInside = 0;

    AET->nextWETE = 0;
    pWETE = AET;
    AET = AET->next;
    while (AET) {
        if (AET->ClockWise)
            ++isInside;
        else
            --isInside;

        if (!inside && !isInside || inside && isInside) {
            pWETE->nextWETE = AET;
            pWETE = AET;
            inside = !inside;
        }
        AET = AET->next;

static void CreateETandAET	(	register int	count,
		register const QPoint *	pts,
		EdgeTable *	ET,
		EdgeTableEntry *	AET,
		register EdgeTableEntry *	pETEs,
		ScanLineListBlock *	pSLLBlock
	)			[static]

Definition at line 1858 of file qregion_unix.cpp.

References _EdgeTableEntry::back, _EdgeTableEntry::bres, BRESINITPGONSTRUCT, InsertEdgeInET(), LARGE_COORDINATE, BRESINFO::minor_axis, _ScanLineListBlock::next, _ScanLineList::next, _EdgeTableEntry::next, _EdgeTableEntry::nextWETE, EdgeTable::scanlines, SMALL_COORDINATE, QPoint::x(), QPoint::y(), EdgeTable::ymax, and EdgeTable::ymin.

Referenced by PolygonRegion().

{
    register const QPoint *top,
                          *bottom,
                          *PrevPt,
                          *CurrPt;
    int iSLLBlock = 0;
    int dy;

    if (count < 2)
        return;

    /*
     *  initialize the Active Edge Table
     */
    AET->next = 0;
    AET->back = 0;
    AET->nextWETE = 0;
    AET->bres.minor_axis = SMALL_COORDINATE;

    /*
     *  initialize the Edge Table.
     */
    ET->scanlines.next = 0;
    ET->ymax = SMALL_COORDINATE;
    ET->ymin = LARGE_COORDINATE;
    pSLLBlock->next = 0;

    PrevPt = &pts[count - 1];

    /*
     *  for each vertex in the array of points.
     *  In this loop we are dealing with two vertices at
     *  a time -- these make up one edge of the polygon.
     */
    while (count--) {
        CurrPt = pts++;

        /*
         *  find out which point is above and which is below.
         */
        if (PrevPt->y() > CurrPt->y()) {
            bottom = PrevPt;
            top = CurrPt;
            pETEs->ClockWise = 0;
        } else {
            bottom = CurrPt;
            top = PrevPt;
            pETEs->ClockWise = 1;
        }

        /*
         * don't add horizontal edges to the Edge table.
         */
        if (bottom->y() != top->y()) {
            pETEs->ymax = bottom->y() - 1;  /* -1 so we don't get last scanline */

            /*
             *  initialize integer edge algorithm
             */
            dy = bottom->y() - top->y();
            BRESINITPGONSTRUCT(dy, top->x(), bottom->x(), pETEs->bres)

            InsertEdgeInET(ET, pETEs, top->y(), &pSLLBlock, &iSLLBlock);

            if (PrevPt->y() > ET->ymax)
                ET->ymax = PrevPt->y();
            if (PrevPt->y() < ET->ymin)
                ET->ymin = PrevPt->y();
            ++pETEs;
        }

Here is the call graph for this function:

static bool EqualRegion	(	const QRegionPrivate *	r1,
		const QRegionPrivate *	r2
	)			[static]

Definition at line 1320 of file qregion_unix.cpp.

References QVector< T >::constData(), QRegionPrivate::extents, i, QRegionPrivate::numRects, and QRegionPrivate::rects.

Referenced by SubtractRegion(), and UnionRegion().

{
    if (r1->numRects != r2->numRects) {
        return false;
    } else if (r1->numRects == 0) {
        return true;
    } else if (r1->extents != r2->extents) {
        return false;
    } else {
        const QRect *rr1 = r1->rects.constData();
        const QRect *rr2 = r2->rects.constData();
        for (int i = 0; i < r1->numRects; ++i, ++rr1, ++rr2) {
            if (*rr1 != *rr2)
                return false;
        }
    }

    return true;
}

Here is the call graph for this function:

static void FreeStorage

(

register ScanLineListBlock *

pSLLBlock

)

[static]

Definition at line 2056 of file qregion_unix.cpp.

References _ScanLineListBlock::next.

Referenced by PolygonRegion().

{
    register ScanLineListBlock *tmpSLLBlock;

    while (pSLLBlock) {
        tmpSLLBlock = pSLLBlock->next;
        free(pSLLBlock);

static void InsertEdgeInET	(	EdgeTable *	ET,
		EdgeTableEntry *	ETE,
		int	scanline,
		ScanLineListBlock **	SLLBlock,
		int *	iSLLBlock
	)			[static]

Definition at line 1778 of file qregion_unix.cpp.

References _EdgeTableEntry::bres, _ScanLineList::edgelist, BRESINFO::minor_axis, _ScanLineListBlock::next, _ScanLineList::next, _EdgeTableEntry::next, NULL, _ScanLineList::scanline, EdgeTable::scanlines, SLLSPERBLOCK, and start.

Referenced by CreateETandAET().

{
    register EdgeTableEntry *start, *prev;
    register ScanLineList *pSLL, *pPrevSLL;
    ScanLineListBlock *tmpSLLBlock;

    /*
     * find the right bucket to put the edge into
     */
    pPrevSLL = &ET->scanlines;
    pSLL = pPrevSLL->next;
    while (pSLL && (pSLL->scanline < scanline)) {
        pPrevSLL = pSLL;
        pSLL = pSLL->next;
    }

    /*
     * reassign pSLL (pointer to ScanLineList) if necessary
     */
    if ((!pSLL) || (pSLL->scanline > scanline)) {
        if (*iSLLBlock > SLLSPERBLOCK-1)
        {
            tmpSLLBlock =
                  (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
            (*SLLBlock)->next = tmpSLLBlock;
            tmpSLLBlock->next = (ScanLineListBlock *)NULL;
            *SLLBlock = tmpSLLBlock;
            *iSLLBlock = 0;
        }
        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);

        pSLL->next = pPrevSLL->next;
        pSLL->edgelist = (EdgeTableEntry *)NULL;
        pPrevSLL->next = pSLL;
    }
    pSLL->scanline = scanline;

    /*
     * now insert the edge in the right bucket
     */
    prev = 0;
    start = pSLL->edgelist;
    while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) {
        prev = start;
        start = start->next;
    }
    ETE->next = start;

    if (prev)
        prev->next = ETE;

static int InsertionSort

(

register EdgeTableEntry *

AET

)

[static]

Definition at line 2023 of file qregion_unix.cpp.

References _EdgeTableEntry::back, _EdgeTableEntry::bres, BRESINFO::minor_axis, and _EdgeTableEntry::next.

Referenced by PolygonRegion().

{
    register EdgeTableEntry *pETEchase;
    register EdgeTableEntry *pETEinsert;
    register EdgeTableEntry *pETEchaseBackTMP;
    register int changed = 0;

    AET = AET->next;
    while (AET) {
        pETEinsert = AET;
        pETEchase = AET;
        while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
            pETEchase = pETEchase->back;

        AET = AET->next;
        if (pETEchase != pETEinsert) {
            pETEchaseBackTMP = pETEchase->back;
            pETEinsert->back->next = AET;
            if (AET)
                AET->back = pETEinsert->back;
            pETEinsert->next = pETEchase;
            pETEchase->back->next = pETEinsert;
            pETEchase->back = pETEinsert;
            pETEinsert->back = pETEchaseBackTMP;
            changed = 1;
        }

static bool isEmpty

(

const QRegionPrivate *

preg

)

[inline, static]

Definition at line 173 of file qregion_unix.cpp.

References QRegionPrivate::numRects.

Referenced by qdesigner_internal::FormWindow::absoluteDir(), qdesigner_internal::FindIconDialog::accept(), qdesigner_internal::QrcView::acceptDrop(), QSvgStructureNode::addChild(), Q3Url::addPath(), Q3ActionGroup::addTo(), qdesigner_internal::FormWindowWidgetStack::addTool(), QSvgNode::appendStyleProperty(), Browser::Browser(), Q3Action::clearStatusText(), ConnectionManager::clientId(), TextEdit::clipboardDataChanged(), collision_double_dispatch(), SourceTextEdit::contextMenuEvent(), QApplicationPrivate::createEventDispatcher(), QCoreApplicationPrivate::createEventDispatcher(), QThreadPrivate::createEventDispatcher(), Ui3Reader::createFormImpl(), DocuParser::createParser(), createReadHandler(), Q3Url::dirPath(), Q3TextDocument::draw(), QObject::dumpObjectInfo(), QSet< Feature * >::empty(), QMap< int, QFrameInfo >::empty(), TextEdit::filePrintPdf(), QDropData::formats_sys(), QRingBuffer::getChar(), QDockWidgetLayout::getGrid(), getLprPrinters(), Q3ListBoxPixmap::height(), qdesigner_internal::WidgetDataBase::indexOfObject(), isNull(), Q3PointArray::isNull(), QTextEdit::keyPressEvent(), QDialogButtonBoxPrivate::layoutButtons(), main(), merge(), QUrlPrivate::mergePaths(), Q3Ftp::operationListChildren(), Q3Ftp::operationRemove(), Q3Ftp::operationRename(), Q3TextEdit::optimSelectedText(), Q3TextEdit::optimText(), Q3ListBoxPixmap::paint(), Mouse::paint(), Q3TextEdit::paragraphLength(), QXmlSimpleReaderPrivate::parseContent(), Semantic::parseDeclaration(), Semantic::parseNamespace(), PointInRegion(), ProjectPorter::portProFile(), QXmlSimpleReaderPrivate::processReference(), QCss::Selector::pseudoState(), qDBusGenerateMetaObjectXml(), QSessionManager::QSessionManager(), QXmlSimpleReaderPrivate::reportEndEntities(), qdesigner_internal::WidgetBoxTreeView::save(), MetaTranslator::save(), QSqlRelationalTableModel::selectStatement(), QDockWidgetLayout::separatorRect(), Q3Url::setFileName(), QDockWidgetLayout::setGrid(), qdesigner_internal::FindIconDialog::setPaths(), QAccessible::setRootObject(), QApplication::setStyle(), TextEdit::setupEditActions(), QUiLoaderPrivate::setupWidgetMap(), QSvgHandler::startElement(), SubtractRegion(), QAccessibleWidget::text(), Feature::toHtml(), UnionRegion(), QAccessible::updateAccessibility(), qdesigner_internal::NewActionDialog::updateButtons(), LocationDialog::updateLocationsTable(), QWorkspaceChild::updateMask(), qdesigner_internal::SignalSlotConnection::updateVisibility(), QTestAccessibility::verifyEvent(), Q3ListBoxPixmap::width(), and FeatureTreeModel::~FeatureTreeModel().

{
    return !preg || preg->numRects == 0;
}

static void loadAET	(	register EdgeTableEntry *	AET,
		register EdgeTableEntry *	ETEs
	)			[static]

Definition at line 1945 of file qregion_unix.cpp.

References _EdgeTableEntry::back, and _EdgeTableEntry::next.

Referenced by PolygonRegion().

{
    register EdgeTableEntry *pPrevAET;
    register EdgeTableEntry *tmp;

    pPrevAET = AET;
    AET = AET->next;
    while (ETEs) {
        while (AET && AET->bres.minor_axis < ETEs->bres.minor_axis) {
            pPrevAET = AET;
            AET = AET->next;
        }
        tmp = ETEs->next;
        ETEs->next = AET;
        if (AET)
            AET->back = ETEs;
        ETEs->back = pPrevAET;
        pPrevAET->next = ETEs;
        pPrevAET = ETEs;

static int miCoalesce	(	register QRegionPrivate &	dest,
		int	prevStart,
		int	curStart
	)			[static]

Definition at line 564 of file qregion_unix.cpp.

References QRect::bottom(), QRect::left(), QRect::right(), QRect::setBottom(), and QRect::top().

Referenced by miRegionOp().

{
    register QRect *pPrevBox;   /* Current box in previous band */
    register QRect *pCurBox;    /* Current box in current band */
    register QRect *pRegEnd;    /* End of region */
    int curNumRects;    /* Number of rectangles in current band */
    int prevNumRects;   /* Number of rectangles in previous band */
    int bandY1;         /* Y1 coordinate for current band */
    QRect *rData = dest.rects.data();

    pRegEnd = rData + dest.numRects;

    pPrevBox = rData + prevStart;
    prevNumRects = curStart - prevStart;

    /*
     * Figure out how many rectangles are in the current band. Have to do
     * this because multiple bands could have been added in miRegionOp
     * at the end when one region has been exhausted.
     */
    pCurBox = rData + curStart;
    bandY1 = pCurBox->top();
    for (curNumRects = 0; pCurBox != pRegEnd && pCurBox->top() == bandY1; ++curNumRects) {
        ++pCurBox;
    }

    if (pCurBox != pRegEnd) {
        /*
         * If more than one band was added, we have to find the start
         * of the last band added so the next coalescing job can start
         * at the right place... (given when multiple bands are added,
         * this may be pointless -- see above).
         */
        --pRegEnd;
        while ((pRegEnd - 1)->top() == pRegEnd->top())
            --pRegEnd;
        curStart = pRegEnd - rData;
        pRegEnd = rData + dest.numRects;
    }

    if (curNumRects == prevNumRects && curNumRects != 0) {
        pCurBox -= curNumRects;
        /*
         * The bands may only be coalesced if the bottom of the previous
         * matches the top scanline of the current.
         */
        if (pPrevBox->bottom() == pCurBox->top() - 1) {
            /*
             * Make sure the bands have boxes in the same places. This
             * assumes that boxes have been added in such a way that they
             * cover the most area possible. I.e. two boxes in a band must
             * have some horizontal space between them.
             */
            do {
                if (pPrevBox->left() != pCurBox->left() || pPrevBox->right() != pCurBox->right()) {
                     // The bands don't line up so they can't be coalesced.
                    return curStart;
                }
                ++pPrevBox;
                ++pCurBox;
                --prevNumRects;
            } while (prevNumRects != 0);

            dest.numRects -= curNumRects;
            pCurBox -= curNumRects;
            pPrevBox -= curNumRects;

            /*
             * The bands may be merged, so set the bottom y of each box
             * in the previous band to that of the corresponding box in
             * the current band.
             */
            do {
                pPrevBox->setBottom(pCurBox->bottom());
#ifdef QT_EXPERIMENTAL_REGIONS
                dest.updateInnerRect(*pPrevBox);
#endif
                ++pPrevBox;
                ++pCurBox;
                curNumRects -= 1;
            } while (curNumRects != 0);

            /*
             * If only one band was added to the region, we have to backup
             * curStart to the start of the previous band.
             *
             * If more than one band was added to the region, copy the
             * other bands down. The assumption here is that the other bands
             * came from the same region as the current one and no further
             * coalescing can be done on them since it's all been done
             * already... curStart is already in the right place.
             */
            if (pCurBox == pRegEnd) {
                curStart = prevStart;
            } else {
                do {
                    *pPrevBox++ = *pCurBox++;
#ifdef QT_EXPERIMENTAL_REGIONS
                    dest.updateInnerRect(*pPrevBox);
#endif
                } while (pCurBox != pRegEnd);
            }
        }
    }
    return curStart;
}

Here is the call graph for this function:

static void miIntersectO	(	register QRegionPrivate &	dest,
		register const QRect *	r1,
		const QRect *	r1End,
		register const QRect *	r2,
		const QRect *	r2End,
		int	y1,
		int	y2
	)			[static]

Definition at line 499 of file qregion_unix.cpp.

References MEMCHECK, qMax(), qMin(), and QRect::setCoords().

{
    register int x1;
    register int x2;
    register QRect *pNextRect;

    pNextRect = dest.rects.data() + dest.numRects;

    while (r1 != r1End && r2 != r2End) {
        x1 = qMax(r1->left(), r2->left());
        x2 = qMin(r1->right(), r2->right());

        /*
         * If there's any overlap between the two rectangles, add that
         * overlap to the new region.
         * There's no need to check for subsumption because the only way
         * such a need could arise is if some region has two rectangles
         * right next to each other. Since that should never happen...
         */
        if (x1 <= x2) {
            Q_ASSERT(y1 <= y2);
            MEMCHECK(dest, pNextRect, dest.rects)
            pNextRect->setCoords(x1, y1, x2, y2);
            ++dest.numRects;
            ++pNextRect;
        }

        /*
         * Need to advance the pointers. Shift the one that extends
         * to the right the least, since the other still has a chance to
         * overlap with that region's next rectangle, if you see what I mean.
         */
        if (r1->right() < r2->right()) {
            ++r1;
        } else if (r2->right() < r1->right()) {
            ++r2;
        } else {
            ++r1;
            ++r2;
        }
    }
}

Here is the call graph for this function:

static void miRegionOp	(	register QRegionPrivate &	dest,
		const QRegionPrivate *	reg1,
		const QRegionPrivate *	reg2,
		OverlapFunc	overlapFunc,
		NonOverlapFunc	nonOverlap1Func,
		NonOverlapFunc	nonOverlap2Func
	)			[static]

Definition at line 697 of file qregion_unix.cpp.

References QRect::bottom(), QVector< T >::data(), QRegionPrivate::extents, miCoalesce(), QRegionPrivate::numRects, qMax(), qMin(), QRegionPrivate::rects, and QRect::top().

Referenced by SubtractRegion(), and UnionRegion().

{
    register const QRect *r1;         // Pointer into first region
    register const QRect *r2;         // Pointer into 2d region
    const QRect *r1End;               // End of 1st region
    const QRect *r2End;               // End of 2d region
    register int ybot;          // Bottom of intersection
    register int ytop;          // Top of intersection
    int prevBand;               // Index of start of previous band in dest
    int curBand;                // Index of start of current band in dest
    register const QRect *r1BandEnd;  // End of current band in r1
    register const QRect *r2BandEnd;  // End of current band in r2
    int top;                    // Top of non-overlapping band
    int bot;                    // Bottom of non-overlapping band

    /*
     * Initialization:
     *  set r1, r2, r1End and r2End appropriately, preserve the important
     * parts of the destination region until the end in case it's one of
     * the two source regions, then mark the "new" region empty, allocating
     * another array of rectangles for it to use.
     */
    r1 = reg1->rects.data();
    r2 = reg2->rects.data();
    r1End = r1 + reg1->numRects;
    r2End = r2 + reg2->numRects;

    QVector<QRect> oldRects = dest.rects;

    dest.numRects = 0;

    /*
     * Allocate a reasonable number of rectangles for the new region. The idea
     * is to allocate enough so the individual functions don't need to
     * reallocate and copy the array, which is time consuming, yet we don't
     * have to worry about using too much memory. I hope to be able to
     * nuke the realloc() at the end of this function eventually.
     */
    dest.rects.resize(qMax(reg1->numRects,reg2->numRects) * 2);

    /*
     * Initialize ybot and ytop.
     * In the upcoming loop, ybot and ytop serve different functions depending
     * on whether the band being handled is an overlapping or non-overlapping
     * band.
     *  In the case of a non-overlapping band (only one of the regions
     * has points in the band), ybot is the bottom of the most recent
     * intersection and thus clips the top of the rectangles in that band.
     * ytop is the top of the next intersection between the two regions and
     * serves to clip the bottom of the rectangles in the current band.
     *  For an overlapping band (where the two regions intersect), ytop clips
     * the top of the rectangles of both regions and ybot clips the bottoms.
     */
    if (reg1->extents.top() < reg2->extents.top())
        ybot = reg1->extents.top() - 1;
    else
        ybot = reg2->extents.top() - 1;

    /*
     * prevBand serves to mark the start of the previous band so rectangles
     * can be coalesced into larger rectangles. qv. miCoalesce, above.
     * In the beginning, there is no previous band, so prevBand == curBand
     * (curBand is set later on, of course, but the first band will always
     * start at index 0). prevBand and curBand must be indices because of
     * the possible expansion, and resultant moving, of the new region's
     * array of rectangles.
     */
    prevBand = 0;

    do {
        curBand = dest.numRects;

        /*
         * This algorithm proceeds one source-band (as opposed to a
         * destination band, which is determined by where the two regions
         * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
         * rectangle after the last one in the current band for their
         * respective regions.
         */
        r1BandEnd = r1;
        while (r1BandEnd != r1End && r1BandEnd->top() == r1->top())
            ++r1BandEnd;

        r2BandEnd = r2;
        while (r2BandEnd != r2End && r2BandEnd->top() == r2->top())
            ++r2BandEnd;

        /*
         * First handle the band that doesn't intersect, if any.
         *
         * Note that attention is restricted to one band in the
         * non-intersecting region at once, so if a region has n
         * bands between the current position and the next place it overlaps
         * the other, this entire loop will be passed through n times.
         */
        if (r1->top() < r2->top()) {
            top = qMax(r1->top(), ybot + 1);
            bot = qMin(r1->bottom(), r2->top() - 1);

            if (nonOverlap1Func != 0 && bot >= top)
                (*nonOverlap1Func)(dest, r1, r1BandEnd, top, bot);
            ytop = r2->top();
        } else if (r2->top() < r1->top()) {
            top = qMax(r2->top(), ybot + 1);
            bot = qMin(r2->bottom(), r1->top() - 1);

            if (nonOverlap2Func != 0 && bot >= top)
                (*nonOverlap2Func)(dest, r2, r2BandEnd, top, bot);
            ytop = r1->top();
        } else {
            ytop = r1->top();
        }

        /*
         * If any rectangles got added to the region, try and coalesce them
         * with rectangles from the previous band. Note we could just do
         * this test in miCoalesce, but some machines incur a not
         * inconsiderable cost for function calls, so...
         */
        if (dest.numRects != curBand)
            prevBand = miCoalesce(dest, prevBand, curBand);

        /*
         * Now see if we've hit an intersecting band. The two bands only
         * intersect if ybot >= ytop
         */
        ybot = qMin(r1->bottom(), r2->bottom());
        curBand = dest.numRects;
        if (ybot >= ytop)
            (*overlapFunc)(dest, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);

        if (dest.numRects != curBand)
            prevBand = miCoalesce(dest, prevBand, curBand);

        /*
         * If we've finished with a band (y2 == ybot) we skip forward
         * in the region to the next band.
         */
        if (r1->bottom() == ybot)
            r1 = r1BandEnd;
        if (r2->bottom() == ybot)
            r2 = r2BandEnd;
    } while (r1 != r1End && r2 != r2End);

    /*
     * Deal with whichever region still has rectangles left.
     */
    curBand = dest.numRects;
    if (r1 != r1End) {
        if (nonOverlap1Func != 0) {
            do {
                r1BandEnd = r1;
                while (r1BandEnd < r1End && r1BandEnd->top() == r1->top())
                    ++r1BandEnd;
                (*nonOverlap1Func)(dest, r1, r1BandEnd, qMax(r1->top(), ybot + 1), r1->bottom());
                r1 = r1BandEnd;
            } while (r1 != r1End);
        }
    } else if ((r2 != r2End) && (nonOverlap2Func != 0)) {
        do {
            r2BandEnd = r2;
            while (r2BandEnd < r2End && r2BandEnd->top() == r2->top())
                 ++r2BandEnd;
            (*nonOverlap2Func)(dest, r2, r2BandEnd, qMax(r2->top(), ybot + 1), r2->bottom());
            r2 = r2BandEnd;
        } while (r2 != r2End);
    }

    if (dest.numRects != curBand)
        (void)miCoalesce(dest, prevBand, curBand);

    /*
     * A bit of cleanup. To keep regions from growing without bound,
     * we shrink the array of rectangles to match the new number of
     * rectangles in the region.
     *
     * Only do this stuff if the number of rectangles allocated is more than
     * twice the number of rectangles in the region (a simple optimization).
     */
#ifdef QT_EXPERIMENTAL_REGIONS
    if (qMax(4, dest.numRects) < (dest.rects.size() >> 1))
#else
    if (dest.numRects < (dest.rects.size() >> 1))
#endif
        dest.rects.resize(dest.numRects);
}

Here is the call graph for this function:

static void miSetExtents

(

QRegionPrivate &

dest

)

[static]

Definition at line 415 of file qregion_unix.cpp.

References QRect::bottom(), QVector< T >::constData(), QRegionPrivate::extents, QRect::left(), QRegionPrivate::numRects, QRegionPrivate::rects, QRect::right(), QRect::setBottom(), QRect::setCoords(), QRect::setLeft(), QRect::setRight(), QRect::setTop(), and QRect::top().

Referenced by SubtractRegion().

{
    register const QRect *pBox,
                         *pBoxEnd;
    register QRect *pExtents;

#ifdef QT_EXPERIMENTAL_REGIONS
    dest.innerRect.setCoords(0, 0, -1, -1);
    dest.innerArea = -1;
#endif
    if (dest.numRects == 0) {
        dest.extents.setCoords(0, 0, 0, 0);
        return;
    }

    pExtents = &dest.extents;
    pBox = dest.rects.constData();
    pBoxEnd = &pBox[dest.numRects - 1];

    /*
     * Since pBox is the first rectangle in the region, it must have the
     * smallest y1 and since pBoxEnd is the last rectangle in the region,
     * it must have the largest y2, because of banding. Initialize x1 and
     * x2 from  pBox and pBoxEnd, resp., as good things to initialize them
     * to...
     */
    pExtents->setLeft(pBox->left());
    pExtents->setTop(pBox->top());
    pExtents->setRight(pBoxEnd->right());
    pExtents->setBottom(pBoxEnd->bottom());

    Q_ASSERT(pExtents->top() <= pExtents->bottom());
    while (pBox <= pBoxEnd) {
        if (pBox->left() < pExtents->left())
            pExtents->setLeft(pBox->left());
        if (pBox->right() > pExtents->right())
            pExtents->setRight(pBox->right());
#ifdef QT_EXPERIMENTAL_REGIONS
        dest.updateInnerRect(*pBox);
#endif
        ++pBox;
    }
    Q_ASSERT(pExtents->left() <= pExtents->right());
}

Here is the call graph for this function:

static void miSubtractNonO1	(	register QRegionPrivate &	dest,
		register const QRect *	r,
		const QRect *	rEnd,
		register int	y1,
		register int	y2
	)			[static]

Definition at line 1137 of file qregion_unix.cpp.

References MEMCHECK, and QRect::setCoords().

Referenced by SubtractRegion().

{
    register QRect *pNextRect;

    pNextRect = dest.rects.data() + dest.numRects;

    Q_ASSERT(y1<=y2);

    while (r != rEnd) {
        Q_ASSERT(r->left() <= r->right());
        MEMCHECK(dest, pNextRect, dest.rects)
        pNextRect->setCoords(r->left(), y1, r->right(), y2);
        ++dest.numRects;
        ++pNextRect;
        ++r;
    }
}

Here is the call graph for this function:

static void miSubtractO	(	register QRegionPrivate &	dest,
		register const QRect *	r1,
		const QRect *	r1End,
		register const QRect *	r2,
		const QRect *	r2End,
		register int	y1,
		register int	y2
	)			[static]

Definition at line 1171 of file qregion_unix.cpp.

References QTextStream::left(), QRect::left(), MEMCHECK, QTextStream::right(), QRect::right(), and QRect::setCoords().

Referenced by SubtractRegion().

{
    register QRect *pNextRect;
    register int x1;

    x1 = r1->left();

    Q_ASSERT(y1 <= y2);
    pNextRect = dest.rects.data() + dest.numRects;

    while (r1 != r1End && r2 != r2End) {
        if (r2->right() < x1) {
            /*
             * Subtrahend missed the boat: go to next subtrahend.
             */
            ++r2;
        } else if (r2->left() <= x1) {
            /*
             * Subtrahend precedes minuend: nuke left edge of minuend.
             */
            x1 = r2->right() + 1;
            if (x1 > r1->right()) {
                /*
                 * Minuend completely covered: advance to next minuend and
                 * reset left fence to edge of new minuend.
                 */
                ++r1;
                if (r1 != r1End)
                    x1 = r1->left();
            } else {
                // Subtrahend now used up since it doesn't extend beyond minuend
                ++r2;
            }
        } else if (r2->left() <= r1->right()) {
            /*
             * Left part of subtrahend covers part of minuend: add uncovered
             * part of minuend to region and skip to next subtrahend.
             */
            Q_ASSERT(x1 < r2->left());
            MEMCHECK(dest, pNextRect, dest.rects)
            pNextRect->setCoords(x1, y1, r2->left() - 1, y2);
            ++dest.numRects;
            ++pNextRect;

            x1 = r2->right() + 1;
            if (x1 > r1->right()) {
                /*
                 * Minuend used up: advance to new...
                 */
                ++r1;
                if (r1 != r1End)
                    x1 = r1->left();
            } else {
                // Subtrahend used up
                ++r2;
            }
        } else {
            /*
             * Minuend used up: add any remaining piece before advancing.
             */
            if (r1->right() >= x1) {
                MEMCHECK(dest, pNextRect, dest.rects)
                pNextRect->setCoords(x1, y1, r1->right(), y2);
                ++dest.numRects;
                ++pNextRect;
            }
            ++r1;
            if (r1 != r1End)
                x1 = r1->left();
        }
    }

    /*
     * Add remaining minuend rectangles to region.
     */
    while (r1 != r1End) {
        Q_ASSERT(x1 <= r1->right());
        MEMCHECK(dest, pNextRect, dest.rects)
        pNextRect->setCoords(x1, y1, r1->right(), y2);
        ++dest.numRects;
        ++pNextRect;

        ++r1;
        if (r1 != r1End)
            x1 = r1->left();
    }
}

Here is the call graph for this function:

static void miUnionNonO	(	register QRegionPrivate &	dest,
		register const QRect *	r,
		const QRect *	rEnd,
		register int	y1,
		register int	y2
	)			[static]

Definition at line 907 of file qregion_unix.cpp.

References MEMCHECK, and QRect::setCoords().

Referenced by UnionRegion().

{
    register QRect *pNextRect;

    pNextRect = dest.rects.data() + dest.numRects;

    Q_ASSERT(y1 <= y2);

    while (r != rEnd) {
        Q_ASSERT(r->left() <= r->right());
        MEMCHECK(dest, pNextRect, dest.rects)
        pNextRect->setCoords(r->left(), y1, r->right(), y2);
        dest.numRects++;
        ++pNextRect;
        ++r;
    }
}

Here is the call graph for this function:

static void miUnionO	(	register QRegionPrivate &	dest,
		register const QRect *	r1,
		const QRect *	r1End,
		register const QRect *	r2,
		const QRect *	r2End,
		register int	y1,
		register int	y2
	)			[static]

Definition at line 943 of file qregion_unix.cpp.

References MERGERECT.

Referenced by UnionRegion().

{
    register QRect *pNextRect;

    pNextRect = dest.rects.data() + dest.numRects;

#ifndef QT_EXPERIMENTAL_REGIONS
#define MERGERECT(r)             \
    if ((dest.numRects != 0) &&  \
        (pNextRect[-1].top() == y1) &&  \
        (pNextRect[-1].bottom() == y2) &&  \
        (pNextRect[-1].right() >= r->left()-1)) { \
        if (pNextRect[-1].right() < r->right()) { \
            pNextRect[-1].setRight(r->right());  \
            Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
        }  \
    } else { \
        MEMCHECK(dest, pNextRect, dest.rects)  \
        pNextRect->setCoords(r->left(), y1, r->right(), y2); \
        dest.numRects++;  \
        pNextRect++;  \
    }  \
    r++;
#else
#define MERGERECT(r)             \
    if ((dest.numRects != 0) &&  \
        (pNextRect[-1].top() == y1) &&  \
        (pNextRect[-1].bottom() == y2) &&  \
        (pNextRect[-1].right() >= r->left()-1)) { \
        if (pNextRect[-1].right() < r->right()) { \
            pNextRect[-1].setRight(r->right());  \
            dest.updateInnerRect(pNextRect[-1]); \
            Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
        }  \
    } else { \
        MEMCHECK(dest, pNextRect, dest.rects)  \
        pNextRect->setCoords(r->left(), y1, r->right(), y2); \
        dest.updateInnerRect(*pNextRect); \
        dest.numRects++;  \
        pNextRect++;  \
    }  \
    r++;
#endif

    Q_ASSERT(y1 <= y2);
    while (r1 != r1End && r2 != r2End) {
        if (r1->left() < r2->left()) {
            MERGERECT(r1)
        } else {
            MERGERECT(r2)
        }
    }

    if (r1 != r1End) {
        do {
            MERGERECT(r1)
        } while (r1 != r1End);
    } else {
        while (r2 != r2End) {
            MERGERECT(r2)
        }
    }
}

static void OffsetRegion	(	register QRegionPrivate &	region,
		register int	x,
		register int	y
	)			[static]

Definition at line 465 of file qregion_unix.cpp.

References QRect::translate().

{
    register int nbox;
    register QRect *pbox;

    pbox = region.rects.data();
    nbox = region.numRects;

    while (nbox--) {
        pbox->translate(x, y);
        ++pbox;
    }
    region.extents.translate(x, y);
#ifdef QT_EXPERIMENTAL_REGIONS
    region.innerRect.translate(x, y);
#endif
}

Here is the call graph for this function:

static bool PointInRegion	(	QRegionPrivate *	pRegion,
		int	x,
		int	y
	)			[static]

Definition at line 1340 of file qregion_unix.cpp.

References QRect::contains(), QVector< T >::contains(), QRegionPrivate::extents, i, isEmpty(), QRegionPrivate::numRects, and QRegionPrivate::rects.

{
    int i;

    if (isEmpty(pRegion))
        return false;
    if (!pRegion->extents.contains(x, y))
        return false;
#ifdef QT_EXPERIMENTAL_REGIONS
    if (pRegion->innerRect.contains(x, y))
        return true;
#endif
    for (i = 0; i < pRegion->numRects; ++i) {
        if (pRegion->rects[i].contains(x, y))
            return true;
    }
    return false;
}

Here is the call graph for this function:

static QRegionPrivate* PolygonRegion	(	const QPoint *	Pts,
		int	Count,
		int	rule
	)			[static]

Definition at line 2148 of file qregion_unix.cpp.

References QRect::bottom(), _EdgeTableEntry::bres, computeWAET(), CreateETandAET(), _ScanLineList::edgelist, EVALUATEEDGEEVENODD, EVALUATEEDGEWINDING, EvenOddRule, QRegionPrivate::extents, FreeStorage(), InsertionSort(), QRect::left(), loadAET(), BRESINFO::minor_axis, _ScanLineListBlock::next, _ScanLineList::next, _EdgeTableEntry::next, _POINTBLOCK::next, _EdgeTableEntry::nextWETE, NUMPTSTOBUFFER, QRegionPrivate::numRects, _POINTBLOCK::pts, PtsToRegion(), qMax(), qMin(), QRegionPrivate::rects, QVector< T >::resize(), QRect::right(), _ScanLineList::scanline, EdgeTable::scanlines, QRect::setHeight(), QRect::setLeft(), QRect::setTop(), QRect::setWidth(), QPoint::setX(), QPoint::setY(), QRect::top(), x, y, EdgeTable::ymax, and EdgeTable::ymin.

{
    QRegionPrivate *region;
    register EdgeTableEntry *pAET;   /* Active Edge Table       */
    register int y;                  /* current scanline        */
    register int iPts = 0;           /* number of pts in buffer */
    register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
    register ScanLineList *pSLL;     /* current scanLineList    */
    register QPoint *pts;             /* output buffer           */
    EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
    EdgeTable ET;                    /* header node for ET      */
    EdgeTableEntry AET;              /* header node for AET     */
    EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
    ScanLineListBlock SLLBlock;      /* header for scanlinelist */
    int fixWAET = false;
    POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
    POINTBLOCK *tmpPtBlock;
    int numFullPtBlocks = 0;

    if (!(region = new QRegionPrivate))
        return 0;

    /* special case a rectangle */
    if (((Count == 4) ||
         ((Count == 5) && (Pts[4].x() == Pts[0].x()) && (Pts[4].y() == Pts[0].y())))
         && (((Pts[0].y() == Pts[1].y()) && (Pts[1].x() == Pts[2].x()) && (Pts[2].y() == Pts[3].y())
               && (Pts[3].x() == Pts[0].x())) || ((Pts[0].x() == Pts[1].x())
               && (Pts[1].y() == Pts[2].y()) && (Pts[2].x() == Pts[3].x())
               && (Pts[3].y() == Pts[0].y())))) {
        int x = qMin(Pts[0].x(), Pts[2].x());
        region->extents.setLeft(x);
        int y = qMin(Pts[0].y(), Pts[2].y());
        region->extents.setTop(y);
        region->extents.setWidth(qMax(Pts[0].x(), Pts[2].x()) - x);
        region->extents.setHeight(qMax(Pts[0].y(), Pts[2].y()) - y);
        if ((region->extents.left() <= region->extents.right()) &&
            (region->extents.top() <= region->extents.bottom())) {
            region->numRects = 1;
            region->rects.resize(1);
            region->rects[0] = region->extents;
#ifdef QT_EXPERIMENTAL_REGIONS
            region->innerRect = region->extents;
            region->innerArea = region->innerRect.width() * region->innerRect.height();
#endif
        }
        return region;
    }

    if (!(pETEs = static_cast<EdgeTableEntry *>(malloc(sizeof(EdgeTableEntry) * Count))))
        return 0;

    pts = FirstPtBlock.pts;
    CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
    pSLL = ET.scanlines.next;
    curPtBlock = &FirstPtBlock;

    if (rule == EvenOddRule) {
        /*
         *  for each scanline
         */
        for (y = ET.ymin; y < ET.ymax; ++y) {
            /*
             *  Add a new edge to the active edge table when we
             *  get to the next edge.
             */
            if (pSLL && y == pSLL->scanline) {
                loadAET(&AET, pSLL->edgelist);
                pSLL = pSLL->next;
            }
            pPrevAET = &AET;
            pAET = AET.next;

            /*
             *  for each active edge
             */
            while (pAET) {
                pts->setX(pAET->bres.minor_axis);
                pts->setY(y);
                ++pts;
                ++iPts;

                /*
                 *  send out the buffer
                 */
                if (iPts == NUMPTSTOBUFFER) {
                    tmpPtBlock = (POINTBLOCK *)malloc(sizeof(POINTBLOCK));
                    curPtBlock->next = tmpPtBlock;
                    curPtBlock = tmpPtBlock;
                    pts = curPtBlock->pts;
                    ++numFullPtBlocks;
                    iPts = 0;
                }
                EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
            }
            InsertionSort(&AET);
        }
    } else {
        /*
         *  for each scanline
         */
        for (y = ET.ymin; y < ET.ymax; ++y) {
            /*
             *  Add a new edge to the active edge table when we
             *  get to the next edge.
             */
            if (pSLL && y == pSLL->scanline) {
                loadAET(&AET, pSLL->edgelist);
                computeWAET(&AET);
                pSLL = pSLL->next;
            }
            pPrevAET = &AET;
            pAET = AET.next;
            pWETE = pAET;

            /*
             *  for each active edge
             */
            while (pAET) {
                /*
                 *  add to the buffer only those edges that
                 *  are in the Winding active edge table.
                 */
                if (pWETE == pAET) {
                    pts->setX(pAET->bres.minor_axis);
                    pts->setY(y);
                    ++pts;
                    ++iPts;

                    /*
                     *  send out the buffer
                     */
                    if (iPts == NUMPTSTOBUFFER) {
                        tmpPtBlock = static_cast<POINTBLOCK *>(malloc(sizeof(POINTBLOCK)));
                        curPtBlock->next = tmpPtBlock;
                        curPtBlock = tmpPtBlock;
                        pts = curPtBlock->pts;
                        ++numFullPtBlocks;
                        iPts = 0;
                    }
                    pWETE = pWETE->nextWETE;
                }
                EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
            }

            /*
             *  recompute the winding active edge table if
             *  we just resorted or have exited an edge.
             */
            if (InsertionSort(&AET) || fixWAET) {
                computeWAET(&AET);
                fixWAET = false;
            }
        }
    }
    FreeStorage(SLLBlock.next);
    PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
    for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
        tmpPtBlock = curPtBlock->next;
        free(curPtBlock);
        curPtBlock = tmpPtBlock;
    }

Here is the call graph for this function:

static void PtsToRegion	(	register int	numFullPtBlocks,
		register int	iCurPtBlock,
		POINTBLOCK *	FirstPtBlock,
		QRegionPrivate *	reg
	)			[static]

Definition at line 2075 of file qregion_unix.cpp.

References QRect::bottom(), QVector< T >::data(), QRegionPrivate::extents, i, QRect::left(), _POINTBLOCK::next, NUMPTSTOBUFFER, _POINTBLOCK::pts, QRegionPrivate::rects, QVector< T >::resize(), QRect::right(), QRect::setBottom(), QRect::setCoords(), QRect::setLeft(), QRect::setRight(), QRect::top(), QPoint::x(), QPoint::y(), and y.

Referenced by PolygonRegion().

{
    register QRect *rects;
    register QPoint *pts;
    register POINTBLOCK *CurPtBlock;
    register int i;
    register QRect *extents;
    register int numRects;

    extents = &reg->extents;
    numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;

    reg->rects.resize(numRects);

    CurPtBlock = FirstPtBlock;
    rects = reg->rects.data() - 1;
    numRects = 0;
    extents->setLeft(INT_MAX);
    extents->setRight(INT_MIN);
#ifdef QT_EXPERIMENTAL_REGIONS
    reg->innerArea = -1;
#endif

    for (; numFullPtBlocks >= 0; --numFullPtBlocks) {
        /* the loop uses 2 points per iteration */
        i = NUMPTSTOBUFFER >> 1;
        if (!numFullPtBlocks)
            i = iCurPtBlock >> 1;
        if(i) {
            for (pts = CurPtBlock->pts; i--; pts += 2) {
                if (pts->x() == pts[1].x())
                    continue;
                if (numRects && pts->x() == rects->left() && pts->y() == rects->bottom() + 1
                    && pts[1].x() == rects->right()+1 && (numRects == 1 || rects[-1].top() != rects->top())
                                                          && (i && pts[2].y() > pts[1].y())) {
                        rects->setBottom(pts[1].y());
#ifdef QT_EXPERIMENTAL_REGIONS
                        reg->updateInnerRect(*rects);
#endif
                        continue;
                }
                ++numRects;
                ++rects;
                rects->setCoords(pts->x(), pts->y(), pts[1].x() - 1, pts[1].y());
                if (rects->left() < extents->left())
                    extents->setLeft(rects->left());
                if (rects->right() > extents->right())
                    extents->setRight(rects->right());
#ifdef QT_EXPERIMENTAL_REGIONS
                reg->updateInnerRect(*rects);
#endif
            }
        }
        CurPtBlock = CurPtBlock->next;
    }

    if (numRects) {
        extents->setTop(reg->rects[0].top());
        extents->setBottom(rects->bottom());
    } else {
        extents->setCoords(0, 0, 0, 0);

Here is the call graph for this function:

QRegionPrivate* qt_bitmapToRegion

(

const QBitmap &

bitmap

)

Definition at line 2317 of file qregion_unix.cpp.

{
    QImage image = bitmap.toImage();

    QRegionPrivate *region = new QRegionPrivate;
    QRect xr;

#define AddSpan \
        { \
            xr.setCoords(prev1, y, x-1, y); \
            UnionRectWithRegion(&xr, region, *region); \
        }

    const uchar zero = 0;
    bool little = image.format() == QImage::Format_MonoLSB;

    int x,
        y;
    for (y = 0; y < image.height(); ++y) {
        uchar *line = image.scanLine(y);
        int w = image.width();
        uchar all = zero;
        int prev1 = -1;
        for (x = 0; x < w;) {
            uchar byte = line[x / 8];
            if (x > w - 8 || byte!=all) {
                if (little) {
                    for (int b = 8; b > 0 && x < w; --b) {
                        if (!(byte & 0x01) == !all) {
                            // More of the same
                        } else {
                            // A change.
                            if (all!=zero) {
                                AddSpan
                                all = zero;
                            } else {
                                prev1 = x;
                                all = ~zero;
                            }
                        }
                        byte >>= 1;
                        ++x;
                    }
                } else {
                    for (int b = 8; b > 0 && x < w; --b) {
                        if (!(byte & 0x80) == !all) {
                            // More of the same
                        } else {
                            // A change.
                            if (all != zero) {
                                AddSpan
                                all = zero;
                            } else {
                                prev1 = x;
                                all = ~zero;
                            }
                        }
                        byte <<= 1;
                        ++x;
                    }
                }
            } else {
                x += 8;
            }
        }
        if (all != zero) {
            AddSpan
        }
    }
#undef AddSpan

static bool RectInRegion	(	register QRegionPrivate *	region,
		int	rx,
		int	ry,
		uint	rwidth,
		uint	rheight
	)			[static]

Definition at line 1359 of file qregion_unix.cpp.

References QRect::bottom(), EXTENTCHECK, QRect::left(), RectangleIn, RectangleOut, RectanglePart, QRect::right(), and QRect::top().

{
    register const QRect *pbox;
    register const QRect *pboxEnd;
    QRect rect(rx, ry, rwidth, rheight);
    register QRect *prect = ▭
    int partIn, partOut;

    if (!region || region->numRects == 0 || !EXTENTCHECK(&region->extents, prect))
        return RectangleOut;

    partOut = false;
    partIn = false;

    /* can stop when both partOut and partIn are true, or we reach prect->y2 */
    for (pbox = region->rects.constData(), pboxEnd = pbox + region->numRects;
         pbox < pboxEnd; ++pbox) {
        if (pbox->bottom() < ry)
           continue;

        if (pbox->top() > ry) {
           partOut = true;
           if (partIn || pbox->top() > prect->bottom())
              break;
           ry = pbox->top();
        }

        if (pbox->right() < rx)
           continue;            /* not far enough over yet */

        if (pbox->left() > rx) {
           partOut = true;      /* missed part of rectangle to left */
           if (partIn)
              break;
        }

        if (pbox->left() <= prect->right()) {
            partIn = true;      /* definitely overlap */
            if (partOut)
               break;
        }

        if (pbox->right() >= prect->right()) {
           ry = pbox->bottom() + 1;     /* finished with this band */
           if (ry > prect->bottom())
              break;
           rx = prect->left();  /* reset x out to left again */
        } else {
            /*
             * Because boxes in a band are maximal width, if the first box
             * to overlap the rectangle doesn't completely cover it in that
             * band, the rectangle must be partially out, since some of it
             * will be uncovered in that band. partIn will have been set true
             * by now...
             */
            break;
        }
    }
    return partIn ? ((ry <= prect->bottom()) ? RectanglePart : RectangleIn) : RectangleOut;
}

Here is the call graph for this function:

static void SubtractRegion	(	QRegionPrivate *	regM,
		QRegionPrivate *	regS,
		register QRegionPrivate &	dest
	)			[static]

Definition at line 1272 of file qregion_unix.cpp.

References EqualRegion(), EXTENTCHECK, QRegionPrivate::extents, isEmpty(), miRegionOp(), miSetExtents(), miSubtractNonO1(), and miSubtractO().

Referenced by XorRegion().

{
   /* check for trivial reject */
    if (isEmpty(regM))
        return;

    if (isEmpty(regS) || !EXTENTCHECK(&regM->extents, &regS->extents)) {
        dest = *regM;
        return;
    }

#ifdef QT_EXPERIMENTAL_REGIONS
    if (regS->contains(*regM)) {
        dest = QRegionPrivate();
        return;
    }

    if (EqualRegion(regM, regS)) {
        dest = QRegionPrivate();
        return;
    }
#endif

    miRegionOp(dest, regM, regS, miSubtractO, miSubtractNonO1, 0);

    /*
     * Can't alter dest's extents before we call miRegionOp because
     * it might be one of the source regions and miRegionOp depends
     * on the extents of those regions being the unaltered. Besides, this
     * way there's no checking against rectangles that will be nuked
     * due to coalescing, so we have to examine fewer rectangles.
     */
    miSetExtents(dest);
}

Here is the call graph for this function:

static void UnionRectWithRegion	(	register const QRect *	rect,
		const QRegionPrivate *	source,
		QRegionPrivate &	dest
	)			[static]

Definition at line 380 of file qregion_unix.cpp.

References QRegionPrivate::extents, QRegionPrivate::numRects, QRegionPrivate::rects, QVector< T >::resize(), and UnionRegion().

{
    if (!rect->width() || !rect->height())
        return;

    QRegionPrivate region;
    region.rects.resize(1);
    region.numRects = 1;
    region.rects[0] = *rect;
    region.extents = *rect;
#ifdef QT_EXPERIMENTAL_REGIONS
    region.innerRect = *rect;
    region.innerArea = rect->width() * rect->height();
#endif

    UnionRegion(&region, source, dest);
    return;
}

Here is the call graph for this function:

static void UnionRegion	(	const QRegionPrivate *	reg1,
		const QRegionPrivate *	reg2,
		QRegionPrivate &	dest
	)			[static]

Definition at line 1008 of file qregion_unix.cpp.

References QRect::bottom(), EqualRegion(), QRegionPrivate::extents, isEmpty(), QRect::left(), miRegionOp(), miUnionNonO(), miUnionO(), QRegionPrivate::numRects, qMax(), qMin(), QRect::right(), QRect::setCoords(), and QRect::top().

Referenced by UnionRectWithRegion(), and XorRegion().

{
#ifdef QT_EXPERIMENTAL_REGIONS
    /*
      Empty region
    */
    if (isEmpty(reg1)) {
        dest = *reg2;
        return;
    }
    if (isEmpty(reg2)) {
        dest = *reg1;
        return;
    }

    /*
      A region completely subsumes the other
    */
    if (reg1->contains(*reg2)) {
        dest = *reg1;
        return;
    }
    if (reg2->contains(*reg1)) {
        dest = *reg2;
        return;
    }

    /*
      Regions are equal.
    */
    if (EqualRegion(reg1, reg2)) {
        dest = *reg1;
        return;
    }

    /*
      Can append reg2 to reg1
    */
    if (reg1->canAppend(reg2)) {
        dest = *reg1;
        dest.append(reg2);
        return;
    }

    /*
      Can append reg1 to reg2
    */
    if (reg2->canAppend(reg1)) {
        dest = *reg2;
        dest.append(reg1);
        return;
    }
#else
    /*
      Region 1 is empty or is equal to region 2.
    */
    if (reg1 == reg2 || isEmpty(reg1)) {
        if (!isEmpty(reg2))
            dest = *reg2;
        return;
    }

    /*
      Region 2 is empty (and region 1 isn't).
    */
    if (isEmpty(reg2)) {
        dest = *reg1;
        return;
    }

    /*
      Region 1 completely subsumes region 2.
     */
    if (reg1->numRects == 1 && reg1->extents.left() <= reg2->extents.left()
            && reg1->extents.top() <= reg2->extents.top()
            && reg1->extents.right() >= reg2->extents.right()
            && reg1->extents.bottom() >= reg2->extents.bottom()) {
        dest = *reg1;
        return;
    }

    /*
      Region 2 completely subsumes region 1.
     */
    if (reg2->numRects == 1 && reg2->extents.left() <= reg1->extents.left()
            && reg2->extents.top() <= reg1->extents.top()
            && reg2->extents.right() >= reg1->extents.right()
            && reg2->extents.bottom() >= reg1->extents.bottom()) {
        dest = *reg2;
        return;
    }
#endif

#ifdef QT_EXPERIMENTAL_REGIONS
    if (reg1->innerArea > reg2->innerArea) {
        dest.innerArea = reg1->innerArea;
        dest.innerRect = reg1->innerRect;
    } else {
        dest.innerArea = reg2->innerArea;
        dest.innerRect = reg2->innerRect;
    }
#endif
    miRegionOp(dest, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);

    dest.extents.setCoords(qMin(reg1->extents.left(), reg2->extents.left()),
                           qMin(reg1->extents.top(), reg2->extents.top()),
                           qMax(reg1->extents.right(), reg2->extents.right()),
                           qMax(reg1->extents.bottom(), reg2->extents.bottom()));
}

Here is the call graph for this function:

static void XorRegion	(	QRegionPrivate *	sra,
		QRegionPrivate *	srb,
		QRegionPrivate &	dest
	)			[static]

Definition at line 1308 of file qregion_unix.cpp.

References SubtractRegion(), and UnionRegion().

{
    QRegionPrivate tra, trb;

    SubtractRegion(sra, srb, tra);
    SubtractRegion(srb, sra, trb);
    UnionRegion(&tra, &trb, dest);
}

Here is the call graph for this function:

---