Qt 4.8
qregion.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtGui module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 
42 #include "qregion.h"
43 #include "qpainterpath.h"
44 #include "qpolygon.h"
45 #include "qbuffer.h"
46 #include "qdatastream.h"
47 #include "qvariant.h"
48 #include "qvarlengtharray.h"
49 
50 #include <qdebug.h>
51 
52 #if defined(Q_OS_UNIX) || defined(Q_WS_WIN)
53 #include "qimage.h"
54 #include "qbitmap.h"
55 #include <stdlib.h>
56 #endif
57 
59 
193 /*****************************************************************************
194  QRegion member functions
195  *****************************************************************************/
196 
272 QRegion::QRegion(int x, int y, int w, int h, RegionType t)
273 {
274  QRegion tmp(QRect(x, y, w, h), t);
275  tmp.d->ref.ref();
276  d = tmp.d;
277 }
278 
279 #ifdef QT3_SUPPORT
280 
284 QRegion::QRegion(const QPolygon &pa, bool winding)
285 {
286  new (this) QRegion(pa, winding ? Qt::WindingFill : Qt::OddEvenFill);
287 }
288 #endif
289 
301 {
302  if (d->ref != 1)
303  *this = copy();
304 #if defined(Q_WS_X11)
305  else if (d->xrectangles) {
306  free(d->xrectangles);
307  d->xrectangles = 0;
308  }
309 #endif
310 }
311 
312 // duplicates in qregion_win.cpp and qregion_wce.cpp
313 #define QRGN_SETRECT 1 // region stream commands
314 #define QRGN_SETELLIPSE 2 // (these are internal)
315 #define QRGN_SETPTARRAY_ALT 3
316 #define QRGN_SETPTARRAY_WIND 4
317 #define QRGN_TRANSLATE 5
318 #define QRGN_OR 6
319 #define QRGN_AND 7
320 #define QRGN_SUB 8
321 #define QRGN_XOR 9
322 #define QRGN_RECTS 10
323 
324 
325 #ifndef QT_NO_DATASTREAM
326 
327 /*
328  Executes region commands in the internal buffer and rebuilds the
329  original region.
330 
331  We do this when we read a region from the data stream.
332 
333  If \a ver is non-0, uses the format version \a ver on reading the
334  byte array.
335 */
336 void QRegion::exec(const QByteArray &buffer, int ver, QDataStream::ByteOrder byteOrder)
337 {
338  QByteArray copy = buffer;
340  if (ver)
341  s.setVersion(ver);
342  s.setByteOrder(byteOrder);
343  QRegion rgn;
344 #ifndef QT_NO_DEBUG
345  int test_cnt = 0;
346 #endif
347  while (!s.atEnd()) {
348  qint32 id;
349  if (s.version() == 1) {
350  int id_int;
351  s >> id_int;
352  id = id_int;
353  } else {
354  s >> id;
355  }
356 #ifndef QT_NO_DEBUG
357  if (test_cnt > 0 && id != QRGN_TRANSLATE)
358  qWarning("QRegion::exec: Internal error");
359  test_cnt++;
360 #endif
361  if (id == QRGN_SETRECT || id == QRGN_SETELLIPSE) {
362  QRect r;
363  s >> r;
364  rgn = QRegion(r, id == QRGN_SETRECT ? Rectangle : Ellipse);
365  } else if (id == QRGN_SETPTARRAY_ALT || id == QRGN_SETPTARRAY_WIND) {
366  QPolygon a;
367  s >> a;
369  } else if (id == QRGN_TRANSLATE) {
370  QPoint p;
371  s >> p;
372  rgn.translate(p.x(), p.y());
373  } else if (id >= QRGN_OR && id <= QRGN_XOR) {
374  QByteArray bop1, bop2;
375  QRegion r1, r2;
376  s >> bop1;
377  r1.exec(bop1);
378  s >> bop2;
379  r2.exec(bop2);
380 
381  switch (id) {
382  case QRGN_OR:
383  rgn = r1.united(r2);
384  break;
385  case QRGN_AND:
386  rgn = r1.intersected(r2);
387  break;
388  case QRGN_SUB:
389  rgn = r1.subtracted(r2);
390  break;
391  case QRGN_XOR:
392  rgn = r1.xored(r2);
393  break;
394  }
395  } else if (id == QRGN_RECTS) {
396  // (This is the only form used in Qt 2.0)
397  quint32 n;
398  s >> n;
399  QRect r;
400  for (int i=0; i<(int)n; i++) {
401  s >> r;
402  rgn = rgn.united(QRegion(r));
403  }
404  }
405  }
406  *this = rgn;
407 }
408 
409 
410 /*****************************************************************************
411  QRegion stream functions
412  *****************************************************************************/
413 
447 {
448  QVector<QRect> a = r.rects();
449  if (a.isEmpty()) {
450  s << (quint32)0;
451  } else {
452  if (s.version() == 1) {
453  int i;
454  for (i = a.size() - 1; i > 0; --i) {
455  s << (quint32)(12 + i * 24);
456  s << (int)QRGN_OR;
457  }
458  for (i = 0; i < a.size(); ++i) {
459  s << (quint32)(4+8) << (int)QRGN_SETRECT << a[i];
460  }
461  } else {
462  s << (quint32)(4 + 4 + 16 * a.size()); // 16: storage size of QRect
463  s << (qint32)QRGN_RECTS;
464  s << a;
465  }
466  }
467  return s;
468 }
469 
483 {
484  QByteArray b;
485  s >> b;
486  r.exec(b, s.version(), s.byteOrder());
487  return s;
488 }
489 #endif //QT_NO_DATASTREAM
490 
491 #ifndef QT_NO_DEBUG_STREAM
493 {
494  QVector<QRect> rects = r.rects();
495  s.nospace() << "QRegion(size=" << rects.size() << "), "
496  << "bounds = " << r.boundingRect() << '\n';
497  for (int i=0; i<rects.size(); ++i)
498  s << "- " << i << rects.at(i) << '\n';
499  return s;
500 }
501 #endif
502 
503 
504 // These are not inline - they can be implemented better on some platforms
505 // (eg. Windows at least provides 3-variable operations). For now, simple.
506 
507 
514 const QRegion QRegion::operator|(const QRegion &r) const
515  { return united(r); }
516 
523 const QRegion QRegion::operator+(const QRegion &r) const
524  { return united(r); }
525 
530 const QRegion QRegion::operator+(const QRect &r) const
531  { return united(r); }
532 
539 const QRegion QRegion::operator&(const QRegion &r) const
540  { return intersected(r); }
541 
546 const QRegion QRegion::operator&(const QRect &r) const
547 {
548  return intersected(r);
549 }
550 
557 const QRegion QRegion::operator-(const QRegion &r) const
558  { return subtracted(r); }
559 
566 const QRegion QRegion::operator^(const QRegion &r) const
567  { return xored(r); }
568 
577  { return *this = *this | r; }
578 
601 #if !defined (Q_OS_UNIX) && !defined (Q_WS_WIN)
603 {
604  return operator+=(QRegion(r));
605 }
606 #endif
607 
621  { return *this = *this & r; }
622 
627 #if defined (Q_OS_UNIX) || defined (Q_WS_WIN)
629 {
630  return *this = *this & r;
631 }
632 #else
634 {
635  return *this &= (QRegion(r));
636 }
637 #endif
638 
652  { return *this = *this - r; }
653 
662  { return *this = *this ^ r; }
663 
677 QRegion::operator QVariant() const
678 {
679  return QVariant(QVariant::Region, this);
680 }
681 
742 QRegion
743 QRegion::translated(int dx, int dy) const
744 {
745  QRegion ret(*this);
746  ret.translate(dx, dy);
747  return ret;
748 }
749 
750 
751 inline bool rect_intersects(const QRect &r1, const QRect &r2)
752 {
753  return (r1.right() >= r2.left() && r1.left() <= r2.right() &&
754  r1.bottom() >= r2.top() && r1.top() <= r2.bottom());
755 }
756 
766 bool QRegion::intersects(const QRegion &region) const
767 {
768  if (isEmpty() || region.isEmpty())
769  return false;
770 
771  if (!rect_intersects(boundingRect(), region.boundingRect()))
772  return false;
773  if (rectCount() == 1 && region.rectCount() == 1)
774  return true;
775 
776  const QVector<QRect> myRects = rects();
777  const QVector<QRect> otherRects = region.rects();
778 
779  for (QVector<QRect>::const_iterator i1 = myRects.constBegin(); i1 < myRects.constEnd(); ++i1)
780  for (QVector<QRect>::const_iterator i2 = otherRects.constBegin(); i2 < otherRects.constEnd(); ++i2)
781  if (rect_intersects(*i1, *i2))
782  return true;
783  return false;
784 }
785 
798 #if !defined (Q_OS_UNIX) && !defined (Q_WS_WIN)
799 
803 QRegion QRegion::intersect(const QRect &r) const
804 {
805  return intersect(QRegion(r));
806 }
807 #endif
808 
1058 namespace {
1059 
1060 struct Segment
1061 {
1062  Segment() {}
1063  Segment(const QPoint &p)
1064  : added(false)
1065  , point(p)
1066  {
1067  }
1068 
1069  int left() const
1070  {
1071  return qMin(point.x(), next->point.x());
1072  }
1073 
1074  int right() const
1075  {
1076  return qMax(point.x(), next->point.x());
1077  }
1078 
1079  bool overlaps(const Segment &other) const
1080  {
1081  return left() < other.right() && other.left() < right();
1082  }
1083 
1084  void connect(Segment &other)
1085  {
1086  next = &other;
1087  other.prev = this;
1088 
1089  horizontal = (point.y() == other.point.y());
1090  }
1091 
1092  void merge(Segment &other)
1093  {
1094  if (right() <= other.right()) {
1095  QPoint p = other.point;
1096  Segment *oprev = other.prev;
1097 
1098  other.point = point;
1099  other.prev = prev;
1100  prev->next = &other;
1101 
1102  point = p;
1103  prev = oprev;
1104  oprev->next = this;
1105  } else {
1106  Segment *onext = other.next;
1107  other.next = next;
1108  next->prev = &other;
1109 
1110  next = onext;
1111  next->prev = this;
1112  }
1113  }
1114 
1115  int horizontal : 1;
1116  int added : 1;
1117 
1118  QPoint point;
1119  Segment *prev;
1120  Segment *next;
1121 };
1122 
1123 void mergeSegments(Segment *a, int na, Segment *b, int nb)
1124 {
1125  int i = 0;
1126  int j = 0;
1127 
1128  while (i != na && j != nb) {
1129  Segment &sa = a[i];
1130  Segment &sb = b[j];
1131  const int ra = sa.right();
1132  const int rb = sb.right();
1133  if (sa.overlaps(sb))
1134  sa.merge(sb);
1135  i += (rb >= ra);
1136  j += (ra >= rb);
1137  }
1138 }
1139 
1140 void addSegmentsToPath(Segment *segment, QPainterPath &path)
1141 {
1142  Segment *current = segment;
1143  path.moveTo(current->point);
1144 
1145  current->added = true;
1146 
1147  Segment *last = current;
1148  current = current->next;
1149  while (current != segment) {
1150  if (current->horizontal != last->horizontal)
1151  path.lineTo(current->point);
1152  current->added = true;
1153  last = current;
1154  current = current->next;
1155  }
1156 }
1157 
1158 }
1159 
1161 {
1162  QPainterPath result;
1163  if (region.rectCount() == 1) {
1164  result.addRect(region.boundingRect());
1165  return result;
1166  }
1167 
1168  const QVector<QRect> rects = region.rects();
1169 
1170  QVarLengthArray<Segment> segments;
1171  segments.resize(4 * rects.size());
1172 
1173  const QRect *rect = rects.constData();
1174  const QRect *end = rect + rects.size();
1175 
1176  int lastRowSegmentCount = 0;
1177  Segment *lastRowSegments = 0;
1178 
1179  int lastSegment = 0;
1180  int lastY = 0;
1181  while (rect != end) {
1182  const int y = rect[0].y();
1183  int count = 0;
1184  while (&rect[count] != end && rect[count].y() == y)
1185  ++count;
1186 
1187  for (int i = 0; i < count; ++i) {
1188  int offset = lastSegment + i;
1189  segments[offset] = Segment(rect[i].topLeft());
1190  segments[offset += count] = Segment(rect[i].topRight() + QPoint(1, 0));
1191  segments[offset += count] = Segment(rect[i].bottomRight() + QPoint(1, 1));
1192  segments[offset += count] = Segment(rect[i].bottomLeft() + QPoint(0, 1));
1193 
1194  offset = lastSegment + i;
1195  for (int j = 0; j < 4; ++j)
1196  segments[offset + j * count].connect(segments[offset + ((j + 1) % 4) * count]);
1197  }
1198 
1199  if (lastRowSegments && lastY == y)
1200  mergeSegments(lastRowSegments, lastRowSegmentCount, &segments[lastSegment], count);
1201 
1202  lastRowSegments = &segments[lastSegment + 2 * count];
1203  lastRowSegmentCount = count;
1204  lastSegment += 4 * count;
1205  lastY = y + rect[0].height();
1206  rect += count;
1207  }
1208 
1209  for (int i = 0; i < lastSegment; ++i) {
1210  Segment *segment = &segments[i];
1211  if (!segment->added)
1212  addSegmentsToPath(segment, result);
1213  }
1214 
1215  return result;
1216 }
1217 
1218 #if defined(Q_OS_UNIX) || defined(Q_WS_WIN)
1219 
1220 //#define QT_REGION_DEBUG
1221 /*
1222  * clip region
1223  */
1224 
1231 
1232  inline QRegionPrivate() : numRects(0), innerArea(-1) {}
1233  inline QRegionPrivate(const QRect &r) {
1234  numRects = 1;
1235  extents = r;
1236  innerRect = r;
1237  innerArea = r.width() * r.height();
1238  }
1239 
1240  inline QRegionPrivate(const QRegionPrivate &r) {
1241  rects = r.rects;
1242  numRects = r.numRects;
1243  extents = r.extents;
1244  innerRect = r.innerRect;
1245  innerArea = r.innerArea;
1246  }
1247 
1249  rects = r.rects;
1250  numRects = r.numRects;
1251  extents = r.extents;
1252  innerRect = r.innerRect;
1253  innerArea = r.innerArea;
1254  return *this;
1255  }
1256 
1257  void intersect(const QRect &r);
1258 
1259  /*
1260  * Returns true if r is guaranteed to be fully contained in this region.
1261  * A false return value does not guarantee the opposite.
1262  */
1263  inline bool contains(const QRegionPrivate &r) const {
1264  return contains(r.extents);
1265  }
1266 
1267  inline bool contains(const QRect &r2) const {
1268  const QRect &r1 = innerRect;
1269  return r2.left() >= r1.left() && r2.right() <= r1.right()
1270  && r2.top() >= r1.top() && r2.bottom() <= r1.bottom();
1271  }
1272 
1273  /*
1274  * Returns true if this region is guaranteed to be fully contained in r.
1275  */
1276  inline bool within(const QRect &r1) const {
1277  const QRect &r2 = extents;
1278  return r2.left() >= r1.left() && r2.right() <= r1.right()
1279  && r2.top() >= r1.top() && r2.bottom() <= r1.bottom();
1280  }
1281 
1282  inline void updateInnerRect(const QRect &rect) {
1283  const int area = rect.width() * rect.height();
1284  if (area > innerArea) {
1285  innerArea = area;
1286  innerRect = rect;
1287  }
1288  }
1289 
1290  inline void vectorize() {
1291  if (numRects == 1) {
1292  if (!rects.size())
1293  rects.resize(1);
1294  rects[0] = extents;
1295  }
1296  }
1297 
1298  inline void append(const QRect *r);
1299  void append(const QRegionPrivate *r);
1300  void prepend(const QRect *r);
1301  void prepend(const QRegionPrivate *r);
1302  inline bool canAppend(const QRect *r) const;
1303  inline bool canAppend(const QRegionPrivate *r) const;
1304  inline bool canPrepend(const QRect *r) const;
1305  inline bool canPrepend(const QRegionPrivate *r) const;
1306 
1307  inline bool mergeFromRight(QRect *left, const QRect *right);
1308  inline bool mergeFromLeft(QRect *left, const QRect *right);
1309  inline bool mergeFromBelow(QRect *top, const QRect *bottom,
1310  const QRect *nextToTop,
1311  const QRect *nextToBottom);
1312  inline bool mergeFromAbove(QRect *bottom, const QRect *top,
1313  const QRect *nextToBottom,
1314  const QRect *nextToTop);
1315 
1316 #ifdef QT_REGION_DEBUG
1317  void selfTest() const;
1318 #endif
1319 };
1320 
1321 static inline bool isEmptyHelper(const QRegionPrivate *preg)
1322 {
1323  return !preg || preg->numRects == 0;
1324 }
1325 
1326 static inline bool canMergeFromRight(const QRect *left, const QRect *right)
1327 {
1328  return (right->top() == left->top()
1329  && right->bottom() == left->bottom()
1330  && right->left() <= (left->right() + 1));
1331 }
1332 
1333 static inline bool canMergeFromLeft(const QRect *right, const QRect *left)
1334 {
1335  return canMergeFromRight(left, right);
1336 }
1337 
1339 {
1340  if (canMergeFromRight(left, right)) {
1341  left->setRight(right->right());
1342  updateInnerRect(*left);
1343  return true;
1344  }
1345  return false;
1346 }
1347 
1349 {
1350  if (canMergeFromLeft(right, left)) {
1351  right->setLeft(left->left());
1352  updateInnerRect(*right);
1353  return true;
1354  }
1355  return false;
1356 }
1357 
1358 static inline bool canMergeFromBelow(const QRect *top, const QRect *bottom,
1359  const QRect *nextToTop,
1360  const QRect *nextToBottom)
1361 {
1362  if (nextToTop && nextToTop->y() == top->y())
1363  return false;
1364  if (nextToBottom && nextToBottom->y() == bottom->y())
1365  return false;
1366 
1367  return ((top->bottom() >= (bottom->top() - 1))
1368  && top->left() == bottom->left()
1369  && top->right() == bottom->right());
1370 }
1371 
1372 bool QRegionPrivate::mergeFromBelow(QRect *top, const QRect *bottom,
1373  const QRect *nextToTop,
1374  const QRect *nextToBottom)
1375 {
1376  if (canMergeFromBelow(top, bottom, nextToTop, nextToBottom)) {
1377  top->setBottom(bottom->bottom());
1378  updateInnerRect(*top);
1379  return true;
1380  }
1381  return false;
1382 }
1383 
1384 bool QRegionPrivate::mergeFromAbove(QRect *bottom, const QRect *top,
1385  const QRect *nextToBottom,
1386  const QRect *nextToTop)
1387 {
1388  if (canMergeFromBelow(top, bottom, nextToTop, nextToBottom)) {
1389  bottom->setTop(top->top());
1390  updateInnerRect(*bottom);
1391  return true;
1392  }
1393  return false;
1394 }
1395 
1396 static inline QRect qt_rect_intersect_normalized(const QRect &r1,
1397  const QRect &r2)
1398 {
1399  QRect r;
1400  r.setLeft(qMax(r1.left(), r2.left()));
1401  r.setRight(qMin(r1.right(), r2.right()));
1402  r.setTop(qMax(r1.top(), r2.top()));
1403  r.setBottom(qMin(r1.bottom(), r2.bottom()));
1404  return r;
1405 }
1406 
1408 {
1409  Q_ASSERT(extents.intersects(rect));
1410  Q_ASSERT(numRects > 1);
1411 
1412 #ifdef QT_REGION_DEBUG
1413  selfTest();
1414 #endif
1415 
1416  const QRect r = rect.normalized();
1417  extents = QRect();
1418  innerRect = QRect();
1419  innerArea = -1;
1420 
1421  QRect *dest = rects.data();
1422  const QRect *src = dest;
1423  int n = numRects;
1424  numRects = 0;
1425  while (n--) {
1426  *dest = qt_rect_intersect_normalized(*src++, r);
1427  if (dest->isEmpty())
1428  continue;
1429 
1430  if (numRects == 0) {
1431  extents = *dest;
1432  } else {
1433  extents.setLeft(qMin(extents.left(), dest->left()));
1434  // hw: extents.top() will never change after initialization
1435  //extents.setTop(qMin(extents.top(), dest->top()));
1436  extents.setRight(qMax(extents.right(), dest->right()));
1437  extents.setBottom(qMax(extents.bottom(), dest->bottom()));
1438 
1439  const QRect *nextToLast = (numRects > 1 ? dest - 2 : 0);
1440 
1441  // mergeFromBelow inlined and optimized
1442  if (canMergeFromBelow(dest - 1, dest, nextToLast, 0)) {
1443  if (!n || src->y() != dest->y() || src->left() > r.right()) {
1444  QRect *prev = dest - 1;
1445  prev->setBottom(dest->bottom());
1446  updateInnerRect(*prev);
1447  continue;
1448  }
1449  }
1450  }
1451  updateInnerRect(*dest);
1452  ++dest;
1453  ++numRects;
1454  }
1455 #ifdef QT_REGION_DEBUG
1456  selfTest();
1457 #endif
1458 }
1459 
1461 {
1462  Q_ASSERT(!r->isEmpty());
1463 
1464  QRect *myLast = (numRects == 1 ? &extents : rects.data() + (numRects - 1));
1465  if (mergeFromRight(myLast, r)) {
1466  if (numRects > 1) {
1467  const QRect *nextToTop = (numRects > 2 ? myLast - 2 : 0);
1468  if (mergeFromBelow(myLast - 1, myLast, nextToTop, 0))
1469  --numRects;
1470  }
1471  } else if (mergeFromBelow(myLast, r, (numRects > 1 ? myLast - 1 : 0), 0)) {
1472  // nothing
1473  } else {
1474  vectorize();
1475  ++numRects;
1476  updateInnerRect(*r);
1477  if (rects.size() < numRects)
1479  rects[numRects - 1] = *r;
1480  }
1481  extents.setCoords(qMin(extents.left(), r->left()),
1482  qMin(extents.top(), r->top()),
1483  qMax(extents.right(), r->right()),
1484  qMax(extents.bottom(), r->bottom()));
1485 
1486 #ifdef QT_REGION_DEBUG
1487  selfTest();
1488 #endif
1489 }
1490 
1492 {
1493  Q_ASSERT(!isEmptyHelper(r));
1494 
1495  if (r->numRects == 1) {
1496  append(&r->extents);
1497  return;
1498  }
1499 
1500  vectorize();
1501 
1502  QRect *destRect = rects.data() + numRects;
1503  const QRect *srcRect = r->rects.constData();
1504  int numAppend = r->numRects;
1505 
1506  // try merging
1507  {
1508  const QRect *rFirst = srcRect;
1509  QRect *myLast = destRect - 1;
1510  const QRect *nextToLast = (numRects > 1 ? myLast - 1 : 0);
1511  if (mergeFromRight(myLast, rFirst)) {
1512  ++srcRect;
1513  --numAppend;
1514  const QRect *rNextToFirst = (numAppend > 1 ? rFirst + 2 : 0);
1515  if (mergeFromBelow(myLast, rFirst + 1, nextToLast, rNextToFirst)) {
1516  ++srcRect;
1517  --numAppend;
1518  }
1519  if (numRects > 1) {
1520  nextToLast = (numRects > 2 ? myLast - 2 : 0);
1521  rNextToFirst = (numAppend > 0 ? srcRect : 0);
1522  if (mergeFromBelow(myLast - 1, myLast, nextToLast, rNextToFirst)) {
1523  --destRect;
1524  --numRects;
1525  }
1526  }
1527  } else if (mergeFromBelow(myLast, rFirst, nextToLast, rFirst + 1)) {
1528  ++srcRect;
1529  --numAppend;
1530  }
1531  }
1532 
1533  // append rectangles
1534  if (numAppend > 0) {
1535  const int newNumRects = numRects + numAppend;
1536  if (newNumRects > rects.size()) {
1537  rects.resize(newNumRects);
1538  destRect = rects.data() + numRects;
1539  }
1540  memcpy(destRect, srcRect, numAppend * sizeof(QRect));
1541 
1542  numRects = newNumRects;
1543  }
1544 
1545  // update inner rectangle
1546  if (innerArea < r->innerArea) {
1547  innerArea = r->innerArea;
1548  innerRect = r->innerRect;
1549  }
1550 
1551  // update extents
1552  destRect = &extents;
1553  srcRect = &r->extents;
1554  extents.setCoords(qMin(destRect->left(), srcRect->left()),
1555  qMin(destRect->top(), srcRect->top()),
1556  qMax(destRect->right(), srcRect->right()),
1557  qMax(destRect->bottom(), srcRect->bottom()));
1558 
1559 #ifdef QT_REGION_DEBUG
1560  selfTest();
1561 #endif
1562 }
1563 
1565 {
1566  Q_ASSERT(!isEmptyHelper(r));
1567 
1568  if (r->numRects == 1) {
1569  prepend(&r->extents);
1570  return;
1571  }
1572 
1573  vectorize();
1574 
1575  int numPrepend = r->numRects;
1576  int numSkip = 0;
1577 
1578  // try merging
1579  {
1580  QRect *myFirst = rects.data();
1581  const QRect *nextToFirst = (numRects > 1 ? myFirst + 1 : 0);
1582  const QRect *rLast = r->rects.constData() + r->numRects - 1;
1583  const QRect *rNextToLast = (r->numRects > 1 ? rLast - 1 : 0);
1584  if (mergeFromLeft(myFirst, rLast)) {
1585  --numPrepend;
1586  --rLast;
1587  rNextToLast = (numPrepend > 1 ? rLast - 1 : 0);
1588  if (mergeFromAbove(myFirst, rLast, nextToFirst, rNextToLast)) {
1589  --numPrepend;
1590  --rLast;
1591  }
1592  if (numRects > 1) {
1593  nextToFirst = (numRects > 2? myFirst + 2 : 0);
1594  rNextToLast = (numPrepend > 0 ? rLast : 0);
1595  if (mergeFromAbove(myFirst + 1, myFirst, nextToFirst, rNextToLast)) {
1596  --numRects;
1597  ++numSkip;
1598  }
1599  }
1600  } else if (mergeFromAbove(myFirst, rLast, nextToFirst, rNextToLast)) {
1601  --numPrepend;
1602  }
1603  }
1604 
1605  if (numPrepend > 0) {
1606  const int newNumRects = numRects + numPrepend;
1607  if (newNumRects > rects.size())
1608  rects.resize(newNumRects);
1609 
1610  // move existing rectangles
1611  memmove(rects.data() + numPrepend, rects.constData() + numSkip,
1612  numRects * sizeof(QRect));
1613 
1614  // prepend new rectangles
1615  memcpy(rects.data(), r->rects.constData(), numPrepend * sizeof(QRect));
1616 
1617  numRects = newNumRects;
1618  }
1619 
1620  // update inner rectangle
1621  if (innerArea < r->innerArea) {
1622  innerArea = r->innerArea;
1623  innerRect = r->innerRect;
1624  }
1625 
1626  // update extents
1627  extents.setCoords(qMin(extents.left(), r->extents.left()),
1628  qMin(extents.top(), r->extents.top()),
1629  qMax(extents.right(), r->extents.right()),
1630  qMax(extents.bottom(), r->extents.bottom()));
1631 
1632 #ifdef QT_REGION_DEBUG
1633  selfTest();
1634 #endif
1635 }
1636 
1638 {
1639  Q_ASSERT(!r->isEmpty());
1640 
1641  QRect *myFirst = (numRects == 1 ? &extents : rects.data());
1642  if (mergeFromLeft(myFirst, r)) {
1643  if (numRects > 1) {
1644  const QRect *nextToFirst = (numRects > 2 ? myFirst + 2 : 0);
1645  if (mergeFromAbove(myFirst + 1, myFirst, nextToFirst, 0)) {
1646  --numRects;
1647  memmove(rects.data(), rects.constData() + 1,
1648  numRects * sizeof(QRect));
1649  }
1650  }
1651  } else if (mergeFromAbove(myFirst, r, (numRects > 1 ? myFirst + 1 : 0), 0)) {
1652  // nothing
1653  } else {
1654  vectorize();
1655  ++numRects;
1656  updateInnerRect(*r);
1657  rects.prepend(*r);
1658  }
1659  extents.setCoords(qMin(extents.left(), r->left()),
1660  qMin(extents.top(), r->top()),
1661  qMax(extents.right(), r->right()),
1662  qMax(extents.bottom(), r->bottom()));
1663 
1664 #ifdef QT_REGION_DEBUG
1665  selfTest();
1666 #endif
1667 }
1668 
1669 bool QRegionPrivate::canAppend(const QRect *r) const
1670 {
1671  Q_ASSERT(!r->isEmpty());
1672 
1673  const QRect *myLast = (numRects == 1) ? &extents : (rects.constData() + (numRects - 1));
1674  if (r->top() > myLast->bottom())
1675  return true;
1676  if (r->top() == myLast->top()
1677  && r->height() == myLast->height()
1678  && r->left() > myLast->right())
1679  {
1680  return true;
1681  }
1682 
1683  return false;
1684 }
1685 
1687 {
1688  return canAppend(r->numRects == 1 ? &r->extents : r->rects.constData());
1689 }
1690 
1691 bool QRegionPrivate::canPrepend(const QRect *r) const
1692 {
1693  Q_ASSERT(!r->isEmpty());
1694 
1695  const QRect *myFirst = (numRects == 1) ? &extents : rects.constData();
1696  if (r->bottom() < myFirst->top()) // not overlapping
1697  return true;
1698  if (r->top() == myFirst->top()
1699  && r->height() == myFirst->height()
1700  && r->right() < myFirst->left())
1701  {
1702  return true;
1703  }
1704 
1705  return false;
1706 }
1707 
1709 {
1710  return canPrepend(r->numRects == 1 ? &r->extents : r->rects.constData() + r->numRects - 1);
1711 }
1712 
1713 #ifdef QT_REGION_DEBUG
1714 void QRegionPrivate::selfTest() const
1715 {
1716  if (numRects == 0) {
1717  Q_ASSERT(extents.isEmpty());
1718  Q_ASSERT(innerRect.isEmpty());
1719  return;
1720  }
1721 
1722  Q_ASSERT(innerArea == (innerRect.width() * innerRect.height()));
1723 
1724  if (numRects == 1) {
1725  Q_ASSERT(innerRect == extents);
1726  Q_ASSERT(!innerRect.isEmpty());
1727  return;
1728  }
1729 
1730  for (int i = 0; i < numRects; ++i) {
1731  const QRect r = rects.at(i);
1732  if ((r.width() * r.height()) > innerArea)
1733  qDebug() << "selfTest(): innerRect" << innerRect << '<' << r;
1734  }
1735 
1736  QRect r = rects.first();
1737  for (int i = 1; i < numRects; ++i) {
1738  const QRect r2 = rects.at(i);
1739  Q_ASSERT(!r2.isEmpty());
1740  if (r2.y() == r.y()) {
1741  Q_ASSERT(r.bottom() == r2.bottom());
1742  Q_ASSERT(r.right() < (r2.left() + 1));
1743  } else {
1744  Q_ASSERT(r2.y() >= r.bottom());
1745  }
1746  r = r2;
1747  }
1748 }
1749 #endif // QT_REGION_DEBUG
1750 
1751 #if defined(Q_WS_X11)
1753 # include "qregion_x11.cpp"
1755 #elif defined(Q_WS_MAC)
1757 # include "qregion_mac.cpp"
1759 #elif defined(Q_WS_WIN)
1761 # include "qregion_win.cpp"
1763 #elif defined(Q_WS_QWS) || defined(Q_WS_QPA)
1764 static QRegionPrivate qrp;
1766 #endif
1767 
1768 typedef void (*OverlapFunc)(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
1769  register const QRect *r2, const QRect *r2End, register int y1, register int y2);
1770 typedef void (*NonOverlapFunc)(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
1771  register int y1, register int y2);
1772 
1773 static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2);
1774 static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest);
1775 static void miRegionOp(register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2,
1776  OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
1777  NonOverlapFunc nonOverlap2Func);
1778 
1779 #define RectangleOut 0
1780 #define RectangleIn 1
1781 #define RectanglePart 2
1782 #define EvenOddRule 0
1783 #define WindingRule 1
1784 
1785 // START OF region.h extract
1786 /* $XConsortium: region.h,v 11.14 94/04/17 20:22:20 rws Exp $ */
1787 /************************************************************************
1788 
1789 Copyright (c) 1987 X Consortium
1790 
1791 Permission is hereby granted, free of charge, to any person obtaining a copy
1792 of this software and associated documentation files (the "Software"), to deal
1793 in the Software without restriction, including without limitation the rights
1794 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1795 copies of the Software, and to permit persons to whom the Software is
1796 furnished to do so, subject to the following conditions:
1797 
1798 The above copyright notice and this permission notice shall be included in
1799 all copies or substantial portions of the Software.
1800 
1801 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1802 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1803 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1804 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1805 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1806 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1807 
1808 Except as contained in this notice, the name of the X Consortium shall not be
1809 used in advertising or otherwise to promote the sale, use or other dealings
1810 in this Software without prior written authorization from the X Consortium.
1811 
1812 
1813 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
1814 
1815  All Rights Reserved
1816 
1817 Permission to use, copy, modify, and distribute this software and its
1818 documentation for any purpose and without fee is hereby granted,
1819 provided that the above copyright notice appear in all copies and that
1820 both that copyright notice and this permission notice appear in
1821 supporting documentation, and that the name of Digital not be
1822 used in advertising or publicity pertaining to distribution of the
1823 software without specific, written prior permission.
1824 
1825 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1826 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1827 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1828 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1829 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1830 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1831 SOFTWARE.
1832 
1833 ************************************************************************/
1834 
1835 #ifndef _XREGION_H
1836 #define _XREGION_H
1837 
1839 #include <limits.h>
1841 
1842 /* 1 if two BOXes overlap.
1843  * 0 if two BOXes do not overlap.
1844  * Remember, x2 and y2 are not in the region
1845  */
1846 #define EXTENTCHECK(r1, r2) \
1847  ((r1)->right() >= (r2)->left() && \
1848  (r1)->left() <= (r2)->right() && \
1849  (r1)->bottom() >= (r2)->top() && \
1850  (r1)->top() <= (r2)->bottom())
1851 
1852 /*
1853  * update region extents
1854  */
1855 #define EXTENTS(r,idRect){\
1856  if((r)->left() < (idRect)->extents.left())\
1857  (idRect)->extents.setLeft((r)->left());\
1858  if((r)->top() < (idRect)->extents.top())\
1859  (idRect)->extents.setTop((r)->top());\
1860  if((r)->right() > (idRect)->extents.right())\
1861  (idRect)->extents.setRight((r)->right());\
1862  if((r)->bottom() > (idRect)->extents.bottom())\
1863  (idRect)->extents.setBottom((r)->bottom());\
1864  }
1865 
1866 /*
1867  * Check to see if there is enough memory in the present region.
1868  */
1869 #define MEMCHECK(dest, rect, firstrect){\
1870  if ((dest).numRects >= ((dest).rects.size()-1)){\
1871  firstrect.resize(firstrect.size() * 2); \
1872  (rect) = (firstrect).data() + (dest).numRects;\
1873  }\
1874  }
1875 
1876 
1877 /*
1878  * number of points to buffer before sending them off
1879  * to scanlines(): Must be an even number
1880  */
1881 #define NUMPTSTOBUFFER 200
1882 
1883 /*
1884  * used to allocate buffers for points and link
1885  * the buffers together
1886  */
1887 typedef struct _POINTBLOCK {
1888  int data[NUMPTSTOBUFFER * sizeof(QPoint)];
1891 } POINTBLOCK;
1892 
1893 #endif
1894 // END OF region.h extract
1895 
1896 // START OF Region.c extract
1897 /* $XConsortium: Region.c /main/30 1996/10/22 14:21:24 kaleb $ */
1898 /************************************************************************
1899 
1900 Copyright (c) 1987, 1988 X Consortium
1901 
1902 Permission is hereby granted, free of charge, to any person obtaining a copy
1903 of this software and associated documentation files (the "Software"), to deal
1904 in the Software without restriction, including without limitation the rights
1905 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1906 copies of the Software, and to permit persons to whom the Software is
1907 furnished to do so, subject to the following conditions:
1908 
1909 The above copyright notice and this permission notice shall be included in
1910 all copies or substantial portions of the Software.
1911 
1912 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1913 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1914 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1915 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1916 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1917 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1918 
1919 Except as contained in this notice, the name of the X Consortium shall not be
1920 used in advertising or otherwise to promote the sale, use or other dealings
1921 in this Software without prior written authorization from the X Consortium.
1922 
1923 
1924 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
1925 
1926  All Rights Reserved
1927 
1928 Permission to use, copy, modify, and distribute this software and its
1929 documentation for any purpose and without fee is hereby granted,
1930 provided that the above copyright notice appear in all copies and that
1931 both that copyright notice and this permission notice appear in
1932 supporting documentation, and that the name of Digital not be
1933 used in advertising or publicity pertaining to distribution of the
1934 software without specific, written prior permission.
1935 
1936 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1937 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1938 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1939 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1940 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1941 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1942 SOFTWARE.
1943 
1944 ************************************************************************/
1945 /*
1946  * The functions in this file implement the Region abstraction, similar to one
1947  * used in the X11 sample server. A Region is simply an area, as the name
1948  * implies, and is implemented as a "y-x-banded" array of rectangles. To
1949  * explain: Each Region is made up of a certain number of rectangles sorted
1950  * by y coordinate first, and then by x coordinate.
1951  *
1952  * Furthermore, the rectangles are banded such that every rectangle with a
1953  * given upper-left y coordinate (y1) will have the same lower-right y
1954  * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
1955  * will span the entire vertical distance of the band. This means that some
1956  * areas that could be merged into a taller rectangle will be represented as
1957  * several shorter rectangles to account for shorter rectangles to its left
1958  * or right but within its "vertical scope".
1959  *
1960  * An added constraint on the rectangles is that they must cover as much
1961  * horizontal area as possible. E.g. no two rectangles in a band are allowed
1962  * to touch.
1963  *
1964  * Whenever possible, bands will be merged together to cover a greater vertical
1965  * distance (and thus reduce the number of rectangles). Two bands can be merged
1966  * only if the bottom of one touches the top of the other and they have
1967  * rectangles in the same places (of the same width, of course). This maintains
1968  * the y-x-banding that's so nice to have...
1969  */
1970 /* $XFree86: xc/lib/X11/Region.c,v 1.1.1.2.2.2 1998/10/04 15:22:50 hohndel Exp $ */
1971 
1972 static void UnionRectWithRegion(register const QRect *rect, const QRegionPrivate *source,
1973  QRegionPrivate &dest)
1974 {
1975  if (rect->isEmpty())
1976  return;
1977 
1978  Q_ASSERT(EqualRegion(source, &dest));
1979 
1980  if (dest.numRects == 0) {
1981  dest = QRegionPrivate(*rect);
1982  } else if (dest.canAppend(rect)) {
1983  dest.append(rect);
1984  } else {
1985  QRegionPrivate p(*rect);
1986  UnionRegion(&p, source, dest);
1987  }
1988 }
1989 
1990 /*-
1991  *-----------------------------------------------------------------------
1992  * miSetExtents --
1993  * Reset the extents and innerRect of a region to what they should be.
1994  * Called by miSubtract and miIntersect b/c they can't figure it out
1995  * along the way or do so easily, as miUnion can.
1996  *
1997  * Results:
1998  * None.
1999  *
2000  * Side Effects:
2001  * The region's 'extents' and 'innerRect' structure is overwritten.
2002  *
2003  *-----------------------------------------------------------------------
2004  */
2005 static void miSetExtents(QRegionPrivate &dest)
2006 {
2007  register const QRect *pBox,
2008  *pBoxEnd;
2009  register QRect *pExtents;
2010 
2011  dest.innerRect.setCoords(0, 0, -1, -1);
2012  dest.innerArea = -1;
2013  if (dest.numRects == 0) {
2014  dest.extents.setCoords(0, 0, -1, -1);
2015  return;
2016  }
2017 
2018  pExtents = &dest.extents;
2019  if (dest.rects.isEmpty())
2020  pBox = &dest.extents;
2021  else
2022  pBox = dest.rects.constData();
2023  pBoxEnd = pBox + dest.numRects - 1;
2024 
2025  /*
2026  * Since pBox is the first rectangle in the region, it must have the
2027  * smallest y1 and since pBoxEnd is the last rectangle in the region,
2028  * it must have the largest y2, because of banding. Initialize x1 and
2029  * x2 from pBox and pBoxEnd, resp., as good things to initialize them
2030  * to...
2031  */
2032  pExtents->setLeft(pBox->left());
2033  pExtents->setTop(pBox->top());
2034  pExtents->setRight(pBoxEnd->right());
2035  pExtents->setBottom(pBoxEnd->bottom());
2036 
2037  Q_ASSERT(pExtents->top() <= pExtents->bottom());
2038  while (pBox <= pBoxEnd) {
2039  if (pBox->left() < pExtents->left())
2040  pExtents->setLeft(pBox->left());
2041  if (pBox->right() > pExtents->right())
2042  pExtents->setRight(pBox->right());
2043  dest.updateInnerRect(*pBox);
2044  ++pBox;
2045  }
2046  Q_ASSERT(pExtents->left() <= pExtents->right());
2047 }
2048 
2049 /* TranslateRegion(pRegion, x, y)
2050  translates in place
2051  added by raymond
2052 */
2053 
2054 static void OffsetRegion(register QRegionPrivate &region, register int x, register int y)
2055 {
2056  if (region.rects.size()) {
2057  register QRect *pbox = region.rects.data();
2058  register int nbox = region.numRects;
2059 
2060  while (nbox--) {
2061  pbox->translate(x, y);
2062  ++pbox;
2063  }
2064  }
2065  region.extents.translate(x, y);
2066  region.innerRect.translate(x, y);
2067 }
2068 
2069 /*======================================================================
2070  * Region Intersection
2071  *====================================================================*/
2072 /*-
2073  *-----------------------------------------------------------------------
2074  * miIntersectO --
2075  * Handle an overlapping band for miIntersect.
2076  *
2077  * Results:
2078  * None.
2079  *
2080  * Side Effects:
2081  * Rectangles may be added to the region.
2082  *
2083  *-----------------------------------------------------------------------
2084  */
2085 static void miIntersectO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
2086  register const QRect *r2, const QRect *r2End, int y1, int y2)
2087 {
2088  register int x1;
2089  register int x2;
2090  register QRect *pNextRect;
2091 
2092  pNextRect = dest.rects.data() + dest.numRects;
2093 
2094  while (r1 != r1End && r2 != r2End) {
2095  x1 = qMax(r1->left(), r2->left());
2096  x2 = qMin(r1->right(), r2->right());
2097 
2098  /*
2099  * If there's any overlap between the two rectangles, add that
2100  * overlap to the new region.
2101  * There's no need to check for subsumption because the only way
2102  * such a need could arise is if some region has two rectangles
2103  * right next to each other. Since that should never happen...
2104  */
2105  if (x1 <= x2) {
2106  Q_ASSERT(y1 <= y2);
2107  MEMCHECK(dest, pNextRect, dest.rects)
2108  pNextRect->setCoords(x1, y1, x2, y2);
2109  ++dest.numRects;
2110  ++pNextRect;
2111  }
2112 
2113  /*
2114  * Need to advance the pointers. Shift the one that extends
2115  * to the right the least, since the other still has a chance to
2116  * overlap with that region's next rectangle, if you see what I mean.
2117  */
2118  if (r1->right() < r2->right()) {
2119  ++r1;
2120  } else if (r2->right() < r1->right()) {
2121  ++r2;
2122  } else {
2123  ++r1;
2124  ++r2;
2125  }
2126  }
2127 }
2128 
2129 /*======================================================================
2130  * Generic Region Operator
2131  *====================================================================*/
2132 
2133 /*-
2134  *-----------------------------------------------------------------------
2135  * miCoalesce --
2136  * Attempt to merge the boxes in the current band with those in the
2137  * previous one. Used only by miRegionOp.
2138  *
2139  * Results:
2140  * The new index for the previous band.
2141  *
2142  * Side Effects:
2143  * If coalescing takes place:
2144  * - rectangles in the previous band will have their y2 fields
2145  * altered.
2146  * - dest.numRects will be decreased.
2147  *
2148  *-----------------------------------------------------------------------
2149  */
2150 static int miCoalesce(register QRegionPrivate &dest, int prevStart, int curStart)
2151 {
2152  register QRect *pPrevBox; /* Current box in previous band */
2153  register QRect *pCurBox; /* Current box in current band */
2154  register QRect *pRegEnd; /* End of region */
2155  int curNumRects; /* Number of rectangles in current band */
2156  int prevNumRects; /* Number of rectangles in previous band */
2157  int bandY1; /* Y1 coordinate for current band */
2158  QRect *rData = dest.rects.data();
2159 
2160  pRegEnd = rData + dest.numRects;
2161 
2162  pPrevBox = rData + prevStart;
2163  prevNumRects = curStart - prevStart;
2164 
2165  /*
2166  * Figure out how many rectangles are in the current band. Have to do
2167  * this because multiple bands could have been added in miRegionOp
2168  * at the end when one region has been exhausted.
2169  */
2170  pCurBox = rData + curStart;
2171  bandY1 = pCurBox->top();
2172  for (curNumRects = 0; pCurBox != pRegEnd && pCurBox->top() == bandY1; ++curNumRects) {
2173  ++pCurBox;
2174  }
2175 
2176  if (pCurBox != pRegEnd) {
2177  /*
2178  * If more than one band was added, we have to find the start
2179  * of the last band added so the next coalescing job can start
2180  * at the right place... (given when multiple bands are added,
2181  * this may be pointless -- see above).
2182  */
2183  --pRegEnd;
2184  while ((pRegEnd - 1)->top() == pRegEnd->top())
2185  --pRegEnd;
2186  curStart = pRegEnd - rData;
2187  pRegEnd = rData + dest.numRects;
2188  }
2189 
2190  if (curNumRects == prevNumRects && curNumRects != 0) {
2191  pCurBox -= curNumRects;
2192  /*
2193  * The bands may only be coalesced if the bottom of the previous
2194  * matches the top scanline of the current.
2195  */
2196  if (pPrevBox->bottom() == pCurBox->top() - 1) {
2197  /*
2198  * Make sure the bands have boxes in the same places. This
2199  * assumes that boxes have been added in such a way that they
2200  * cover the most area possible. I.e. two boxes in a band must
2201  * have some horizontal space between them.
2202  */
2203  do {
2204  if (pPrevBox->left() != pCurBox->left() || pPrevBox->right() != pCurBox->right()) {
2205  // The bands don't line up so they can't be coalesced.
2206  return curStart;
2207  }
2208  ++pPrevBox;
2209  ++pCurBox;
2210  --prevNumRects;
2211  } while (prevNumRects != 0);
2212 
2213  dest.numRects -= curNumRects;
2214  pCurBox -= curNumRects;
2215  pPrevBox -= curNumRects;
2216 
2217  /*
2218  * The bands may be merged, so set the bottom y of each box
2219  * in the previous band to that of the corresponding box in
2220  * the current band.
2221  */
2222  do {
2223  pPrevBox->setBottom(pCurBox->bottom());
2224  dest.updateInnerRect(*pPrevBox);
2225  ++pPrevBox;
2226  ++pCurBox;
2227  curNumRects -= 1;
2228  } while (curNumRects != 0);
2229 
2230  /*
2231  * If only one band was added to the region, we have to backup
2232  * curStart to the start of the previous band.
2233  *
2234  * If more than one band was added to the region, copy the
2235  * other bands down. The assumption here is that the other bands
2236  * came from the same region as the current one and no further
2237  * coalescing can be done on them since it's all been done
2238  * already... curStart is already in the right place.
2239  */
2240  if (pCurBox == pRegEnd) {
2241  curStart = prevStart;
2242  } else {
2243  do {
2244  *pPrevBox++ = *pCurBox++;
2245  dest.updateInnerRect(*pPrevBox);
2246  } while (pCurBox != pRegEnd);
2247  }
2248  }
2249  }
2250  return curStart;
2251 }
2252 
2253 /*-
2254  *-----------------------------------------------------------------------
2255  * miRegionOp --
2256  * Apply an operation to two regions. Called by miUnion, miInverse,
2257  * miSubtract, miIntersect...
2258  *
2259  * Results:
2260  * None.
2261  *
2262  * Side Effects:
2263  * The new region is overwritten.
2264  *
2265  * Notes:
2266  * The idea behind this function is to view the two regions as sets.
2267  * Together they cover a rectangle of area that this function divides
2268  * into horizontal bands where points are covered only by one region
2269  * or by both. For the first case, the nonOverlapFunc is called with
2270  * each the band and the band's upper and lower extents. For the
2271  * second, the overlapFunc is called to process the entire band. It
2272  * is responsible for clipping the rectangles in the band, though
2273  * this function provides the boundaries.
2274  * At the end of each band, the new region is coalesced, if possible,
2275  * to reduce the number of rectangles in the region.
2276  *
2277  *-----------------------------------------------------------------------
2278  */
2279 static void miRegionOp(register QRegionPrivate &dest,
2280  const QRegionPrivate *reg1, const QRegionPrivate *reg2,
2281  OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
2282  NonOverlapFunc nonOverlap2Func)
2283 {
2284  register const QRect *r1; // Pointer into first region
2285  register const QRect *r2; // Pointer into 2d region
2286  const QRect *r1End; // End of 1st region
2287  const QRect *r2End; // End of 2d region
2288  register int ybot; // Bottom of intersection
2289  register int ytop; // Top of intersection
2290  int prevBand; // Index of start of previous band in dest
2291  int curBand; // Index of start of current band in dest
2292  register const QRect *r1BandEnd; // End of current band in r1
2293  register const QRect *r2BandEnd; // End of current band in r2
2294  int top; // Top of non-overlapping band
2295  int bot; // Bottom of non-overlapping band
2296 
2297  /*
2298  * Initialization:
2299  * set r1, r2, r1End and r2End appropriately, preserve the important
2300  * parts of the destination region until the end in case it's one of
2301  * the two source regions, then mark the "new" region empty, allocating
2302  * another array of rectangles for it to use.
2303  */
2304  if (reg1->numRects == 1)
2305  r1 = &reg1->extents;
2306  else
2307  r1 = reg1->rects.constData();
2308  if (reg2->numRects == 1)
2309  r2 = &reg2->extents;
2310  else
2311  r2 = reg2->rects.constData();
2312 
2313  r1End = r1 + reg1->numRects;
2314  r2End = r2 + reg2->numRects;
2315 
2316  dest.vectorize();
2317 
2318  QVector<QRect> oldRects = dest.rects;
2319 
2320  dest.numRects = 0;
2321 
2322  /*
2323  * Allocate a reasonable number of rectangles for the new region. The idea
2324  * is to allocate enough so the individual functions don't need to
2325  * reallocate and copy the array, which is time consuming, yet we don't
2326  * have to worry about using too much memory. I hope to be able to
2327  * nuke the realloc() at the end of this function eventually.
2328  */
2329  dest.rects.resize(qMax(reg1->numRects,reg2->numRects) * 2);
2330 
2331  /*
2332  * Initialize ybot and ytop.
2333  * In the upcoming loop, ybot and ytop serve different functions depending
2334  * on whether the band being handled is an overlapping or non-overlapping
2335  * band.
2336  * In the case of a non-overlapping band (only one of the regions
2337  * has points in the band), ybot is the bottom of the most recent
2338  * intersection and thus clips the top of the rectangles in that band.
2339  * ytop is the top of the next intersection between the two regions and
2340  * serves to clip the bottom of the rectangles in the current band.
2341  * For an overlapping band (where the two regions intersect), ytop clips
2342  * the top of the rectangles of both regions and ybot clips the bottoms.
2343  */
2344  if (reg1->extents.top() < reg2->extents.top())
2345  ybot = reg1->extents.top() - 1;
2346  else
2347  ybot = reg2->extents.top() - 1;
2348 
2349  /*
2350  * prevBand serves to mark the start of the previous band so rectangles
2351  * can be coalesced into larger rectangles. qv. miCoalesce, above.
2352  * In the beginning, there is no previous band, so prevBand == curBand
2353  * (curBand is set later on, of course, but the first band will always
2354  * start at index 0). prevBand and curBand must be indices because of
2355  * the possible expansion, and resultant moving, of the new region's
2356  * array of rectangles.
2357  */
2358  prevBand = 0;
2359 
2360  do {
2361  curBand = dest.numRects;
2362 
2363  /*
2364  * This algorithm proceeds one source-band (as opposed to a
2365  * destination band, which is determined by where the two regions
2366  * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
2367  * rectangle after the last one in the current band for their
2368  * respective regions.
2369  */
2370  r1BandEnd = r1;
2371  while (r1BandEnd != r1End && r1BandEnd->top() == r1->top())
2372  ++r1BandEnd;
2373 
2374  r2BandEnd = r2;
2375  while (r2BandEnd != r2End && r2BandEnd->top() == r2->top())
2376  ++r2BandEnd;
2377 
2378  /*
2379  * First handle the band that doesn't intersect, if any.
2380  *
2381  * Note that attention is restricted to one band in the
2382  * non-intersecting region at once, so if a region has n
2383  * bands between the current position and the next place it overlaps
2384  * the other, this entire loop will be passed through n times.
2385  */
2386  if (r1->top() < r2->top()) {
2387  top = qMax(r1->top(), ybot + 1);
2388  bot = qMin(r1->bottom(), r2->top() - 1);
2389 
2390  if (nonOverlap1Func != 0 && bot >= top)
2391  (*nonOverlap1Func)(dest, r1, r1BandEnd, top, bot);
2392  ytop = r2->top();
2393  } else if (r2->top() < r1->top()) {
2394  top = qMax(r2->top(), ybot + 1);
2395  bot = qMin(r2->bottom(), r1->top() - 1);
2396 
2397  if (nonOverlap2Func != 0 && bot >= top)
2398  (*nonOverlap2Func)(dest, r2, r2BandEnd, top, bot);
2399  ytop = r1->top();
2400  } else {
2401  ytop = r1->top();
2402  }
2403 
2404  /*
2405  * If any rectangles got added to the region, try and coalesce them
2406  * with rectangles from the previous band. Note we could just do
2407  * this test in miCoalesce, but some machines incur a not
2408  * inconsiderable cost for function calls, so...
2409  */
2410  if (dest.numRects != curBand)
2411  prevBand = miCoalesce(dest, prevBand, curBand);
2412 
2413  /*
2414  * Now see if we've hit an intersecting band. The two bands only
2415  * intersect if ybot >= ytop
2416  */
2417  ybot = qMin(r1->bottom(), r2->bottom());
2418  curBand = dest.numRects;
2419  if (ybot >= ytop)
2420  (*overlapFunc)(dest, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
2421 
2422  if (dest.numRects != curBand)
2423  prevBand = miCoalesce(dest, prevBand, curBand);
2424 
2425  /*
2426  * If we've finished with a band (y2 == ybot) we skip forward
2427  * in the region to the next band.
2428  */
2429  if (r1->bottom() == ybot)
2430  r1 = r1BandEnd;
2431  if (r2->bottom() == ybot)
2432  r2 = r2BandEnd;
2433  } while (r1 != r1End && r2 != r2End);
2434 
2435  /*
2436  * Deal with whichever region still has rectangles left.
2437  */
2438  curBand = dest.numRects;
2439  if (r1 != r1End) {
2440  if (nonOverlap1Func != 0) {
2441  do {
2442  r1BandEnd = r1;
2443  while (r1BandEnd < r1End && r1BandEnd->top() == r1->top())
2444  ++r1BandEnd;
2445  (*nonOverlap1Func)(dest, r1, r1BandEnd, qMax(r1->top(), ybot + 1), r1->bottom());
2446  r1 = r1BandEnd;
2447  } while (r1 != r1End);
2448  }
2449  } else if ((r2 != r2End) && (nonOverlap2Func != 0)) {
2450  do {
2451  r2BandEnd = r2;
2452  while (r2BandEnd < r2End && r2BandEnd->top() == r2->top())
2453  ++r2BandEnd;
2454  (*nonOverlap2Func)(dest, r2, r2BandEnd, qMax(r2->top(), ybot + 1), r2->bottom());
2455  r2 = r2BandEnd;
2456  } while (r2 != r2End);
2457  }
2458 
2459  if (dest.numRects != curBand)
2460  (void)miCoalesce(dest, prevBand, curBand);
2461 
2462  /*
2463  * A bit of cleanup. To keep regions from growing without bound,
2464  * we shrink the array of rectangles to match the new number of
2465  * rectangles in the region.
2466  *
2467  * Only do this stuff if the number of rectangles allocated is more than
2468  * twice the number of rectangles in the region (a simple optimization).
2469  */
2470  if (qMax(4, dest.numRects) < (dest.rects.size() >> 1))
2471  dest.rects.resize(dest.numRects);
2472 }
2473 
2474 /*======================================================================
2475  * Region Union
2476  *====================================================================*/
2477 
2478 /*-
2479  *-----------------------------------------------------------------------
2480  * miUnionNonO --
2481  * Handle a non-overlapping band for the union operation. Just
2482  * Adds the rectangles into the region. Doesn't have to check for
2483  * subsumption or anything.
2484  *
2485  * Results:
2486  * None.
2487  *
2488  * Side Effects:
2489  * dest.numRects is incremented and the final rectangles overwritten
2490  * with the rectangles we're passed.
2491  *
2492  *-----------------------------------------------------------------------
2493  */
2494 
2495 static void miUnionNonO(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
2496  register int y1, register int y2)
2497 {
2498  register QRect *pNextRect;
2499 
2500  pNextRect = dest.rects.data() + dest.numRects;
2501 
2502  Q_ASSERT(y1 <= y2);
2503 
2504  while (r != rEnd) {
2505  Q_ASSERT(r->left() <= r->right());
2506  MEMCHECK(dest, pNextRect, dest.rects)
2507  pNextRect->setCoords(r->left(), y1, r->right(), y2);
2508  dest.numRects++;
2509  ++pNextRect;
2510  ++r;
2511  }
2512 }
2513 
2514 
2515 /*-
2516  *-----------------------------------------------------------------------
2517  * miUnionO --
2518  * Handle an overlapping band for the union operation. Picks the
2519  * left-most rectangle each time and merges it into the region.
2520  *
2521  * Results:
2522  * None.
2523  *
2524  * Side Effects:
2525  * Rectangles are overwritten in dest.rects and dest.numRects will
2526  * be changed.
2527  *
2528  *-----------------------------------------------------------------------
2529  */
2530 
2531 static void miUnionO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
2532  register const QRect *r2, const QRect *r2End, register int y1, register int y2)
2533 {
2534  register QRect *pNextRect;
2535 
2536  pNextRect = dest.rects.data() + dest.numRects;
2537 
2538 #define MERGERECT(r) \
2539  if ((dest.numRects != 0) && \
2540  (pNextRect[-1].top() == y1) && \
2541  (pNextRect[-1].bottom() == y2) && \
2542  (pNextRect[-1].right() >= r->left()-1)) { \
2543  if (pNextRect[-1].right() < r->right()) { \
2544  pNextRect[-1].setRight(r->right()); \
2545  dest.updateInnerRect(pNextRect[-1]); \
2546  Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
2547  } \
2548  } else { \
2549  MEMCHECK(dest, pNextRect, dest.rects) \
2550  pNextRect->setCoords(r->left(), y1, r->right(), y2); \
2551  dest.updateInnerRect(*pNextRect); \
2552  dest.numRects++; \
2553  pNextRect++; \
2554  } \
2555  r++;
2556 
2557  Q_ASSERT(y1 <= y2);
2558  while (r1 != r1End && r2 != r2End) {
2559  if (r1->left() < r2->left()) {
2560  MERGERECT(r1)
2561  } else {
2562  MERGERECT(r2)
2563  }
2564  }
2565 
2566  if (r1 != r1End) {
2567  do {
2568  MERGERECT(r1)
2569  } while (r1 != r1End);
2570  } else {
2571  while (r2 != r2End) {
2572  MERGERECT(r2)
2573  }
2574  }
2575 }
2576 
2577 static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest)
2578 {
2579  Q_ASSERT(!isEmptyHelper(reg1) && !isEmptyHelper(reg2));
2580  Q_ASSERT(!reg1->contains(*reg2));
2581  Q_ASSERT(!reg2->contains(*reg1));
2582  Q_ASSERT(!EqualRegion(reg1, reg2));
2583  Q_ASSERT(!reg1->canAppend(reg2));
2584  Q_ASSERT(!reg2->canAppend(reg1));
2585 
2586  if (reg1->innerArea > reg2->innerArea) {
2587  dest.innerArea = reg1->innerArea;
2588  dest.innerRect = reg1->innerRect;
2589  } else {
2590  dest.innerArea = reg2->innerArea;
2591  dest.innerRect = reg2->innerRect;
2592  }
2593  miRegionOp(dest, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);
2594 
2595  dest.extents.setCoords(qMin(reg1->extents.left(), reg2->extents.left()),
2596  qMin(reg1->extents.top(), reg2->extents.top()),
2597  qMax(reg1->extents.right(), reg2->extents.right()),
2598  qMax(reg1->extents.bottom(), reg2->extents.bottom()));
2599 }
2600 
2601 /*======================================================================
2602  * Region Subtraction
2603  *====================================================================*/
2604 
2605 /*-
2606  *-----------------------------------------------------------------------
2607  * miSubtractNonO --
2608  * Deal with non-overlapping band for subtraction. Any parts from
2609  * region 2 we discard. Anything from region 1 we add to the region.
2610  *
2611  * Results:
2612  * None.
2613  *
2614  * Side Effects:
2615  * dest may be affected.
2616  *
2617  *-----------------------------------------------------------------------
2618  */
2619 
2620 static void miSubtractNonO1(register QRegionPrivate &dest, register const QRect *r,
2621  const QRect *rEnd, register int y1, register int y2)
2622 {
2623  register QRect *pNextRect;
2624 
2625  pNextRect = dest.rects.data() + dest.numRects;
2626 
2627  Q_ASSERT(y1<=y2);
2628 
2629  while (r != rEnd) {
2630  Q_ASSERT(r->left() <= r->right());
2631  MEMCHECK(dest, pNextRect, dest.rects)
2632  pNextRect->setCoords(r->left(), y1, r->right(), y2);
2633  ++dest.numRects;
2634  ++pNextRect;
2635  ++r;
2636  }
2637 }
2638 
2639 /*-
2640  *-----------------------------------------------------------------------
2641  * miSubtractO --
2642  * Overlapping band subtraction. x1 is the left-most point not yet
2643  * checked.
2644  *
2645  * Results:
2646  * None.
2647  *
2648  * Side Effects:
2649  * dest may have rectangles added to it.
2650  *
2651  *-----------------------------------------------------------------------
2652  */
2653 
2654 static void miSubtractO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
2655  register const QRect *r2, const QRect *r2End, register int y1, register int y2)
2656 {
2657  register QRect *pNextRect;
2658  register int x1;
2659 
2660  x1 = r1->left();
2661 
2662  Q_ASSERT(y1 <= y2);
2663  pNextRect = dest.rects.data() + dest.numRects;
2664 
2665  while (r1 != r1End && r2 != r2End) {
2666  if (r2->right() < x1) {
2667  /*
2668  * Subtrahend missed the boat: go to next subtrahend.
2669  */
2670  ++r2;
2671  } else if (r2->left() <= x1) {
2672  /*
2673  * Subtrahend precedes minuend: nuke left edge of minuend.
2674  */
2675  x1 = r2->right() + 1;
2676  if (x1 > r1->right()) {
2677  /*
2678  * Minuend completely covered: advance to next minuend and
2679  * reset left fence to edge of new minuend.
2680  */
2681  ++r1;
2682  if (r1 != r1End)
2683  x1 = r1->left();
2684  } else {
2685  // Subtrahend now used up since it doesn't extend beyond minuend
2686  ++r2;
2687  }
2688  } else if (r2->left() <= r1->right()) {
2689  /*
2690  * Left part of subtrahend covers part of minuend: add uncovered
2691  * part of minuend to region and skip to next subtrahend.
2692  */
2693  Q_ASSERT(x1 < r2->left());
2694  MEMCHECK(dest, pNextRect, dest.rects)
2695  pNextRect->setCoords(x1, y1, r2->left() - 1, y2);
2696  ++dest.numRects;
2697  ++pNextRect;
2698 
2699  x1 = r2->right() + 1;
2700  if (x1 > r1->right()) {
2701  /*
2702  * Minuend used up: advance to new...
2703  */
2704  ++r1;
2705  if (r1 != r1End)
2706  x1 = r1->left();
2707  } else {
2708  // Subtrahend used up
2709  ++r2;
2710  }
2711  } else {
2712  /*
2713  * Minuend used up: add any remaining piece before advancing.
2714  */
2715  if (r1->right() >= x1) {
2716  MEMCHECK(dest, pNextRect, dest.rects)
2717  pNextRect->setCoords(x1, y1, r1->right(), y2);
2718  ++dest.numRects;
2719  ++pNextRect;
2720  }
2721  ++r1;
2722  if (r1 != r1End)
2723  x1 = r1->left();
2724  }
2725  }
2726 
2727  /*
2728  * Add remaining minuend rectangles to region.
2729  */
2730  while (r1 != r1End) {
2731  Q_ASSERT(x1 <= r1->right());
2732  MEMCHECK(dest, pNextRect, dest.rects)
2733  pNextRect->setCoords(x1, y1, r1->right(), y2);
2734  ++dest.numRects;
2735  ++pNextRect;
2736 
2737  ++r1;
2738  if (r1 != r1End)
2739  x1 = r1->left();
2740  }
2741 }
2742 
2743 /*-
2744  *-----------------------------------------------------------------------
2745  * miSubtract --
2746  * Subtract regS from regM and leave the result in regD.
2747  * S stands for subtrahend, M for minuend and D for difference.
2748  *
2749  * Side Effects:
2750  * regD is overwritten.
2751  *
2752  *-----------------------------------------------------------------------
2753  */
2754 
2756  register QRegionPrivate &dest)
2757 {
2758  Q_ASSERT(!isEmptyHelper(regM));
2759  Q_ASSERT(!isEmptyHelper(regS));
2760  Q_ASSERT(EXTENTCHECK(&regM->extents, &regS->extents));
2761  Q_ASSERT(!regS->contains(*regM));
2762  Q_ASSERT(!EqualRegion(regM, regS));
2763 
2764  miRegionOp(dest, regM, regS, miSubtractO, miSubtractNonO1, 0);
2765 
2766  /*
2767  * Can't alter dest's extents before we call miRegionOp because
2768  * it might be one of the source regions and miRegionOp depends
2769  * on the extents of those regions being the unaltered. Besides, this
2770  * way there's no checking against rectangles that will be nuked
2771  * due to coalescing, so we have to examine fewer rectangles.
2772  */
2773  miSetExtents(dest);
2774 }
2775 
2777 {
2778  Q_ASSERT(!isEmptyHelper(sra) && !isEmptyHelper(srb));
2779  Q_ASSERT(EXTENTCHECK(&sra->extents, &srb->extents));
2780  Q_ASSERT(!EqualRegion(sra, srb));
2781 
2782  QRegionPrivate tra, trb;
2783 
2784  if (!srb->contains(*sra))
2785  SubtractRegion(sra, srb, tra);
2786  if (!sra->contains(*srb))
2787  SubtractRegion(srb, sra, trb);
2788 
2789  Q_ASSERT(isEmptyHelper(&trb) || !tra.contains(trb));
2790  Q_ASSERT(isEmptyHelper(&tra) || !trb.contains(tra));
2791 
2792  if (isEmptyHelper(&tra)) {
2793  dest = trb;
2794  } else if (isEmptyHelper(&trb)) {
2795  dest = tra;
2796  } else if (tra.canAppend(&trb)) {
2797  dest = tra;
2798  dest.append(&trb);
2799  } else if (trb.canAppend(&tra)) {
2800  dest = trb;
2801  dest.append(&tra);
2802  } else {
2803  UnionRegion(&tra, &trb, dest);
2804  }
2805 }
2806 
2807 /*
2808  * Check to see if two regions are equal
2809  */
2810 static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2)
2811 {
2812  if (r1->numRects != r2->numRects) {
2813  return false;
2814  } else if (r1->numRects == 0) {
2815  return true;
2816  } else if (r1->extents != r2->extents) {
2817  return false;
2818  } else if (r1->numRects == 1 && r2->numRects == 1) {
2819  return true; // equality tested in previous if-statement
2820  } else {
2821  const QRect *rr1 = (r1->numRects == 1) ? &r1->extents : r1->rects.constData();
2822  const QRect *rr2 = (r2->numRects == 1) ? &r2->extents : r2->rects.constData();
2823  for (int i = 0; i < r1->numRects; ++i, ++rr1, ++rr2) {
2824  if (*rr1 != *rr2)
2825  return false;
2826  }
2827  }
2828 
2829  return true;
2830 }
2831 
2832 static bool PointInRegion(QRegionPrivate *pRegion, int x, int y)
2833 {
2834  int i;
2835 
2836  if (isEmptyHelper(pRegion))
2837  return false;
2838  if (!pRegion->extents.contains(x, y))
2839  return false;
2840  if (pRegion->numRects == 1)
2841  return pRegion->extents.contains(x, y);
2842  if (pRegion->innerRect.contains(x, y))
2843  return true;
2844  for (i = 0; i < pRegion->numRects; ++i) {
2845  if (pRegion->rects[i].contains(x, y))
2846  return true;
2847  }
2848  return false;
2849 }
2850 
2851 static bool RectInRegion(register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
2852 {
2853  register const QRect *pbox;
2854  register const QRect *pboxEnd;
2855  QRect rect(rx, ry, rwidth, rheight);
2856  register QRect *prect = &rect;
2857  int partIn, partOut;
2858 
2859  if (!region || region->numRects == 0 || !EXTENTCHECK(&region->extents, prect))
2860  return RectangleOut;
2861 
2862  partOut = false;
2863  partIn = false;
2864 
2865  /* can stop when both partOut and partIn are true, or we reach prect->y2 */
2866  pbox = (region->numRects == 1) ? &region->extents : region->rects.constData();
2867  pboxEnd = pbox + region->numRects;
2868  for (; pbox < pboxEnd; ++pbox) {
2869  if (pbox->bottom() < ry)
2870  continue;
2871 
2872  if (pbox->top() > ry) {
2873  partOut = true;
2874  if (partIn || pbox->top() > prect->bottom())
2875  break;
2876  ry = pbox->top();
2877  }
2878 
2879  if (pbox->right() < rx)
2880  continue; /* not far enough over yet */
2881 
2882  if (pbox->left() > rx) {
2883  partOut = true; /* missed part of rectangle to left */
2884  if (partIn)
2885  break;
2886  }
2887 
2888  if (pbox->left() <= prect->right()) {
2889  partIn = true; /* definitely overlap */
2890  if (partOut)
2891  break;
2892  }
2893 
2894  if (pbox->right() >= prect->right()) {
2895  ry = pbox->bottom() + 1; /* finished with this band */
2896  if (ry > prect->bottom())
2897  break;
2898  rx = prect->left(); /* reset x out to left again */
2899  } else {
2900  /*
2901  * Because boxes in a band are maximal width, if the first box
2902  * to overlap the rectangle doesn't completely cover it in that
2903  * band, the rectangle must be partially out, since some of it
2904  * will be uncovered in that band. partIn will have been set true
2905  * by now...
2906  */
2907  break;
2908  }
2909  }
2910  return partIn ? ((ry <= prect->bottom()) ? RectanglePart : RectangleIn) : RectangleOut;
2911 }
2912 // END OF Region.c extract
2913 // START OF poly.h extract
2914 /* $XConsortium: poly.h,v 1.4 94/04/17 20:22:19 rws Exp $ */
2915 /************************************************************************
2916 
2917 Copyright (c) 1987 X Consortium
2918 
2919 Permission is hereby granted, free of charge, to any person obtaining a copy
2920 of this software and associated documentation files (the "Software"), to deal
2921 in the Software without restriction, including without limitation the rights
2922 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
2923 copies of the Software, and to permit persons to whom the Software is
2924 furnished to do so, subject to the following conditions:
2925 
2926 The above copyright notice and this permission notice shall be included in
2927 all copies or substantial portions of the Software.
2928 
2929 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
2930 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
2931 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
2932 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
2933 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
2934 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
2935 
2936 Except as contained in this notice, the name of the X Consortium shall not be
2937 used in advertising or otherwise to promote the sale, use or other dealings
2938 in this Software without prior written authorization from the X Consortium.
2939 
2940 
2941 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
2942 
2943  All Rights Reserved
2944 
2945 Permission to use, copy, modify, and distribute this software and its
2946 documentation for any purpose and without fee is hereby granted,
2947 provided that the above copyright notice appear in all copies and that
2948 both that copyright notice and this permission notice appear in
2949 supporting documentation, and that the name of Digital not be
2950 used in advertising or publicity pertaining to distribution of the
2951 software without specific, written prior permission.
2952 
2953 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
2954 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
2955 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
2956 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
2957 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
2958 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
2959 SOFTWARE.
2960 
2961 ************************************************************************/
2962 
2963 /*
2964  * This file contains a few macros to help track
2965  * the edge of a filled object. The object is assumed
2966  * to be filled in scanline order, and thus the
2967  * algorithm used is an extension of Bresenham's line
2968  * drawing algorithm which assumes that y is always the
2969  * major axis.
2970  * Since these pieces of code are the same for any filled shape,
2971  * it is more convenient to gather the library in one
2972  * place, but since these pieces of code are also in
2973  * the inner loops of output primitives, procedure call
2974  * overhead is out of the question.
2975  * See the author for a derivation if needed.
2976  */
2977 
2978 
2979 /*
2980  * In scan converting polygons, we want to choose those pixels
2981  * which are inside the polygon. Thus, we add .5 to the starting
2982  * x coordinate for both left and right edges. Now we choose the
2983  * first pixel which is inside the pgon for the left edge and the
2984  * first pixel which is outside the pgon for the right edge.
2985  * Draw the left pixel, but not the right.
2986  *
2987  * How to add .5 to the starting x coordinate:
2988  * If the edge is moving to the right, then subtract dy from the
2989  * error term from the general form of the algorithm.
2990  * If the edge is moving to the left, then add dy to the error term.
2991  *
2992  * The reason for the difference between edges moving to the left
2993  * and edges moving to the right is simple: If an edge is moving
2994  * to the right, then we want the algorithm to flip immediately.
2995  * If it is moving to the left, then we don't want it to flip until
2996  * we traverse an entire pixel.
2997  */
2998 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
2999  int dx; /* local storage */ \
3000 \
3001  /* \
3002  * if the edge is horizontal, then it is ignored \
3003  * and assumed not to be processed. Otherwise, do this stuff. \
3004  */ \
3005  if ((dy) != 0) { \
3006  xStart = (x1); \
3007  dx = (x2) - xStart; \
3008  if (dx < 0) { \
3009  m = dx / (dy); \
3010  m1 = m - 1; \
3011  incr1 = -2 * dx + 2 * (dy) * m1; \
3012  incr2 = -2 * dx + 2 * (dy) * m; \
3013  d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
3014  } else { \
3015  m = dx / (dy); \
3016  m1 = m + 1; \
3017  incr1 = 2 * dx - 2 * (dy) * m1; \
3018  incr2 = 2 * dx - 2 * (dy) * m; \
3019  d = -2 * m * (dy) + 2 * dx; \
3020  } \
3021  } \
3022 }
3023 
3024 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
3025  if (m1 > 0) { \
3026  if (d > 0) { \
3027  minval += m1; \
3028  d += incr1; \
3029  } \
3030  else { \
3031  minval += m; \
3032  d += incr2; \
3033  } \
3034  } else {\
3035  if (d >= 0) { \
3036  minval += m1; \
3037  d += incr1; \
3038  } \
3039  else { \
3040  minval += m; \
3041  d += incr2; \
3042  } \
3043  } \
3044 }
3045 
3046 
3047 /*
3048  * This structure contains all of the information needed
3049  * to run the bresenham algorithm.
3050  * The variables may be hardcoded into the declarations
3051  * instead of using this structure to make use of
3052  * register declarations.
3053  */
3054 typedef struct {
3055  int minor_axis; /* minor axis */
3056  int d; /* decision variable */
3057  int m, m1; /* slope and slope+1 */
3058  int incr1, incr2; /* error increments */
3059 } BRESINFO;
3060 
3061 
3062 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
3063  BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
3064  bres.m, bres.m1, bres.incr1, bres.incr2)
3065 
3066 #define BRESINCRPGONSTRUCT(bres) \
3067  BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
3068 
3069 
3070 
3071 /*
3072  * These are the data structures needed to scan
3073  * convert regions. Two different scan conversion
3074  * methods are available -- the even-odd method, and
3075  * the winding number method.
3076  * The even-odd rule states that a point is inside
3077  * the polygon if a ray drawn from that point in any
3078  * direction will pass through an odd number of
3079  * path segments.
3080  * By the winding number rule, a point is decided
3081  * to be inside the polygon if a ray drawn from that
3082  * point in any direction passes through a different
3083  * number of clockwise and counter-clockwise path
3084  * segments.
3085  *
3086  * These data structures are adapted somewhat from
3087  * the algorithm in (Foley/Van Dam) for scan converting
3088  * polygons.
3089  * The basic algorithm is to start at the top (smallest y)
3090  * of the polygon, stepping down to the bottom of
3091  * the polygon by incrementing the y coordinate. We
3092  * keep a list of edges which the current scanline crosses,
3093  * sorted by x. This list is called the Active Edge Table (AET)
3094  * As we change the y-coordinate, we update each entry in
3095  * in the active edge table to reflect the edges new xcoord.
3096  * This list must be sorted at each scanline in case
3097  * two edges intersect.
3098  * We also keep a data structure known as the Edge Table (ET),
3099  * which keeps track of all the edges which the current
3100  * scanline has not yet reached. The ET is basically a
3101  * list of ScanLineList structures containing a list of
3102  * edges which are entered at a given scanline. There is one
3103  * ScanLineList per scanline at which an edge is entered.
3104  * When we enter a new edge, we move it from the ET to the AET.
3105  *
3106  * From the AET, we can implement the even-odd rule as in
3107  * (Foley/Van Dam).
3108  * The winding number rule is a little trickier. We also
3109  * keep the EdgeTableEntries in the AET linked by the
3110  * nextWETE (winding EdgeTableEntry) link. This allows
3111  * the edges to be linked just as before for updating
3112  * purposes, but only uses the edges linked by the nextWETE
3113  * link as edges representing spans of the polygon to
3114  * drawn (as with the even-odd rule).
3115  */
3116 
3117 /*
3118  * for the winding number rule
3119  */
3120 #define CLOCKWISE 1
3121 #define COUNTERCLOCKWISE -1
3122 
3123 typedef struct _EdgeTableEntry {
3124  int ymax; /* ycoord at which we exit this edge. */
3125  BRESINFO bres; /* Bresenham info to run the edge */
3126  struct _EdgeTableEntry *next; /* next in the list */
3127  struct _EdgeTableEntry *back; /* for insertion sort */
3128  struct _EdgeTableEntry *nextWETE; /* for winding num rule */
3129  int ClockWise; /* flag for winding number rule */
3130 } EdgeTableEntry;
3131 
3132 
3133 typedef struct _ScanLineList{
3134  int scanline; /* the scanline represented */
3135  EdgeTableEntry *edgelist; /* header node */
3136  struct _ScanLineList *next; /* next in the list */
3137 } ScanLineList;
3138 
3139 
3140 typedef struct {
3141  int ymax; /* ymax for the polygon */
3142  int ymin; /* ymin for the polygon */
3143  ScanLineList scanlines; /* header node */
3144 } EdgeTable;
3145 
3146 
3147 /*
3148  * Here is a struct to help with storage allocation
3149  * so we can allocate a big chunk at a time, and then take
3150  * pieces from this heap when we need to.
3151  */
3152 #define SLLSPERBLOCK 25
3153 
3154 typedef struct _ScanLineListBlock {
3158 
3159 
3160 
3161 /*
3162  *
3163  * a few macros for the inner loops of the fill code where
3164  * performance considerations don't allow a procedure call.
3165  *
3166  * Evaluate the given edge at the given scanline.
3167  * If the edge has expired, then we leave it and fix up
3168  * the active edge table; otherwise, we increment the
3169  * x value to be ready for the next scanline.
3170  * The winding number rule is in effect, so we must notify
3171  * the caller when the edge has been removed so he
3172  * can reorder the Winding Active Edge Table.
3173  */
3174 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
3175  if (pAET->ymax == y) { /* leaving this edge */ \
3176  pPrevAET->next = pAET->next; \
3177  pAET = pPrevAET->next; \
3178  fixWAET = 1; \
3179  if (pAET) \
3180  pAET->back = pPrevAET; \
3181  } \
3182  else { \
3183  BRESINCRPGONSTRUCT(pAET->bres) \
3184  pPrevAET = pAET; \
3185  pAET = pAET->next; \
3186  } \
3187 }
3188 
3189 
3190 /*
3191  * Evaluate the given edge at the given scanline.
3192  * If the edge has expired, then we leave it and fix up
3193  * the active edge table; otherwise, we increment the
3194  * x value to be ready for the next scanline.
3195  * The even-odd rule is in effect.
3196  */
3197 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
3198  if (pAET->ymax == y) { /* leaving this edge */ \
3199  pPrevAET->next = pAET->next; \
3200  pAET = pPrevAET->next; \
3201  if (pAET) \
3202  pAET->back = pPrevAET; \
3203  } \
3204  else { \
3205  BRESINCRPGONSTRUCT(pAET->bres) \
3206  pPrevAET = pAET; \
3207  pAET = pAET->next; \
3208  } \
3209 }
3210 // END OF poly.h extract
3211 // START OF PolyReg.c extract
3212 /* $XConsortium: PolyReg.c,v 11.23 94/11/17 21:59:37 converse Exp $ */
3213 /************************************************************************
3214 
3215 Copyright (c) 1987 X Consortium
3216 
3217 Permission is hereby granted, free of charge, to any person obtaining a copy
3218 of this software and associated documentation files (the "Software"), to deal
3219 in the Software without restriction, including without limitation the rights
3220 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
3221 copies of the Software, and to permit persons to whom the Software is
3222 furnished to do so, subject to the following conditions:
3223 
3224 The above copyright notice and this permission notice shall be included in
3225 all copies or substantial portions of the Software.
3226 
3227 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
3228 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
3229 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
3230 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
3231 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
3232 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
3233 
3234 Except as contained in this notice, the name of the X Consortium shall not be
3235 used in advertising or otherwise to promote the sale, use or other dealings
3236 in this Software without prior written authorization from the X Consortium.
3237 
3238 
3239 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
3240 
3241  All Rights Reserved
3242 
3243 Permission to use, copy, modify, and distribute this software and its
3244 documentation for any purpose and without fee is hereby granted,
3245 provided that the above copyright notice appear in all copies and that
3246 both that copyright notice and this permission notice appear in
3247 supporting documentation, and that the name of Digital not be
3248 used in advertising or publicity pertaining to distribution of the
3249 software without specific, written prior permission.
3250 
3251 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
3252 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
3253 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
3254 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
3255 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
3256 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
3257 SOFTWARE.
3258 
3259 ************************************************************************/
3260 /* $XFree86: xc/lib/X11/PolyReg.c,v 1.1.1.2.8.2 1998/10/04 15:22:49 hohndel Exp $ */
3261 
3262 #define LARGE_COORDINATE INT_MAX
3263 #define SMALL_COORDINATE INT_MIN
3264 
3265 /*
3266  * InsertEdgeInET
3267  *
3268  * Insert the given edge into the edge table.
3269  * First we must find the correct bucket in the
3270  * Edge table, then find the right slot in the
3271  * bucket. Finally, we can insert it.
3272  *
3273  */
3274 static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline,
3275  ScanLineListBlock **SLLBlock, int *iSLLBlock)
3276 {
3277  register EdgeTableEntry *start, *prev;
3278  register ScanLineList *pSLL, *pPrevSLL;
3279  ScanLineListBlock *tmpSLLBlock;
3280 
3281  /*
3282  * find the right bucket to put the edge into
3283  */
3284  pPrevSLL = &ET->scanlines;
3285  pSLL = pPrevSLL->next;
3286  while (pSLL && (pSLL->scanline < scanline)) {
3287  pPrevSLL = pSLL;
3288  pSLL = pSLL->next;
3289  }
3290 
3291  /*
3292  * reassign pSLL (pointer to ScanLineList) if necessary
3293  */
3294  if ((!pSLL) || (pSLL->scanline > scanline)) {
3295  if (*iSLLBlock > SLLSPERBLOCK-1)
3296  {
3297  tmpSLLBlock =
3298  (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
3299  Q_CHECK_PTR(tmpSLLBlock);
3300  (*SLLBlock)->next = tmpSLLBlock;
3301  tmpSLLBlock->next = (ScanLineListBlock *)NULL;
3302  *SLLBlock = tmpSLLBlock;
3303  *iSLLBlock = 0;
3304  }
3305  pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
3306 
3307  pSLL->next = pPrevSLL->next;
3308  pSLL->edgelist = (EdgeTableEntry *)NULL;
3309  pPrevSLL->next = pSLL;
3310  }
3311  pSLL->scanline = scanline;
3312 
3313  /*
3314  * now insert the edge in the right bucket
3315  */
3316  prev = 0;
3317  start = pSLL->edgelist;
3318  while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) {
3319  prev = start;
3320  start = start->next;
3321  }
3322  ETE->next = start;
3323 
3324  if (prev)
3325  prev->next = ETE;
3326  else
3327  pSLL->edgelist = ETE;
3328 }
3329 
3330 /*
3331  * CreateEdgeTable
3332  *
3333  * This routine creates the edge table for
3334  * scan converting polygons.
3335  * The Edge Table (ET) looks like:
3336  *
3337  * EdgeTable
3338  * --------
3339  * | ymax | ScanLineLists
3340  * |scanline|-->------------>-------------->...
3341  * -------- |scanline| |scanline|
3342  * |edgelist| |edgelist|
3343  * --------- ---------
3344  * | |
3345  * | |
3346  * V V
3347  * list of ETEs list of ETEs
3348  *
3349  * where ETE is an EdgeTableEntry data structure,
3350  * and there is one ScanLineList per scanline at
3351  * which an edge is initially entered.
3352  *
3353  */
3354 
3355 static void CreateETandAET(register int count, register const QPoint *pts,
3356  EdgeTable *ET, EdgeTableEntry *AET, register EdgeTableEntry *pETEs,
3357  ScanLineListBlock *pSLLBlock)
3358 {
3359  register const QPoint *top,
3360  *bottom,
3361  *PrevPt,
3362  *CurrPt;
3363  int iSLLBlock = 0;
3364  int dy;
3365 
3366  if (count < 2)
3367  return;
3368 
3369  /*
3370  * initialize the Active Edge Table
3371  */
3372  AET->next = 0;
3373  AET->back = 0;
3374  AET->nextWETE = 0;
3376 
3377  /*
3378  * initialize the Edge Table.
3379  */
3380  ET->scanlines.next = 0;
3381  ET->ymax = SMALL_COORDINATE;
3382  ET->ymin = LARGE_COORDINATE;
3383  pSLLBlock->next = 0;
3384 
3385  PrevPt = &pts[count - 1];
3386 
3387  /*
3388  * for each vertex in the array of points.
3389  * In this loop we are dealing with two vertices at
3390  * a time -- these make up one edge of the polygon.
3391  */
3392  while (count--) {
3393  CurrPt = pts++;
3394 
3395  /*
3396  * find out which point is above and which is below.
3397  */
3398  if (PrevPt->y() > CurrPt->y()) {
3399  bottom = PrevPt;
3400  top = CurrPt;
3401  pETEs->ClockWise = 0;
3402  } else {
3403  bottom = CurrPt;
3404  top = PrevPt;
3405  pETEs->ClockWise = 1;
3406  }
3407 
3408  /*
3409  * don't add horizontal edges to the Edge table.
3410  */
3411  if (bottom->y() != top->y()) {
3412  pETEs->ymax = bottom->y() - 1; /* -1 so we don't get last scanline */
3413 
3414  /*
3415  * initialize integer edge algorithm
3416  */
3417  dy = bottom->y() - top->y();
3418  BRESINITPGONSTRUCT(dy, top->x(), bottom->x(), pETEs->bres)
3419 
3420  InsertEdgeInET(ET, pETEs, top->y(), &pSLLBlock, &iSLLBlock);
3421 
3422  if (PrevPt->y() > ET->ymax)
3423  ET->ymax = PrevPt->y();
3424  if (PrevPt->y() < ET->ymin)
3425  ET->ymin = PrevPt->y();
3426  ++pETEs;
3427  }
3428 
3429  PrevPt = CurrPt;
3430  }
3431 }
3432 
3433 /*
3434  * loadAET
3435  *
3436  * This routine moves EdgeTableEntries from the
3437  * EdgeTable into the Active Edge Table,
3438  * leaving them sorted by smaller x coordinate.
3439  *
3440  */
3441 
3442 static void loadAET(register EdgeTableEntry *AET, register EdgeTableEntry *ETEs)
3443 {
3444  register EdgeTableEntry *pPrevAET;
3445  register EdgeTableEntry *tmp;
3446 
3447  pPrevAET = AET;
3448  AET = AET->next;
3449  while (ETEs) {
3450  while (AET && AET->bres.minor_axis < ETEs->bres.minor_axis) {
3451  pPrevAET = AET;
3452  AET = AET->next;
3453  }
3454  tmp = ETEs->next;
3455  ETEs->next = AET;
3456  if (AET)
3457  AET->back = ETEs;
3458  ETEs->back = pPrevAET;
3459  pPrevAET->next = ETEs;
3460  pPrevAET = ETEs;
3461 
3462  ETEs = tmp;
3463  }
3464 }
3465 
3466 /*
3467  * computeWAET
3468  *
3469  * This routine links the AET by the
3470  * nextWETE (winding EdgeTableEntry) link for
3471  * use by the winding number rule. The final
3472  * Active Edge Table (AET) might look something
3473  * like:
3474  *
3475  * AET
3476  * ---------- --------- ---------
3477  * |ymax | |ymax | |ymax |
3478  * | ... | |... | |... |
3479  * |next |->|next |->|next |->...
3480  * |nextWETE| |nextWETE| |nextWETE|
3481  * --------- --------- ^--------
3482  * | | |
3483  * V-------------------> V---> ...
3484  *
3485  */
3486 static void computeWAET(register EdgeTableEntry *AET)
3487 {
3488  register EdgeTableEntry *pWETE;
3489  register int inside = 1;
3490  register int isInside = 0;
3491 
3492  AET->nextWETE = 0;
3493  pWETE = AET;
3494  AET = AET->next;
3495  while (AET) {
3496  if (AET->ClockWise)
3497  ++isInside;
3498  else
3499  --isInside;
3500 
3501  if ((!inside && !isInside) || (inside && isInside)) {
3502  pWETE->nextWETE = AET;
3503  pWETE = AET;
3504  inside = !inside;
3505  }
3506  AET = AET->next;
3507  }
3508  pWETE->nextWETE = 0;
3509 }
3510 
3511 /*
3512  * InsertionSort
3513  *
3514  * Just a simple insertion sort using
3515  * pointers and back pointers to sort the Active
3516  * Edge Table.
3517  *
3518  */
3519 
3520 static int InsertionSort(register EdgeTableEntry *AET)
3521 {
3522  register EdgeTableEntry *pETEchase;
3523  register EdgeTableEntry *pETEinsert;
3524  register EdgeTableEntry *pETEchaseBackTMP;
3525  register int changed = 0;
3526 
3527  AET = AET->next;
3528  while (AET) {
3529  pETEinsert = AET;
3530  pETEchase = AET;
3531  while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
3532  pETEchase = pETEchase->back;
3533 
3534  AET = AET->next;
3535  if (pETEchase != pETEinsert) {
3536  pETEchaseBackTMP = pETEchase->back;
3537  pETEinsert->back->next = AET;
3538  if (AET)
3539  AET->back = pETEinsert->back;
3540  pETEinsert->next = pETEchase;
3541  pETEchase->back->next = pETEinsert;
3542  pETEchase->back = pETEinsert;
3543  pETEinsert->back = pETEchaseBackTMP;
3544  changed = 1;
3545  }
3546  }
3547  return changed;
3548 }
3549 
3550 /*
3551  * Clean up our act.
3552  */
3553 static void FreeStorage(register ScanLineListBlock *pSLLBlock)
3554 {
3555  register ScanLineListBlock *tmpSLLBlock;
3556 
3557  while (pSLLBlock) {
3558  tmpSLLBlock = pSLLBlock->next;
3559  free(pSLLBlock);
3560  pSLLBlock = tmpSLLBlock;
3561  }
3562 }
3563 
3564 struct QRegionSpan {
3566  QRegionSpan(int x1_, int x2_) : x1(x1_), x2(x2_) {}
3567 
3568  int x1;
3569  int x2;
3570  int width() const { return x2 - x1; }
3571 };
3572 
3574 
3575 static inline void flushRow(const QRegionSpan *spans, int y, int numSpans, QRegionPrivate *reg, int *lastRow, int *extendTo, bool *needsExtend)
3576 {
3577  QRect *regRects = reg->rects.data() + *lastRow;
3578  bool canExtend = reg->rects.size() - *lastRow == numSpans
3579  && !(*needsExtend && *extendTo + 1 != y)
3580  && (*needsExtend || regRects[0].y() + regRects[0].height() == y);
3581 
3582  for (int i = 0; i < numSpans && canExtend; ++i) {
3583  if (regRects[i].x() != spans[i].x1 || regRects[i].right() != spans[i].x2 - 1)
3584  canExtend = false;
3585  }
3586 
3587  if (canExtend) {
3588  *extendTo = y;
3589  *needsExtend = true;
3590  } else {
3591  if (*needsExtend) {
3592  for (int i = 0; i < reg->rects.size() - *lastRow; ++i)
3593  regRects[i].setBottom(*extendTo);
3594  }
3595 
3596  *lastRow = reg->rects.size();
3597  reg->rects.reserve(*lastRow + numSpans);
3598  for (int i = 0; i < numSpans; ++i)
3599  reg->rects << QRect(spans[i].x1, y, spans[i].width(), 1);
3600 
3601  if (spans[0].x1 < reg->extents.left())
3602  reg->extents.setLeft(spans[0].x1);
3603 
3604  if (spans[numSpans-1].x2 - 1 > reg->extents.right())
3605  reg->extents.setRight(spans[numSpans-1].x2 - 1);
3606 
3607  *needsExtend = false;
3608  }
3609 }
3610 
3611 /*
3612  * Create an array of rectangles from a list of points.
3613  * If indeed these things (POINTS, RECTS) are the same,
3614  * then this proc is still needed, because it allocates
3615  * storage for the array, which was allocated on the
3616  * stack by the calling procedure.
3617  *
3618  */
3619 static void PtsToRegion(register int numFullPtBlocks, register int iCurPtBlock,
3620  POINTBLOCK *FirstPtBlock, QRegionPrivate *reg)
3621 {
3622  int lastRow = 0;
3623  int extendTo = 0;
3624  bool needsExtend = false;
3626  int rowSize = 0;
3627 
3628  reg->extents.setLeft(INT_MAX);
3629  reg->extents.setRight(INT_MIN);
3630  reg->innerArea = -1;
3631 
3632  POINTBLOCK *CurPtBlock = FirstPtBlock;
3633  for (; numFullPtBlocks >= 0; --numFullPtBlocks) {
3634  /* the loop uses 2 points per iteration */
3635  int i = NUMPTSTOBUFFER >> 1;
3636  if (!numFullPtBlocks)
3637  i = iCurPtBlock >> 1;
3638  if(i) {
3639  row.resize(qMax(row.size(), rowSize + i));
3640  for (QPoint *pts = CurPtBlock->pts; i--; pts += 2) {
3641  const int width = pts[1].x() - pts[0].x();
3642  if (width) {
3643  if (rowSize && row[rowSize-1].x2 == pts[0].x())
3644  row[rowSize-1].x2 = pts[1].x();
3645  else
3646  row[rowSize++] = QRegionSpan(pts[0].x(), pts[1].x());
3647  }
3648 
3649  if (rowSize) {
3650  QPoint *next = i ? &pts[2] : (numFullPtBlocks ? CurPtBlock->next->pts : 0);
3651 
3652  if (!next || next->y() != pts[0].y()) {
3653  flushRow(row.data(), pts[0].y(), rowSize, reg, &lastRow, &extendTo, &needsExtend);
3654  rowSize = 0;
3655  }
3656  }
3657  }
3658  }
3659  CurPtBlock = CurPtBlock->next;
3660  }
3661 
3662  if (needsExtend) {
3663  for (int i = lastRow; i < reg->rects.size(); ++i)
3664  reg->rects[i].setBottom(extendTo);
3665  }
3666 
3667  reg->numRects = reg->rects.size();
3668 
3669  if (reg->numRects) {
3670  reg->extents.setTop(reg->rects[0].top());
3671  reg->extents.setBottom(reg->rects[lastRow].bottom());
3672 
3673  for (int i = 0; i < reg->rects.size(); ++i)
3674  reg->updateInnerRect(reg->rects[i]);
3675  } else {
3676  reg->extents.setCoords(0, 0, 0, 0);
3677  }
3678 }
3679 
3680 /*
3681  * polytoregion
3682  *
3683  * Scan converts a polygon by returning a run-length
3684  * encoding of the resultant bitmap -- the run-length
3685  * encoding is in the form of an array of rectangles.
3686  *
3687  * Can return 0 in case of errors.
3688  */
3689 static QRegionPrivate *PolygonRegion(const QPoint *Pts, int Count, int rule)
3690  //Point *Pts; /* the pts */
3691  //int Count; /* number of pts */
3692  //int rule; /* winding rule */
3693 {
3694  QRegionPrivate *region;
3695  register EdgeTableEntry *pAET; /* Active Edge Table */
3696  register int y; /* current scanline */
3697  register int iPts = 0; /* number of pts in buffer */
3698  register EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
3699  register ScanLineList *pSLL; /* current scanLineList */
3700  register QPoint *pts; /* output buffer */
3701  EdgeTableEntry *pPrevAET; /* ptr to previous AET */
3702  EdgeTable ET; /* header node for ET */
3703  EdgeTableEntry AET; /* header node for AET */
3704  EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
3705  ScanLineListBlock SLLBlock; /* header for scanlinelist */
3706  int fixWAET = false;
3707  POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
3708  FirstPtBlock.pts = reinterpret_cast<QPoint *>(FirstPtBlock.data);
3709  POINTBLOCK *tmpPtBlock;
3710  int numFullPtBlocks = 0;
3711 
3712  if (!(region = new QRegionPrivate))
3713  return 0;
3714 
3715  /* special case a rectangle */
3716  if (((Count == 4) ||
3717  ((Count == 5) && (Pts[4].x() == Pts[0].x()) && (Pts[4].y() == Pts[0].y())))
3718  && (((Pts[0].y() == Pts[1].y()) && (Pts[1].x() == Pts[2].x()) && (Pts[2].y() == Pts[3].y())
3719  && (Pts[3].x() == Pts[0].x())) || ((Pts[0].x() == Pts[1].x())
3720  && (Pts[1].y() == Pts[2].y()) && (Pts[2].x() == Pts[3].x())
3721  && (Pts[3].y() == Pts[0].y())))) {
3722  int x = qMin(Pts[0].x(), Pts[2].x());
3723  region->extents.setLeft(x);
3724  int y = qMin(Pts[0].y(), Pts[2].y());
3725  region->extents.setTop(y);
3726  region->extents.setWidth(qMax(Pts[0].x(), Pts[2].x()) - x);
3727  region->extents.setHeight(qMax(Pts[0].y(), Pts[2].y()) - y);
3728  if ((region->extents.left() <= region->extents.right()) &&
3729  (region->extents.top() <= region->extents.bottom())) {
3730  region->numRects = 1;
3731  region->innerRect = region->extents;
3732  region->innerArea = region->innerRect.width() * region->innerRect.height();
3733  }
3734  return region;
3735  }
3736 
3737  if (!(pETEs = static_cast<EdgeTableEntry *>(malloc(sizeof(EdgeTableEntry) * Count))))
3738  return 0;
3739 
3740  region->vectorize();
3741 
3742  pts = FirstPtBlock.pts;
3743  CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
3744 
3745  pSLL = ET.scanlines.next;
3746  curPtBlock = &FirstPtBlock;
3747 
3748  // sanity check that the region won't become too big...
3749  if (ET.ymax - ET.ymin > 100000) {
3750  // clean up region ptr
3751 #ifndef QT_NO_DEBUG
3752  qWarning("QRegion: creating region from big polygon failed...!");
3753 #endif
3754  delete region;
3755  return 0;
3756  }
3757 
3758 
3759  QT_TRY {
3760  if (rule == EvenOddRule) {
3761  /*
3762  * for each scanline
3763  */
3764  for (y = ET.ymin; y < ET.ymax; ++y) {
3765 
3766  /*
3767  * Add a new edge to the active edge table when we
3768  * get to the next edge.
3769  */
3770  if (pSLL && y == pSLL->scanline) {
3771  loadAET(&AET, pSLL->edgelist);
3772  pSLL = pSLL->next;
3773  }
3774  pPrevAET = &AET;
3775  pAET = AET.next;
3776 
3777  /*
3778  * for each active edge
3779  */
3780  while (pAET) {
3781  pts->setX(pAET->bres.minor_axis);
3782  pts->setY(y);
3783  ++pts;
3784  ++iPts;
3785 
3786  /*
3787  * send out the buffer
3788  */
3789  if (iPts == NUMPTSTOBUFFER) {
3790  tmpPtBlock = (POINTBLOCK *)malloc(sizeof(POINTBLOCK));
3791  Q_CHECK_PTR(tmpPtBlock);
3792  tmpPtBlock->pts = reinterpret_cast<QPoint *>(tmpPtBlock->data);
3793  curPtBlock->next = tmpPtBlock;
3794  curPtBlock = tmpPtBlock;
3795  pts = curPtBlock->pts;
3796  ++numFullPtBlocks;
3797  iPts = 0;
3798  }
3799  EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
3800  }
3801  InsertionSort(&AET);
3802  }
3803  } else {
3804  /*
3805  * for each scanline
3806  */
3807  for (y = ET.ymin; y < ET.ymax; ++y) {
3808  /*
3809  * Add a new edge to the active edge table when we
3810  * get to the next edge.
3811  */
3812  if (pSLL && y == pSLL->scanline) {
3813  loadAET(&AET, pSLL->edgelist);
3814  computeWAET(&AET);
3815  pSLL = pSLL->next;
3816  }
3817  pPrevAET = &AET;
3818  pAET = AET.next;
3819  pWETE = pAET;
3820 
3821  /*
3822  * for each active edge
3823  */
3824  while (pAET) {
3825  /*
3826  * add to the buffer only those edges that
3827  * are in the Winding active edge table.
3828  */
3829  if (pWETE == pAET) {
3830  pts->setX(pAET->bres.minor_axis);
3831  pts->setY(y);
3832  ++pts;
3833  ++iPts;
3834 
3835  /*
3836  * send out the buffer
3837  */
3838  if (iPts == NUMPTSTOBUFFER) {
3839  tmpPtBlock = static_cast<POINTBLOCK *>(malloc(sizeof(POINTBLOCK)));
3840  tmpPtBlock->pts = reinterpret_cast<QPoint *>(tmpPtBlock->data);
3841  curPtBlock->next = tmpPtBlock;
3842  curPtBlock = tmpPtBlock;
3843  pts = curPtBlock->pts;
3844  ++numFullPtBlocks;
3845  iPts = 0;
3846  }
3847  pWETE = pWETE->nextWETE;
3848  }
3849  EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
3850  }
3851 
3852  /*
3853  * recompute the winding active edge table if
3854  * we just resorted or have exited an edge.
3855  */
3856  if (InsertionSort(&AET) || fixWAET) {
3857  computeWAET(&AET);
3858  fixWAET = false;
3859  }
3860  }
3861  }
3862  } QT_CATCH(...) {
3863  FreeStorage(SLLBlock.next);
3864  PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
3865  for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
3866  tmpPtBlock = curPtBlock->next;
3867  free(curPtBlock);
3868  curPtBlock = tmpPtBlock;
3869  }
3870  free(pETEs);
3871  return 0; // this function returns 0 in case of an error
3872  }
3873 
3874  FreeStorage(SLLBlock.next);
3875  PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
3876  for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
3877  tmpPtBlock = curPtBlock->next;
3878  free(curPtBlock);
3879  curPtBlock = tmpPtBlock;
3880  }
3881  free(pETEs);
3882  return region;
3883 }
3884 // END OF PolyReg.c extract
3885 
3887 {
3888  QImage image = bitmap.toImage();
3889 
3890  QRegionPrivate *region = new QRegionPrivate;
3891 
3892  QRect xr;
3893 
3894 #define AddSpan \
3895  { \
3896  xr.setCoords(prev1, y, x-1, y); \
3897  UnionRectWithRegion(&xr, region, *region); \
3898  }
3899 
3900  const uchar zero = 0;
3901  bool little = image.format() == QImage::Format_MonoLSB;
3902 
3903  int x,
3904  y;
3905  for (y = 0; y < image.height(); ++y) {
3906  uchar *line = image.scanLine(y);
3907  int w = image.width();
3908  uchar all = zero;
3909  int prev1 = -1;
3910  for (x = 0; x < w;) {
3911  uchar byte = line[x / 8];
3912  if (x > w - 8 || byte!=all) {
3913  if (little) {
3914  for (int b = 8; b > 0 && x < w; --b) {
3915  if (!(byte & 0x01) == !all) {
3916  // More of the same
3917  } else {
3918  // A change.
3919  if (all!=zero) {
3920  AddSpan
3921  all = zero;
3922  } else {
3923  prev1 = x;
3924  all = ~zero;
3925  }
3926  }
3927  byte >>= 1;
3928  ++x;
3929  }
3930  } else {
3931  for (int b = 8; b > 0 && x < w; --b) {
3932  if (!(byte & 0x80) == !all) {
3933  // More of the same
3934  } else {
3935  // A change.
3936  if (all != zero) {
3937  AddSpan
3938  all = zero;
3939  } else {
3940  prev1 = x;
3941  all = ~zero;
3942  }
3943  }
3944  byte <<= 1;
3945  ++x;
3946  }
3947  }
3948  } else {
3949  x += 8;
3950  }
3951  }
3952  if (all != zero) {
3953  AddSpan
3954  }
3955  }
3956 #undef AddSpan
3957 
3958  return region;
3959 }
3960 
3962  : d(&shared_empty)
3963 {
3964  d->ref.ref();
3965 }
3966 
3968 {
3969  if (r.isEmpty()) {
3970  d = &shared_empty;
3971  d->ref.ref();
3972  } else {
3973  d = new QRegionData;
3974  d->ref = 1;
3975 #if defined(Q_WS_X11)
3976  d->rgn = 0;
3977  d->xrectangles = 0;
3978 #elif defined(Q_WS_WIN)
3979  d->rgn = 0;
3980 #endif
3981  if (t == Rectangle) {
3982  d->qt_rgn = new QRegionPrivate(r);
3983  } else if (t == Ellipse) {
3984  QPainterPath path;
3985  path.addEllipse(r.x(), r.y(), r.width(), r.height());
3986  QPolygon a = path.toSubpathPolygons().at(0).toPolygon();
3988  }
3989  }
3990 }
3991 
3993 {
3994  if (a.count() > 2) {
3995  QRegionPrivate *qt_rgn = PolygonRegion(a.constData(), a.size(),
3996  fillRule == Qt::WindingFill ? WindingRule : EvenOddRule);
3997  if (qt_rgn) {
3998  d = new QRegionData;
3999  d->ref = 1;
4000 #if defined(Q_WS_X11)
4001  d->rgn = 0;
4002  d->xrectangles = 0;
4003 #elif defined(Q_WS_WIN)
4004  d->rgn = 0;
4005 #endif
4006  d->qt_rgn = qt_rgn;
4007  } else {
4008  d = &shared_empty;
4009  d->ref.ref();
4010  }
4011  } else {
4012  d = &shared_empty;
4013  d->ref.ref();
4014  }
4015 }
4016 
4018 {
4019  d = r.d;
4020  d->ref.ref();
4021 }
4022 
4023 
4025 {
4026  if (bm.isNull()) {
4027  d = &shared_empty;
4028  d->ref.ref();
4029  } else {
4030  d = new QRegionData;
4031  d->ref = 1;
4032 #if defined(Q_WS_X11)
4033  d->rgn = 0;
4034  d->xrectangles = 0;
4035 #elif defined(Q_WS_WIN)
4036  d->rgn = 0;
4037 #endif
4038  d->qt_rgn = qt_bitmapToRegion(bm);
4039  }
4040 }
4041 
4043 {
4044  delete x->qt_rgn;
4045 #if defined(Q_WS_X11)
4046  if (x->rgn)
4047  XDestroyRegion(x->rgn);
4048  if (x->xrectangles)
4049  free(x->xrectangles);
4050 #elif defined(Q_WS_WIN)
4051  if (x->rgn)
4052  qt_win_dispose_rgn(x->rgn);
4053 #endif
4054  delete x;
4055 }
4056 
4058 {
4059  if (!d->ref.deref())
4060  cleanUp(d);
4061 }
4062 
4063 
4065 {
4066  r.d->ref.ref();
4067  if (!d->ref.deref())
4068  cleanUp(d);
4069  d = r.d;
4070  return *this;
4071 }
4072 
4073 
4078 {
4079  QRegion r;
4081  x->ref = 1;
4082 #if defined(Q_WS_X11)
4083  x->rgn = 0;
4084  x->xrectangles = 0;
4085 #elif defined(Q_WS_WIN)
4086  x->rgn = 0;
4087 #endif
4088  if (d->qt_rgn)
4089  x->qt_rgn = new QRegionPrivate(*d->qt_rgn);
4090  else
4091  x->qt_rgn = new QRegionPrivate;
4092  if (!r.d->ref.deref())
4093  cleanUp(r.d);
4094  r.d = x.take();
4095  return r;
4096 }
4097 
4098 bool QRegion::isEmpty() const
4099 {
4100  return d == &shared_empty || d->qt_rgn->numRects == 0;
4101 }
4102 
4103 
4104 bool QRegion::contains(const QPoint &p) const
4105 {
4106  return PointInRegion(d->qt_rgn, p.x(), p.y());
4107 }
4108 
4109 bool QRegion::contains(const QRect &r) const
4110 {
4111  return RectInRegion(d->qt_rgn, r.left(), r.top(), r.width(), r.height()) != RectangleOut;
4112 }
4113 
4114 
4115 
4116 void QRegion::translate(int dx, int dy)
4117 {
4118  if ((dx == 0 && dy == 0) || isEmptyHelper(d->qt_rgn))
4119  return;
4120 
4121  detach();
4122  OffsetRegion(*d->qt_rgn, dx, dy);
4123 }
4124 
4126 {
4127  if (isEmptyHelper(d->qt_rgn))
4128  return r;
4129  if (isEmptyHelper(r.d->qt_rgn))
4130  return *this;
4131  if (d == r.d)
4132  return *this;
4133 
4134  if (d->qt_rgn->contains(*r.d->qt_rgn)) {
4135  return *this;
4136  } else if (r.d->qt_rgn->contains(*d->qt_rgn)) {
4137  return r;
4138  } else if (d->qt_rgn->canAppend(r.d->qt_rgn)) {
4139  QRegion result(*this);
4140  result.detach();
4141  result.d->qt_rgn->append(r.d->qt_rgn);
4142  return result;
4143  } else if (d->qt_rgn->canPrepend(r.d->qt_rgn)) {
4144  QRegion result(*this);
4145  result.detach();
4146  result.d->qt_rgn->prepend(r.d->qt_rgn);
4147  return result;
4148  } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
4149  return *this;
4150  } else {
4151  QRegion result;
4152  result.detach();
4153  UnionRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
4154  return result;
4155  }
4156 }
4157 
4159 {
4160  if (isEmptyHelper(d->qt_rgn))
4161  return *this = r;
4162  if (isEmptyHelper(r.d->qt_rgn))
4163  return *this;
4164  if (d == r.d)
4165  return *this;
4166 
4167  if (d->qt_rgn->contains(*r.d->qt_rgn)) {
4168  return *this;
4169  } else if (r.d->qt_rgn->contains(*d->qt_rgn)) {
4170  return *this = r;
4171  } else if (d->qt_rgn->canAppend(r.d->qt_rgn)) {
4172  detach();
4173  d->qt_rgn->append(r.d->qt_rgn);
4174  return *this;
4175  } else if (d->qt_rgn->canPrepend(r.d->qt_rgn)) {
4176  detach();
4177  d->qt_rgn->prepend(r.d->qt_rgn);
4178  return *this;
4179  } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
4180  return *this;
4181  } else {
4182  detach();
4183  UnionRegion(d->qt_rgn, r.d->qt_rgn, *d->qt_rgn);
4184  return *this;
4185  }
4186 }
4187 
4189 {
4190  if (isEmptyHelper(d->qt_rgn))
4191  return r;
4192  if (r.isEmpty())
4193  return *this;
4194 
4195  if (d->qt_rgn->contains(r)) {
4196  return *this;
4197  } else if (d->qt_rgn->within(r)) {
4198  return r;
4199  } else if (d->qt_rgn->numRects == 1 && d->qt_rgn->extents == r) {
4200  return *this;
4201  } else if (d->qt_rgn->canAppend(&r)) {
4202  QRegion result(*this);
4203  result.detach();
4204  result.d->qt_rgn->append(&r);
4205  return result;
4206  } else if (d->qt_rgn->canPrepend(&r)) {
4207  QRegion result(*this);
4208  result.detach();
4209  result.d->qt_rgn->prepend(&r);
4210  return result;
4211  } else {
4212  QRegion result;
4213  result.detach();
4214  QRegionPrivate rp(r);
4215  UnionRegion(d->qt_rgn, &rp, *result.d->qt_rgn);
4216  return result;
4217  }
4218 }
4219 
4221 {
4222  if (isEmptyHelper(d->qt_rgn))
4223  return *this = r;
4224  if (r.isEmpty())
4225  return *this;
4226 
4227  if (d->qt_rgn->contains(r)) {
4228  return *this;
4229  } else if (d->qt_rgn->within(r)) {
4230  return *this = r;
4231  } else if (d->qt_rgn->canAppend(&r)) {
4232  detach();
4233  d->qt_rgn->append(&r);
4234  return *this;
4235  } else if (d->qt_rgn->canPrepend(&r)) {
4236  detach();
4237  d->qt_rgn->prepend(&r);
4238  return *this;
4239  } else if (d->qt_rgn->numRects == 1 && d->qt_rgn->extents == r) {
4240  return *this;
4241  } else {
4242  detach();
4243  QRegionPrivate p(r);
4244  UnionRegion(d->qt_rgn, &p, *d->qt_rgn);
4245  return *this;
4246  }
4247 }
4248 
4250 {
4252  || !EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents))
4253  return QRegion();
4254 
4255  /* this is fully contained in r */
4256  if (r.d->qt_rgn->contains(*d->qt_rgn))
4257  return *this;
4258 
4259  /* r is fully contained in this */
4260  if (d->qt_rgn->contains(*r.d->qt_rgn))
4261  return r;
4262 
4263  if (r.d->qt_rgn->numRects == 1 && d->qt_rgn->numRects == 1) {
4265  d->qt_rgn->extents);
4266  return QRegion(rect);
4267  } else if (r.d->qt_rgn->numRects == 1) {
4268  QRegion result(*this);
4269  result.detach();
4270  result.d->qt_rgn->intersect(r.d->qt_rgn->extents);
4271  return result;
4272  } else if (d->qt_rgn->numRects == 1) {
4273  QRegion result(r);
4274  result.detach();
4275  result.d->qt_rgn->intersect(d->qt_rgn->extents);
4276  return result;
4277  }
4278 
4279  QRegion result;
4280  result.detach();
4281  miRegionOp(*result.d->qt_rgn, d->qt_rgn, r.d->qt_rgn, miIntersectO, 0, 0);
4282 
4283  /*
4284  * Can't alter dest's extents before we call miRegionOp because
4285  * it might be one of the source regions and miRegionOp depends
4286  * on the extents of those regions being the same. Besides, this
4287  * way there's no checking against rectangles that will be nuked
4288  * due to coalescing, so we have to examine fewer rectangles.
4289  */
4290  miSetExtents(*result.d->qt_rgn);
4291  return result;
4292 }
4293 
4295 {
4296  if (isEmptyHelper(d->qt_rgn) || r.isEmpty()
4297  || !EXTENTCHECK(&d->qt_rgn->extents, &r))
4298  return QRegion();
4299 
4300  /* this is fully contained in r */
4301  if (d->qt_rgn->within(r))
4302  return *this;
4303 
4304  /* r is fully contained in this */
4305  if (d->qt_rgn->contains(r))
4306  return r;
4307 
4308  if (d->qt_rgn->numRects == 1) {
4310  r.normalized());
4311  return QRegion(rect);
4312  }
4313 
4314  QRegion result(*this);
4315  result.detach();
4316  result.d->qt_rgn->intersect(r);
4317  return result;
4318 }
4319 
4321 {
4322  if (isEmptyHelper(d->qt_rgn) || isEmptyHelper(r.d->qt_rgn))
4323  return *this;
4324  if (r.d->qt_rgn->contains(*d->qt_rgn))
4325  return QRegion();
4326  if (!EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents))
4327  return *this;
4328  if (d == r.d || EqualRegion(d->qt_rgn, r.d->qt_rgn))
4329  return QRegion();
4330 
4331 #ifdef QT_REGION_DEBUG
4332  d->qt_rgn->selfTest();
4333  r.d->qt_rgn->selfTest();
4334 #endif
4335 
4336  QRegion result;
4337  result.detach();
4338  SubtractRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
4339 #ifdef QT_REGION_DEBUG
4340  result.d->qt_rgn->selfTest();
4341 #endif
4342  return result;
4343 }
4344 
4346 {
4347  if (isEmptyHelper(d->qt_rgn)) {
4348  return r;
4349  } else if (isEmptyHelper(r.d->qt_rgn)) {
4350  return *this;
4351  } else if (!EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents)) {
4352  return (*this + r);
4353  } else if (d == r.d || EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
4354  return QRegion();
4355  } else {
4356  QRegion result;
4357  result.detach();
4358  XorRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
4359  return result;
4360  }
4361 }
4362 
4364 {
4365  if (isEmpty())
4366  return QRect();
4367  return d->qt_rgn->extents;
4368 }
4369 
4377 #if defined(Q_WS_QWS) || defined(Q_WS_QPA)
4379 #endif
4380 bool qt_region_strictContains(const QRegion &region, const QRect &rect)
4381 {
4382  if (isEmptyHelper(region.d->qt_rgn) || !rect.isValid())
4383  return false;
4384 
4385 #if 0 // TEST_INNERRECT
4386  static bool guard = false;
4387  if (guard)
4388  return false;
4389  guard = true;
4390  QRegion inner = region.d->qt_rgn->innerRect;
4391  Q_ASSERT((inner - region).isEmpty());
4392  guard = false;
4393 
4394  int maxArea = 0;
4395  for (int i = 0; i < region.d->qt_rgn->numRects; ++i) {
4396  const QRect r = region.d->qt_rgn->rects.at(i);
4397  if (r.width() * r.height() > maxArea)
4398  maxArea = r.width() * r.height();
4399  }
4400 
4401  if (maxArea > region.d->qt_rgn->innerArea) {
4402  qDebug() << "not largest rectangle" << region << region.d->qt_rgn->innerRect;
4403  }
4404  Q_ASSERT(maxArea <= region.d->qt_rgn->innerArea);
4405 #endif
4406 
4407  const QRect r1 = region.d->qt_rgn->innerRect;
4408  return (rect.left() >= r1.left() && rect.right() <= r1.right()
4409  && rect.top() >= r1.top() && rect.bottom() <= r1.bottom());
4410 }
4411 
4413 {
4414  if (d->qt_rgn) {
4415  d->qt_rgn->vectorize();
4416  // hw: modify the vector size directly to avoid reallocation
4417  d->qt_rgn->rects.d->size = d->qt_rgn->numRects;
4418  return d->qt_rgn->rects;
4419  } else {
4420  return QVector<QRect>();
4421  }
4422 }
4423 
4424 void QRegion::setRects(const QRect *rects, int num)
4425 {
4426  *this = QRegion();
4427  if (!rects || num == 0 || (num == 1 && rects->isEmpty()))
4428  return;
4429 
4430  detach();
4431 
4432  d->qt_rgn->numRects = num;
4433  if (num == 1) {
4434  d->qt_rgn->extents = *rects;
4435  d->qt_rgn->innerRect = *rects;
4436  } else {
4437  d->qt_rgn->rects.resize(num);
4438 
4439  int left = INT_MAX,
4440  right = INT_MIN,
4441  top = INT_MAX,
4442  bottom = INT_MIN;
4443  for (int i = 0; i < num; ++i) {
4444  const QRect &rect = rects[i];
4445  d->qt_rgn->rects[i] = rect;
4446  left = qMin(rect.left(), left);
4447  right = qMax(rect.right(), right);
4448  top = qMin(rect.top(), top);
4449  bottom = qMax(rect.bottom(), bottom);
4450  d->qt_rgn->updateInnerRect(rect);
4451  }
4452  d->qt_rgn->extents = QRect(QPoint(left, top), QPoint(right, bottom));
4453  }
4454 }
4455 
4457 {
4458  return (d->qt_rgn ? d->qt_rgn->numRects : 0);
4459 }
4460 
4462 {
4463  return (d->qt_rgn ? d->qt_rgn->numRects : 0);
4464 }
4465 
4466 
4467 bool QRegion::operator==(const QRegion &r) const
4468 {
4469  if (!d->qt_rgn)
4470  return r.isEmpty();
4471  if (!r.d->qt_rgn)
4472  return isEmpty();
4473 
4474  if (d == r.d)
4475  return true;
4476  else
4477  return EqualRegion(d->qt_rgn, r.d->qt_rgn);
4478 }
4479 
4480 bool QRegion::intersects(const QRect &rect) const
4481 {
4482  if (isEmptyHelper(d->qt_rgn) || rect.isNull())
4483  return false;
4484 
4485  const QRect r = rect.normalized();
4486  if (!rect_intersects(d->qt_rgn->extents, r))
4487  return false;
4488  if (d->qt_rgn->numRects == 1)
4489  return true;
4490 
4491  const QVector<QRect> myRects = rects();
4492  for (QVector<QRect>::const_iterator it = myRects.constBegin(); it < myRects.constEnd(); ++it)
4493  if (rect_intersects(r, *it))
4494  return true;
4495  return false;
4496 }
4497 
4498 
4499 #endif
QRegion & operator|=(const QRegion &r)
Applies the united() function to this region and r and assigns the result to this region...
Definition: qregion.cpp:576
The QVariant class acts like a union for the most common Qt data types.
Definition: qvariant.h:92
void detach()
Definition: qregion.cpp:300
struct _ScanLineList * next
Definition: qregion.cpp:3136
void resize(int size)
The QDebug class provides an output stream for debugging information.
Definition: qdebug.h:62
void append(const QRect *r)
Definition: qregion.cpp:1460
QImage toImage() const
Converts the pixmap to a QImage.
Definition: qpixmap.cpp:542
struct _POINTBLOCK POINTBLOCK
QT_DEPRECATED int numRects() const
Returns the number of rectangles that will be returned in rects().
Definition: qregion.cpp:4456
#define QRGN_SETPTARRAY_ALT
Definition: qregion.cpp:315
static QRect qt_rect_intersect_normalized(const QRect &r1, const QRect &r2)
Definition: qregion.cpp:1396
QRegion intersected(const QRegion &r) const
Returns a region which is the intersection of this region and r.
Definition: qregion.h:112
struct _ScanLineList ScanLineList
bool isNull() const
Returns true if the rectangle is a null rectangle, otherwise returns false.
Definition: qrect.h:231
void qt_win_dispose_rgn(HRGN r)
void setHeight(int h)
Sets the height of the rectangle to the given height.
Definition: qrect.h:445
void setBottom(int pos)
Sets the bottom edge of the rectangle to the given y coordinate.
Definition: qrect.h:267
QRegionPrivate(const QRect &r)
Definition: qregion.cpp:1233
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
Definition: qglobal.h:1215
#define QRGN_TRANSLATE
Definition: qregion.cpp:317
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
int qint32
Definition: qglobal.h:937
struct _ScanLineListBlock ScanLineListBlock
static bool canMergeFromBelow(const QRect *top, const QRect *bottom, const QRect *nextToTop, const QRect *nextToBottom)
Definition: qregion.cpp:1358
bool within(const QRect &r1) const
Definition: qregion.cpp:1276
QRegion & operator-=(const QRegion &r)
Applies the subtracted() function to this region and r and assigns the result to this region...
Definition: qregion.cpp:651
static void XorRegion(QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest)
Definition: qregion.cpp:2776
RegionType
Specifies the shape of the region to be created.
Definition: qregion.h:71
static void SubtractRegion(QRegionPrivate *regM, QRegionPrivate *regS, register QRegionPrivate &dest)
Definition: qregion.cpp:2755
friend struct QRegionPrivate
Definition: qregion.h:195
~QRegion()
Destroys the region.
Definition: qregion.cpp:4057
Q_DECLARE_TYPEINFO(QRegionSpan, Q_PRIMITIVE_TYPE)
bool mergeFromAbove(QRect *bottom, const QRect *top, const QRect *nextToBottom, const QRect *nextToTop)
Definition: qregion.cpp:1384
#define it(className, varName)
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: qregion.cpp:1768
The QPainterPath class provides a container for painting operations, enabling graphical shapes to be ...
Definition: qpainterpath.h:67
int count(const T &t) const
Returns the number of occurrences of value in the vector.
Definition: qvector.h:742
QDebug & nospace()
Clears the stream&#39;s internal flag that records whether the last character was a space and returns a r...
Definition: qdebug.h:92
ByteOrder byteOrder() const
Returns the current byte order setting – either BigEndian or LittleEndian.
Definition: qdatastream.h:209
#define QRGN_SETPTARRAY_WIND
Definition: qregion.cpp:316
#define Q_GUI_EXPORT
Definition: qglobal.h:1450
#define EvenOddRule
Definition: qregion.cpp:1782
T & first()
Returns a reference to the first item in the vector.
Definition: qvector.h:260
bool atEnd() const
Returns true if the I/O device has reached the end position (end of the stream or file) or if there i...
#define AddSpan
int minor_axis
Definition: qregion.cpp:3055
struct _POINTBLOCK * next
Definition: qregion.cpp:1890
The QByteArray class provides an array of bytes.
Definition: qbytearray.h:135
#define RectanglePart
Definition: qregion.cpp:1781
#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres)
Definition: qregion.cpp:3062
T * take()
Returns the value of the pointer referenced by this object.
void intersect(const QRect &r)
Definition: qregion.cpp:1407
FillRule
Definition: qnamespace.h:1485
struct _EdgeTableEntry * back
Definition: qregion.cpp:3127
const_iterator constEnd() const
Returns a const STL-style iterator pointing to the imaginary item after the last item in the vector...
Definition: qvector.h:252
QRect normalized() const
Returns a normalized rectangle; i.e., a rectangle that has a non-negative width and height...
Definition: qrect.cpp:322
static QRegionPrivate * PolygonRegion(const QPoint *Pts, int Count, int rule)
Definition: qregion.cpp:3689
int left() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:240
int width() const
Returns the width of the rectangle.
Definition: qrect.h:303
#define QT_END_INCLUDE_NAMESPACE
This macro is equivalent to QT_BEGIN_NAMESPACE.
Definition: qglobal.h:92
QRegionPrivate * qt_rgn
Definition: qregion.h:211
long ASN1_INTEGER_get ASN1_INTEGER * a
QRect boundingRect() const
Returns the bounding rectangle of this region.
Definition: qregion.cpp:4363
The QPolygon class provides a vector of points using integer precision.
Definition: qpolygon.h:60
QPoint * pts
Definition: qregion.cpp:1889
bool mergeFromLeft(QRect *left, const QRect *right)
Definition: qregion.cpp:1348
QRegion subtract(const QRegion &r) const
Use subtracted(r) instead.
Definition: qregion.cpp:4320
ScanLineList scanlines
Definition: qregion.cpp:3143
static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest)
Definition: qregion.cpp:2577
QVectorData * d
Definition: qvector.h:109
static void loadAET(register EdgeTableEntry *AET, register EdgeTableEntry *ETEs)
Definition: qregion.cpp:3442
int height() const
Returns the height of the rectangle.
Definition: qrect.h:306
bool mergeFromRight(QRect *left, const QRect *right)
Definition: qregion.cpp:1338
int bottom() const
Returns the y-coordinate of the rectangle&#39;s bottom edge.
Definition: qrect.h:249
QRegion()
Constructs an empty region.
Definition: qregion.cpp:3961
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)
Definition: qregion.cpp:2654
static bool canMergeFromRight(const QRect *left, const QRect *right)
Definition: qregion.cpp:1326
#define EXTENTCHECK(r1, r2)
Definition: qregion.cpp:1846
const QRegion operator+(const QRegion &r) const
Applies the united() function to this region and r.
Definition: qregion.cpp:523
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)
Definition: qregion.cpp:2531
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
const QRegion operator^(const QRegion &r) const
Applies the xored() function to this region and r.
Definition: qregion.cpp:566
#define Q_BASIC_ATOMIC_INITIALIZER(a)
Definition: qbasicatomic.h:218
bool operator==(const QRegion &r) const
Returns true if the region is equal to r; otherwise returns false.
Definition: qregion.cpp:4467
static void FreeStorage(register ScanLineListBlock *pSLLBlock)
Definition: qregion.cpp:3553
static struct QRegionData shared_empty
Definition: qregion.h:218
#define QRGN_RECTS
Definition: qregion.cpp:322
struct _EdgeTableEntry * nextWETE
Definition: qregion.cpp:3128
void moveTo(const QPointF &p)
Moves the current point to the given point, implicitly starting a new subpath and closing the previou...
int rectCount() const
Returns the number of rectangles that will be returned in rects().
Definition: qregion.cpp:4461
Q_CORE_EXPORT QTextStream & right(QTextStream &s)
Format format() const
Returns the format of the image.
Definition: qimage.cpp:2305
#define WindingRule
Definition: qregion.cpp:1783
static void miUnionNonO(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
Definition: qregion.cpp:2495
QRegion copy() const
Definition: qregion.cpp:4077
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
The QScopedPointer class stores a pointer to a dynamically allocated object, and deletes it upon dest...
void resize(int size)
Sets the size of the vector to size.
Definition: qvector.h:342
#define EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
Definition: qregion.cpp:3197
void setVersion(int)
Sets the version number of the data serialization format to v.
Definition: qdatastream.h:215
BRESINFO bres
Definition: qregion.cpp:3125
bool mergeFromBelow(QRect *top, const QRect *bottom, const QRect *nextToTop, const QRect *nextToBottom)
Definition: qregion.cpp:1372
const QRegion operator &(const QRegion &r) const
void lineTo(const QPointF &p)
Adds a straight line from the current position to the given endPoint.
QRegionPrivate * qt_bitmapToRegion(const QBitmap &bitmap)
Definition: qregion.cpp:3886
Q_CORE_EXPORT void qDebug(const char *,...)
const_iterator constBegin() const
Returns a const STL-style iterator pointing to the first item in the vector.
Definition: qvector.h:249
unsigned char uchar
Definition: qglobal.h:994
The QBitmap class provides monochrome (1-bit depth) pixmaps.
Definition: qbitmap.h:55
struct _ScanLineListBlock * next
Definition: qregion.cpp:3156
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
#define QRGN_OR
Definition: qregion.cpp:318
QRegionPrivate(const QRegionPrivate &r)
Definition: qregion.cpp:1240
static void computeWAET(register EdgeTableEntry *AET)
Definition: qregion.cpp:3486
bool canPrepend(const QRect *r) const
Definition: qregion.cpp:1691
#define LARGE_COORDINATE
Definition: qregion.cpp:3262
QRegion & operator+=(const QRegion &r)
Applies the united() function to this region and r and assigns the result to this region...
Definition: qregion.cpp:4158
The Rectangle item provides a filled rectangle with an optional border.
bool isEmpty() const
Returns true if the region is empty; otherwise returns false.
Definition: qregion.cpp:4098
static void miSubtractNonO1(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
Definition: qregion.cpp:2620
#define QRGN_AND
Definition: qregion.cpp:319
void setTop(int pos)
Sets the top edge of the rectangle to the given y coordinate.
Definition: qrect.h:261
static void miSetExtents(QRegionPrivate &dest)
Definition: qregion.cpp:2005
void updateInnerRect(const QRect &rect)
Definition: qregion.cpp:1282
#define SLLSPERBLOCK
Definition: qregion.cpp:3152
QRegion intersect(const QRegion &r) const
Use intersected(r) instead.
Definition: qregion.cpp:4249
static void flushRow(const QRegionSpan *spans, int y, int numSpans, QRegionPrivate *reg, int *lastRow, int *extendTo, bool *needsExtend)
Definition: qregion.cpp:3575
void setRight(int pos)
Sets the right edge of the rectangle to the given x coordinate.
Definition: qrect.h:264
Q_CORE_EXPORT void qWarning(const char *,...)
#define QRGN_SUB
Definition: qregion.cpp:320
The QImage class provides a hardware-independent image representation that allows direct access to th...
Definition: qimage.h:87
bool contains(const QPoint &p) const
Returns true if the region contains the point p; otherwise returns false.
Definition: qregion.cpp:4104
struct _EdgeTableEntry EdgeTableEntry
static const char * data(const QByteArray &arr)
unsigned int uint
Definition: qglobal.h:996
void addRect(const QRectF &rect)
Adds the given rectangle to this path as a closed subpath.
static void UnionRectWithRegion(register const QRect *rect, const QRegionPrivate *source, QRegionPrivate &dest)
Definition: qregion.cpp:1972
The QRegion class specifies a clip region for a painter.
Definition: qregion.h:68
void setByteOrder(ByteOrder)
Sets the serialization byte order to bo.
static bool PointInRegion(QRegionPrivate *pRegion, int x, int y)
Definition: qregion.cpp:2832
static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2)
Definition: qregion.cpp:2810
void setCoords(int x1, int y1, int x2, int y2)
Sets the coordinates of the rectangle&#39;s top-left corner to (x1, y1), and the coordinates of its botto...
Definition: qrect.h:416
EdgeTableEntry * edgelist
Definition: qregion.cpp:3135
QRegion united(const QRegion &r) const
Returns a region which is the union of this region and r.
Definition: qregion.h:110
QRegion eor(const QRegion &r) const
Use xored(r) instead.
Definition: qregion.cpp:4345
#define QT_CATCH(A)
Definition: qglobal.h:1537
bool canAppend(const QRect *r) const
Definition: qregion.cpp:1669
bool contains(const QPoint &p, bool proper=false) const
Returns true if the given point is inside or on the edge of the rectangle, otherwise returns false...
Definition: qrect.cpp:1101
QRegion & operator=(const QRegion &)
Assigns r to this region and returns a reference to the region.
Definition: qregion.cpp:4064
int incr2
Definition: qregion.cpp:3058
const T & at(int i) const
Returns the item at index position i in the vector.
Definition: qvector.h:350
#define QRGN_SETRECT
Definition: qregion.cpp:313
int data[NUMPTSTOBUFFER *sizeof(QPoint)]
Definition: qregion.cpp:1888
static void cleanUp(QRegionData *x)
Definition: qregion.cpp:4042
int version() const
Returns the version number of the data serialization format.
Definition: qdatastream.h:212
QRegionSpan(int x1_, int x2_)
Definition: qregion.cpp:3566
void(* NonOverlapFunc)(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
Definition: qregion.cpp:1770
QVector< QRect > rects
Definition: qregion.cpp:1227
#define RectangleOut
Definition: qregion.cpp:1779
QRegion unite(const QRegion &r) const
Use united(r) instead.
Definition: qregion.cpp:4125
bool isEmpty() const
Returns true if the rectangle is empty, otherwise returns false.
Definition: qrect.h:234
int size
Definition: qvector.h:70
#define MERGERECT(r)
#define Q_CHECK_PTR(p)
Definition: qglobal.h:1853
#define NUMPTSTOBUFFER
Definition: qregion.cpp:1881
void setY(int y)
Sets the y coordinate of this point to the given y coordinate.
Definition: qpoint.h:137
int top() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:243
int width() const
Returns the width of the image.
Definition: qimage.cpp:1557
void setRects(const QRect *rect, int num)
Sets the region using the array of rectangles specified by rects and number.
Definition: qregion.cpp:4424
int right() const
Returns the x-coordinate of the rectangle&#39;s right edge.
Definition: qrect.h:246
Q_AUTOTEST_EXPORT QPainterPath qt_regionToPath(const QRegion &region)
Definition: qregion.cpp:1160
void setLeft(int pos)
Sets the left edge of the rectangle to the given x coordinate.
Definition: qrect.h:258
bool contains(const QRect &r2) const
Definition: qregion.cpp:1267
static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock)
Definition: qregion.cpp:3274
const QRegion operator-(const QRegion &r) const
Applies the subtracted() function to this region and r.
Definition: qregion.cpp:557
int y() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:255
static void miRegionOp(register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2, OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func, NonOverlapFunc nonOverlap2Func)
Definition: qregion.cpp:2279
int x() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:252
static bool RectInRegion(register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
Definition: qregion.cpp:2851
QRegion & operator^=(const QRegion &r)
Applies the xored() function to this region and r and assigns the result to this region.
Definition: qregion.cpp:661
The QPoint class defines a point in the plane using integer precision.
Definition: qpoint.h:53
QVector< QRect > rects() const
Returns an array of non-overlapping rectangles that make up the region.
Definition: qregion.cpp:4412
unsigned int quint32
Definition: qglobal.h:938
void setWidth(int w)
Sets the width of the rectangle to the given width.
Definition: qrect.h:442
static const int zero
The QRect class defines a rectangle in the plane using integer precision.
Definition: qrect.h:58
#define Q_AUTOTEST_EXPORT
Definition: qglobal.h:1510
struct _EdgeTableEntry * next
Definition: qregion.cpp:3126
int height() const
Returns the height of the image.
Definition: qimage.cpp:1572
QRegionPrivate & operator=(const QRegionPrivate &r)
Definition: qregion.cpp:1248
bool contains(const T &t) const
Returns true if the vector contains an occurrence of value; otherwise returns false.
Definition: qvector.h:731
int y() const
Returns the y coordinate of this point.
Definition: qpoint.h:131
static bool canMergeFromLeft(const QRect *right, const QRect *left)
Definition: qregion.cpp:1333
bool intersects(const QRegion &r) const
Returns true if this region intersects with region, otherwise returns false.
Definition: qregion.cpp:766
#define QT_BEGIN_INCLUDE_NAMESPACE
This macro is equivalent to QT_END_NAMESPACE.
Definition: qglobal.h:91
friend bool qt_region_strictContains(const QRegion &region, const QRect &rect)
Returns true if rect is guaranteed to be fully contained in region.
Definition: qregion.cpp:4380
QList< QPolygonF > toSubpathPolygons(const QMatrix &matrix=QMatrix()) const
This is an overloaded member function, provided for convenience. It differs from the above function o...
QRegion & operator &=(const QRegion &r)
#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
Definition: qregion.cpp:3174
bool rect_intersects(const QRect &r1, const QRect &r2)
Definition: qregion.cpp:751
void translate(int dx, int dy)
Translates (moves) the region dx along the X axis and dy along the Y axis.
Definition: qregion.cpp:4116
T * data()
Returns a pointer to the data stored in the vector.
Definition: qvector.h:152
static int InsertionSort(register EdgeTableEntry *AET)
Definition: qregion.cpp:3520
void exec(const QByteArray &ba, int ver=0, QDataStream::ByteOrder byteOrder=QDataStream::BigEndian)
Definition: qregion.cpp:336
QRegion translated(int dx, int dy) const
Returns a copy of the region that is translated dx along the x axis and dy along the y axis...
Definition: qregion.cpp:743
bool isEmpty() const
Returns true if the vector has size 0; otherwise returns false.
Definition: qvector.h:139
#define QRGN_XOR
Definition: qregion.cpp:321
The QDataStream class provides serialization of binary data to a QIODevice.
Definition: qdatastream.h:71
static void CreateETandAET(register int count, register const QPoint *pts, EdgeTable *ET, EdgeTableEntry *AET, register EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
Definition: qregion.cpp:3355
const T * constData() const
Returns a const pointer to the data stored in the vector.
Definition: qvector.h:154
void reserve(int size)
Attempts to allocate memory for at least size elements.
Definition: qvector.h:339
int x() const
Returns the x coordinate of this point.
Definition: qpoint.h:128
const QRegion operator|(const QRegion &r) const
Applies the united() function to this region and r.
Definition: qregion.cpp:514
friend Q_GUI_EXPORT QDataStream & operator<<(QDataStream &, const QRegion &)
Writes the region r to the stream s and returns a reference to the stream.
Definition: qregion.cpp:446
ByteOrder
The byte order used for reading/writing the data.
Definition: qdatastream.h:96
QRegion subtracted(const QRegion &r) const
Returns a region which is r subtracted from this region.
Definition: qregion.h:114
QRegion xored(const QRegion &r) const
Returns a region which is the exclusive or (XOR) of this region and r.
Definition: qregion.h:115
int width() const
Definition: qregion.cpp:3570
bool isNull() const
Returns true if this is a null pixmap; otherwise returns false.
Definition: qpixmap.cpp:615
bool isValid() const
Returns true if the rectangle is valid, otherwise returns false.
Definition: qrect.h:237
static bool overlaps(int posA, int lengthA, int posB, int lengthB)
Definition: textwriter.cpp:53
void translate(int dx, int dy)
Moves the rectangle dx along the x axis and dy along the y axis, relative to the current position...
Definition: qrect.h:312
static const KeyPair *const end
#define QRGN_SETELLIPSE
Definition: qregion.cpp:314
#define MEMCHECK(dest, rect, firstrect)
Definition: qregion.cpp:1869
struct QRegionData * d
Definition: qregion.h:217
friend Q_GUI_EXPORT QDataStream & operator>>(QDataStream &, QRegion &)
Reads a region from the stream s into r and returns a reference to the stream.
Definition: qregion.cpp:482
void prepend(const T &t)
Inserts value at the beginning of the vector.
Definition: qvector.h:378
Q_CORE_EXPORT QTextStream & left(QTextStream &s)
void setX(int x)
Sets the x coordinate of this point to the given x coordinate.
Definition: qpoint.h:134
#define SMALL_COORDINATE
Definition: qregion.cpp:3263
static void miIntersectO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End, register const QRect *r2, const QRect *r2End, int y1, int y2)
Definition: qregion.cpp:2085
int size() const
Returns the number of items in the vector.
Definition: qvector.h:137
static bool isEmptyHelper(const QRegionPrivate *preg)
Definition: qregion.cpp:1321
QBasicAtomicInt ref
Definition: qregion.h:201
#define QT_TRY
Definition: qglobal.h:1536
#define INT_MAX
#define RectangleIn
Definition: qregion.cpp:1780
void prepend(const QRect *r)
Definition: qregion.cpp:1637
static int miCoalesce(register QRegionPrivate &dest, int prevStart, int curStart)
Definition: qregion.cpp:2150
bool contains(const QRegionPrivate &r) const
Definition: qregion.cpp:1263
uchar * scanLine(int)
Returns a pointer to the pixel data at the scanline with index i.
Definition: qimage.cpp:1886
void vectorize()
Definition: qregion.cpp:1290
void addEllipse(const QRectF &rect)
Creates an ellipse within the specified boundingRectangle and adds it to the painter path as a closed...
int size() const
static int area(const QSize &s)
Definition: qicon.cpp:155
static void OffsetRegion(register QRegionPrivate &region, register int x, register int y)
Definition: qregion.cpp:2054
static void PtsToRegion(register int numFullPtBlocks, register int iCurPtBlock, POINTBLOCK *FirstPtBlock, QRegionPrivate *reg)
Definition: qregion.cpp:3619