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