src/gui/painting/qpathclipper.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/legal
   5 **
   6 ** This file is part of the QtGui module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** Commercial License Usage
  10 ** Licensees holding valid commercial Qt licenses may use this file in
  11 ** accordance with the commercial license agreement provided with the
  12 ** Software or, alternatively, in accordance with the terms contained in
  13 ** a written agreement between you and Digia.  For licensing terms and
  14 ** conditions see http://qt.digia.com/licensing.  For further information
  15 ** use the contact form at http://qt.digia.com/contact-us.
  16 **
  17 ** GNU Lesser General Public License Usage
  18 ** Alternatively, this file may be used under the terms of the GNU Lesser
  19 ** General Public License version 2.1 as published by the Free Software
  20 ** Foundation and appearing in the file LICENSE.LGPL included in the
  21 ** packaging of this file.  Please review the following information to
  22 ** ensure the GNU Lesser General Public License version 2.1 requirements
  23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  24 **
  25 ** In addition, as a special exception, Digia gives you certain additional
  26 ** rights.  These rights are described in the Digia Qt LGPL Exception
  27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  28 **
  29 ** GNU General Public License Usage
  30 ** Alternatively, this file may be used under the terms of the GNU
  31 ** General Public License version 3.0 as published by the Free Software
  32 ** Foundation and appearing in the file LICENSE.GPL included in the
  33 ** packaging of this file.  Please review the following information to
  34 ** ensure the GNU General Public License version 3.0 requirements will be
  35 ** met: http://www.gnu.org/copyleft/gpl.html.
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include "qpathclipper_p.h"
  43
  44 #include <private/qbezier_p.h>
  45 #include <private/qdatabuffer_p.h>
  46 #include <private/qnumeric_p.h>
  47 #include <qmath.h>
  48
  49 /**
  50   The algorithm is as follows:
  51
  52   1. Find all intersections between the two paths (including self-intersections),
  53      and build a winged edge structure of non-intersecting parts.
  54   2. While there are more unhandled edges:
  55     3. Pick a y-coordinate from an unhandled edge.
  56     4. Intersect the horizontal line at y-coordinate with all edges.
  57     5. Traverse intersections left to right deciding whether each subpath should be added or not.
  58     6. If the subpath should be added, traverse the winged-edge structure and add the edges to
  59        a separate winged edge structure.
  60     7. Mark all edges in subpaths crossing the horizontal line as handled.
  61  8. (Optional) Simplify the resulting winged edge structure by merging shared edges.
  62  9. Convert the resulting winged edge structure to a painter path.
  63  */
  64
  65 #include <qdebug.h>
  66
  67 QT_BEGIN_NAMESPACE
  68
  69 static inline bool fuzzyIsNull(qreal d)
  70 {
  71     if (sizeof(qreal) == sizeof(double))
  72         return qAbs(d) <= 1e-12;
  73     else
  74         return qAbs(d) <= 1e-5f;
  75 }
  76
  77 static inline bool comparePoints(const QPointF &a, const QPointF &b)
  78 {
  79     return fuzzyIsNull(a.x() - b.x())
  80            && fuzzyIsNull(a.y() - b.y());
  81 }
  82
  83 //#define QDEBUG_CLIPPER
  84 static qreal dot(const QPointF &a, const QPointF &b)
  85 {
  86     return a.x() * b.x() + a.y() * b.y();
  87 }
  88
  89 static void normalize(double &x, double &y)
  90 {
  91     double reciprocal = 1 / qSqrt(x * x + y * y);
  92     x *= reciprocal;
  93     y *= reciprocal;
  94 }
  95
  96 struct QIntersection
  97 {
  98     qreal alphaA;
  99     qreal alphaB;
 100
 101     QPointF pos;
 102 };
 103
 104 class QIntersectionFinder
 105 {
 106 public:
 107     void produceIntersections(QPathSegments &segments);
 108     bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const;
 109
 110 private:
 111     bool linesIntersect(const QLineF &a, const QLineF &b) const;
 112 };
 113
 114 bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const
 115 {
 116     const QPointF p1 = a.p1();
 117     const QPointF p2 = a.p2();
 118
 119     const QPointF q1 = b.p1();
 120     const QPointF q2 = b.p2();
 121
 122     if (comparePoints(p1, p2) || comparePoints(q1, q2))
 123         return false;
 124
 125     const bool p1_equals_q1 = comparePoints(p1, q1);
 126     const bool p2_equals_q2 = comparePoints(p2, q2);
 127
 128     if (p1_equals_q1 && p2_equals_q2)
 129         return true;
 130
 131     const bool p1_equals_q2 = comparePoints(p1, q2);
 132     const bool p2_equals_q1 = comparePoints(p2, q1);
 133
 134     if (p1_equals_q2 && p2_equals_q1)
 135         return true;
 136
 137     const QPointF pDelta = p2 - p1;
 138     const QPointF qDelta = q2 - q1;
 139
 140     const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x();
 141
 142     if (qFuzzyIsNull(par)) {
 143         const QPointF normal(-pDelta.y(), pDelta.x());
 144
 145         // coinciding?
 146         if (qFuzzyIsNull(dot(normal, q1 - p1))) {
 147             const qreal dp = dot(pDelta, pDelta);
 148
 149             const qreal tq1 = dot(pDelta, q1 - p1);
 150             const qreal tq2 = dot(pDelta, q2 - p1);
 151
 152             if ((tq1 > 0 && tq1 < dp) || (tq2 > 0 && tq2 < dp))
 153                 return true;
 154
 155             const qreal dq = dot(qDelta, qDelta);
 156
 157             const qreal tp1 = dot(qDelta, p1 - q1);
 158             const qreal tp2 = dot(qDelta, p2 - q1);
 159
 160             if ((tp1 > 0 && tp1 < dq) || (tp2 > 0 && tp2 < dq))
 161                 return true;
 162         }
 163
 164         return false;
 165     }
 166
 167     const qreal invPar = 1 / par;
 168
 169     const qreal tp = (qDelta.y() * (q1.x() - p1.x()) -
 170                       qDelta.x() * (q1.y() - p1.y())) * invPar;
 171
 172     if (tp < 0 || tp > 1)
 173         return false;
 174
 175     const qreal tq = (pDelta.y() * (q1.x() - p1.x()) -
 176                       pDelta.x() * (q1.y() - p1.y())) * invPar;
 177
 178     return tq >= 0 && tq <= 1;
 179 }
 180
 181 bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const
 182 {
 183     if (a.segments() == 0 || b.segments() == 0)
 184         return false;
 185
 186     const QRectF &rb0 = b.elementBounds(0);
 187
 188     qreal minX = rb0.left();
 189     qreal minY = rb0.top();
 190     qreal maxX = rb0.right();
 191     qreal maxY = rb0.bottom();
 192
 193     for (int i = 1; i < b.segments(); ++i) {
 194         const QRectF &r = b.elementBounds(i);
 195         minX = qMin(minX, r.left());
 196         minY = qMin(minY, r.top());
 197         maxX = qMax(maxX, r.right());
 198         maxY = qMax(maxY, r.bottom());
 199     }
 200
 201     QRectF rb(minX, minY, maxX - minX, maxY - minY);
 202
 203     for (int i = 0; i < a.segments(); ++i) {
 204         const QRectF &r1 = a.elementBounds(i);
 205
 206         if (r1.left() > rb.right() || rb.left() > r1.right())
 207             continue;
 208         if (r1.top() > rb.bottom() || rb.top() > r1.bottom())
 209             continue;
 210
 211         for (int j = 0; j < b.segments(); ++j) {
 212             const QRectF &r2 = b.elementBounds(j);
 213
 214             if (r1.left() > r2.right() || r2.left() > r1.right())
 215                 continue;
 216             if (r1.top() > r2.bottom() || r2.top() > r1.bottom())
 217                 continue;
 218
 219             if (linesIntersect(a.lineAt(i), b.lineAt(j)))
 220                 return true;
 221         }
 222     }
 223
 224     return false;
 225 }
 226
 227 namespace {
 228 struct TreeNode
 229 {
 230     qreal splitLeft;
 231     qreal splitRight;
 232     bool leaf;
 233
 234     int lowestLeftIndex;
 235     int lowestRightIndex;
 236
 237     union {
 238         struct {
 239             int first;
 240             int last;
 241         } interval;
 242         struct {
 243             int left;
 244             int right;
 245         } children;
 246     } index;
 247 };
 248
 249 struct RectF
 250 {
 251     qreal x1;
 252     qreal y1;
 253     qreal x2;
 254     qreal y2;
 255 };
 256
 257 class SegmentTree
 258 {
 259 public:
 260     SegmentTree(QPathSegments &segments);
 261
 262     QRectF boundingRect() const;
 263
 264     void produceIntersections(int segment);
 265
 266 private:
 267     TreeNode buildTree(int first, int last, int depth, const RectF &bounds);
 268
 269     void produceIntersectionsLeaf(const TreeNode &node, int segment);
 270     void produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis);
 271     void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections);
 272
 273     QPathSegments &m_segments;
 274     QVector<int> m_index;
 275
 276     RectF m_bounds;
 277
 278     QVector<TreeNode> m_tree;
 279     QDataBuffer<QIntersection> m_intersections;
 280 };
 281
 282 SegmentTree::SegmentTree(QPathSegments &segments)
 283     : m_segments(segments),
 284       m_intersections(0)
 285 {
 286     m_bounds.x1 = qt_inf();
 287     m_bounds.y1 = qt_inf();
 288     m_bounds.x2 = -qt_inf();
 289     m_bounds.y2 = -qt_inf();
 290
 291     m_index.resize(m_segments.segments());
 292
 293     for (int i = 0; i < m_index.size(); ++i) {
 294         m_index[i] = i;
 295
 296         const QRectF &segmentBounds = m_segments.elementBounds(i);
 297
 298         if (segmentBounds.left() < m_bounds.x1)
 299             m_bounds.x1 = segmentBounds.left();
 300         if (segmentBounds.top() < m_bounds.y1)
 301             m_bounds.y1 = segmentBounds.top();
 302         if (segmentBounds.right() > m_bounds.x2)
 303             m_bounds.x2 = segmentBounds.right();
 304         if (segmentBounds.bottom() > m_bounds.y2)
 305             m_bounds.y2 = segmentBounds.bottom();
 306     }
 307
 308     m_tree.resize(1);
 309
 310     TreeNode root = buildTree(0, m_index.size(), 0, m_bounds);
 311     m_tree[0] = root;
 312 }
 313
 314 QRectF SegmentTree::boundingRect() const
 315 {
 316     return QRectF(QPointF(m_bounds.x1, m_bounds.y1),
 317                   QPointF(m_bounds.x2, m_bounds.y2));
 318 }
 319
 320 static inline qreal coordinate(const QPointF &pos, int axis)
 321 {
 322     return axis == 0 ? pos.x() : pos.y();
 323 }
 324
 325 TreeNode SegmentTree::buildTree(int first, int last, int depth, const RectF &bounds)
 326 {
 327     if (depth >= 24 || (last - first) <= 10) {
 328         TreeNode node;
 329         node.leaf = true;
 330         node.index.interval.first = first;
 331         node.index.interval.last = last;
 332
 333         return node;
 334     }
 335
 336     int splitAxis = (depth & 1);
 337
 338     TreeNode node;
 339     node.leaf = false;
 340
 341     qreal split = 0.5f * ((&bounds.x1)[splitAxis] + (&bounds.x2)[splitAxis]);
 342
 343     node.splitLeft = (&bounds.x1)[splitAxis];
 344     node.splitRight = (&bounds.x2)[splitAxis];
 345
 346     node.lowestLeftIndex = INT_MAX;
 347     node.lowestRightIndex = INT_MAX;
 348
 349     const int treeSize = m_tree.size();
 350
 351     node.index.children.left = treeSize;
 352     node.index.children.right = treeSize + 1;
 353
 354     m_tree.resize(treeSize + 2);
 355
 356     int l = first;
 357     int r = last - 1;
 358
 359     // partition into left and right sets
 360     while (l <= r) {
 361         const int index = m_index.at(l);
 362         const QRectF &segmentBounds = m_segments.elementBounds(index);
 363
 364         qreal lowCoordinate = coordinate(segmentBounds.topLeft(), splitAxis);
 365
 366         if (coordinate(segmentBounds.center(), splitAxis) < split) {
 367             qreal highCoordinate = coordinate(segmentBounds.bottomRight(), splitAxis);
 368             if (highCoordinate > node.splitLeft)
 369                 node.splitLeft = highCoordinate;
 370             if (index < node.lowestLeftIndex)
 371                 node.lowestLeftIndex = index;
 372             ++l;
 373         } else {
 374             if (lowCoordinate < node.splitRight)
 375                 node.splitRight = lowCoordinate;
 376             if (index < node.lowestRightIndex)
 377                 node.lowestRightIndex = index;
 378             qSwap(m_index[l], m_index[r]);
 379             --r;
 380         }
 381     }
 382
 383     RectF lbounds = bounds;
 384     (&lbounds.x2)[splitAxis] = node.splitLeft;
 385
 386     RectF rbounds = bounds;
 387     (&rbounds.x1)[splitAxis] = node.splitRight;
 388
 389     TreeNode left = buildTree(first, l, depth + 1, lbounds);
 390     m_tree[node.index.children.left] = left;
 391
 392     TreeNode right = buildTree(l, last, depth + 1, rbounds);
 393     m_tree[node.index.children.right] = right;
 394
 395     return node;
 396 }
 397
 398 void SegmentTree::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections)
 399 {
 400     const QPointF p1 = a.p1();
 401     const QPointF p2 = a.p2();
 402
 403     const QPointF q1 = b.p1();
 404     const QPointF q2 = b.p2();
 405
 406     if (comparePoints(p1, p2) || comparePoints(q1, q2))
 407         return;
 408
 409     const bool p1_equals_q1 = comparePoints(p1, q1);
 410     const bool p2_equals_q2 = comparePoints(p2, q2);
 411
 412     if (p1_equals_q1 && p2_equals_q2)
 413         return;
 414
 415     const bool p1_equals_q2 = comparePoints(p1, q2);
 416     const bool p2_equals_q1 = comparePoints(p2, q1);
 417
 418     if (p1_equals_q2 && p2_equals_q1)
 419         return;
 420
 421     const QPointF pDelta = p2 - p1;
 422     const QPointF qDelta = q2 - q1;
 423
 424     const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x();
 425
 426     if (qFuzzyIsNull(par)) {
 427         const QPointF normal(-pDelta.y(), pDelta.x());
 428
 429         // coinciding?
 430         if (qFuzzyIsNull(dot(normal, q1 - p1))) {
 431             const qreal invDp = 1 / dot(pDelta, pDelta);
 432
 433             const qreal tq1 = dot(pDelta, q1 - p1) * invDp;
 434             const qreal tq2 = dot(pDelta, q2 - p1) * invDp;
 435
 436             if (tq1 > 0 && tq1 < 1) {
 437                 QIntersection intersection;
 438                 intersection.alphaA = tq1;
 439                 intersection.alphaB = 0;
 440                 intersection.pos = q1;
 441                 intersections.add(intersection);
 442             }
 443
 444             if (tq2 > 0 && tq2 < 1) {
 445                 QIntersection intersection;
 446                 intersection.alphaA = tq2;
 447                 intersection.alphaB = 1;
 448                 intersection.pos = q2;
 449                 intersections.add(intersection);
 450             }
 451
 452             const qreal invDq = 1 / dot(qDelta, qDelta);
 453
 454             const qreal tp1 = dot(qDelta, p1 - q1) * invDq;
 455             const qreal tp2 = dot(qDelta, p2 - q1) * invDq;
 456
 457             if (tp1 > 0 && tp1 < 1) {
 458                 QIntersection intersection;
 459                 intersection.alphaA = 0;
 460                 intersection.alphaB = tp1;
 461                 intersection.pos = p1;
 462                 intersections.add(intersection);
 463             }
 464
 465             if (tp2 > 0 && tp2 < 1) {
 466                 QIntersection intersection;
 467                 intersection.alphaA = 1;
 468                 intersection.alphaB = tp2;
 469                 intersection.pos = p2;
 470                 intersections.add(intersection);
 471             }
 472         }
 473
 474         return;
 475     }
 476
 477     // if the lines are not parallel and share a common end point, then they
 478     // don't intersect
 479     if (p1_equals_q1 || p1_equals_q2 || p2_equals_q1 || p2_equals_q2)
 480         return;
 481
 482
 483     const qreal tp = (qDelta.y() * (q1.x() - p1.x()) -
 484                       qDelta.x() * (q1.y() - p1.y())) / par;
 485     const qreal tq = (pDelta.y() * (q1.x() - p1.x()) -
 486                       pDelta.x() * (q1.y() - p1.y())) / par;
 487
 488     if (tp<0 || tp>1 || tq<0 || tq>1)
 489         return;
 490
 491     const bool p_zero = qFuzzyIsNull(tp);
 492     const bool p_one = qFuzzyIsNull(tp - 1);
 493
 494     const bool q_zero = qFuzzyIsNull(tq);
 495     const bool q_one = qFuzzyIsNull(tq - 1);
 496
 497     if ((q_zero || q_one) && (p_zero || p_one))
 498         return;
 499
 500     QPointF pt;
 501     if (p_zero) {
 502         pt = p1;
 503     } else if (p_one) {
 504         pt = p2;
 505     } else if (q_zero) {
 506         pt = q1;
 507     } else if (q_one) {
 508         pt = q2;
 509     } else {
 510         pt = q1 + (q2 - q1) * tq;
 511     }
 512
 513     QIntersection intersection;
 514     intersection.alphaA = tp;
 515     intersection.alphaB = tq;
 516     intersection.pos = pt;
 517     intersections.add(intersection);
 518 }
 519
 520 void SegmentTree::produceIntersections(int segment)
 521 {
 522     const QRectF &segmentBounds = m_segments.elementBounds(segment);
 523
 524     RectF sbounds;
 525     sbounds.x1 = segmentBounds.left();
 526     sbounds.y1 = segmentBounds.top();
 527     sbounds.x2 = segmentBounds.right();
 528     sbounds.y2 = segmentBounds.bottom();
 529
 530     produceIntersections(m_tree.at(0), segment, sbounds, m_bounds, 0);
 531 }
 532
 533 void SegmentTree::produceIntersectionsLeaf(const TreeNode &node, int segment)
 534 {
 535     const QRectF &r1 = m_segments.elementBounds(segment);
 536     const QLineF lineA = m_segments.lineAt(segment);
 537
 538     for (int i = node.index.interval.first; i < node.index.interval.last; ++i) {
 539         const int other = m_index.at(i);
 540         if (other >= segment)
 541             continue;
 542
 543         const QRectF &r2 = m_segments.elementBounds(other);
 544
 545         if (r1.left() > r2.right() || r2.left() > r1.right())
 546             continue;
 547         if (r1.top() > r2.bottom() || r2.top() > r1.bottom())
 548             continue;
 549
 550         m_intersections.reset();
 551
 552         const QLineF lineB = m_segments.lineAt(other);
 553
 554         intersectLines(lineA, lineB, m_intersections);
 555
 556         for (int k = 0; k < m_intersections.size(); ++k) {
 557             QPathSegments::Intersection i_isect, j_isect;
 558             i_isect.vertex = j_isect.vertex = m_segments.addPoint(m_intersections.at(k).pos);
 559
 560             i_isect.t = m_intersections.at(k).alphaA;
 561             j_isect.t = m_intersections.at(k).alphaB;
 562
 563             i_isect.next = 0;
 564             j_isect.next = 0;
 565
 566             m_segments.addIntersection(segment, i_isect);
 567             m_segments.addIntersection(other, j_isect);
 568         }
 569     }
 570 }
 571
 572 void SegmentTree::produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis)
 573 {
 574     if (node.leaf) {
 575         produceIntersectionsLeaf(node, segment);
 576         return;
 577     }
 578
 579     RectF lbounds = nodeBounds;
 580     (&lbounds.x2)[axis] = node.splitLeft;
 581
 582     RectF rbounds = nodeBounds;
 583     (&rbounds.x1)[axis] = node.splitRight;
 584
 585     if (segment > node.lowestLeftIndex && (&segmentBounds.x1)[axis] <= node.splitLeft)
 586         produceIntersections(m_tree.at(node.index.children.left), segment, segmentBounds, lbounds, !axis);
 587
 588     if (segment > node.lowestRightIndex && (&segmentBounds.x2)[axis] >= node.splitRight)
 589         produceIntersections(m_tree.at(node.index.children.right), segment, segmentBounds, rbounds, !axis);
 590 }
 591
 592 }
 593
 594 void QIntersectionFinder::produceIntersections(QPathSegments &segments)
 595 {
 596     SegmentTree tree(segments);
 597
 598     for (int i = 0; i < segments.segments(); ++i)
 599         tree.produceIntersections(i);
 600 }
 601
 602 class QKdPointTree
 603 {
 604 public:
 605     enum Traversal {
 606         TraverseBoth,
 607         TraverseLeft,
 608         TraverseRight,
 609         TraverseNone
 610     };
 611
 612     struct Node {
 613         int point;
 614         int id;
 615
 616         Node *left;
 617         Node *right;
 618     };
 619
 620     QKdPointTree(const QPathSegments &segments)
 621         : m_segments(&segments)
 622         , m_nodes(m_segments->points())
 623         , m_id(0)
 624     {
 625         m_nodes.resize(m_segments->points());
 626
 627         for (int i = 0; i < m_nodes.size(); ++i) {
 628             m_nodes.at(i).point = i;
 629             m_nodes.at(i).id = -1;
 630         }
 631
 632         m_rootNode = build(0, m_nodes.size());
 633     }
 634
 635     int build(int begin, int end, int depth = 0);
 636
 637     Node *rootNode()
 638     {
 639         return &m_nodes.at(m_rootNode);
 640     }
 641
 642     inline int nextId()
 643     {
 644         return m_id++;
 645     }
 646
 647 private:
 648     const QPathSegments *m_segments;
 649     QDataBuffer<Node> m_nodes;
 650
 651     int m_rootNode;
 652     int m_id;
 653 };
 654
 655 template <typename T>
 656 void qTraverseKdPointTree(QKdPointTree::Node &node, T &t, int depth = 0)
 657 {
 658     QKdPointTree::Traversal status = t(node, depth);
 659
 660     const bool traverseRight = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseRight);
 661     const bool traverseLeft = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseLeft);
 662
 663     if (traverseLeft && node.left)
 664         QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.left, t, depth + 1);
 665
 666     if (traverseRight && node.right)
 667         QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.right, t, depth + 1);
 668 }
 669
 670 static inline qreal component(const QPointF &point, unsigned int i)
 671 {
 672     Q_ASSERT(i < 2);
 673     const qreal components[] = { point.x(), point.y() };
 674     return components[i];
 675 }
 676
 677 int QKdPointTree::build(int begin, int end, int depth)
 678 {
 679     Q_ASSERT(end > begin);
 680
 681     const qreal pivot = component(m_segments->pointAt(m_nodes.at(begin).point), depth & 1);
 682
 683     int first = begin + 1;
 684     int last = end - 1;
 685
 686     while (first <= last) {
 687         const qreal value = component(m_segments->pointAt(m_nodes.at(first).point), depth & 1);
 688
 689         if (value < pivot)
 690             ++first;
 691         else {
 692             qSwap(m_nodes.at(first), m_nodes.at(last));
 693             --last;
 694         }
 695     }
 696
 697     qSwap(m_nodes.at(last), m_nodes.at(begin));
 698
 699     if (last > begin)
 700         m_nodes.at(last).left = &m_nodes.at(build(begin, last, depth + 1));
 701     else
 702         m_nodes.at(last).left = 0;
 703
 704     if (last + 1 < end)
 705         m_nodes.at(last).right = &m_nodes.at(build(last + 1, end, depth + 1));
 706     else
 707         m_nodes.at(last).right = 0;
 708
 709     return last;
 710 }
 711
 712 class QKdPointFinder
 713 {
 714 public:
 715     QKdPointFinder(int point, const QPathSegments &segments, QKdPointTree &tree)
 716         : m_point(point)
 717         , m_result(-1)
 718         , m_segments(&segments)
 719         , m_tree(&tree)
 720     {
 721         pointComponents[0] = segments.pointAt(point).x();
 722         pointComponents[1] = segments.pointAt(point).y();
 723     }
 724
 725     inline QKdPointTree::Traversal operator()(QKdPointTree::Node &node, int depth)
 726     {
 727         if (m_result != -1)
 728             return QKdPointTree::TraverseNone;
 729
 730         const QPointF &nodePoint = m_segments->pointAt(node.point);
 731
 732         const qreal pivotComponents[] = { nodePoint.x(), nodePoint.y() };
 733
 734         const qreal pivot = pivotComponents[depth & 1];
 735         const qreal value = pointComponents[depth & 1];
 736
 737         if (fuzzyIsNull(pivot - value)) {
 738             const qreal pivot2 = pivotComponents[(depth + 1) & 1];
 739             const qreal value2 = pointComponents[(depth + 1) & 1];
 740
 741             if (fuzzyIsNull(pivot2 - value2)) {
 742                 if (node.id < 0)
 743                     node.id = m_tree->nextId();
 744
 745                 m_result = node.id;
 746                 return QKdPointTree::TraverseNone;
 747             } else
 748                 return QKdPointTree::TraverseBoth;
 749         } else if (value < pivot) {
 750             return QKdPointTree::TraverseLeft;
 751         } else {
 752             return QKdPointTree::TraverseRight;
 753         }
 754     }
 755
 756     int result() const
 757     {
 758         return m_result;
 759     }
 760
 761 private:
 762     int m_point;
 763     qreal pointComponents[2];
 764     int m_result;
 765     const QPathSegments *m_segments;
 766     QKdPointTree *m_tree;
 767 };
 768
 769 // merge all points that are within qFuzzyCompare range of each other
 770 void QPathSegments::mergePoints()
 771 {
 772     QKdPointTree tree(*this);
 773
 774     if (tree.rootNode()) {
 775         QDataBuffer<QPointF> mergedPoints(points());
 776         QDataBuffer<int> pointIndices(points());
 777
 778         for (int i = 0; i < points(); ++i) {
 779             QKdPointFinder finder(i, *this, tree);
 780             QT_PREPEND_NAMESPACE(qTraverseKdPointTree<QKdPointFinder>)(*tree.rootNode(), finder);
 781
 782             Q_ASSERT(finder.result() != -1);
 783
 784             if (finder.result() >= mergedPoints.size())
 785                 mergedPoints << m_points.at(i);
 786
 787             pointIndices << finder.result();
 788         }
 789
 790         for (int i = 0; i < m_segments.size(); ++i) {
 791             m_segments.at(i).va = pointIndices.at(m_segments.at(i).va);
 792             m_segments.at(i).vb = pointIndices.at(m_segments.at(i).vb);
 793         }
 794
 795         for (int i = 0; i < m_intersections.size(); ++i)
 796             m_intersections.at(i).vertex = pointIndices.at(m_intersections.at(i).vertex);
 797
 798         m_points.swap(mergedPoints);
 799     }
 800 }
 801
 802 void QWingedEdge::intersectAndAdd()
 803 {
 804     QIntersectionFinder finder;
 805     finder.produceIntersections(m_segments);
 806
 807     m_segments.mergePoints();
 808
 809     for (int i = 0; i < m_segments.points(); ++i)
 810         addVertex(m_segments.pointAt(i));
 811
 812     QDataBuffer<QPathSegments::Intersection> intersections(m_segments.segments());
 813     for (int i = 0; i < m_segments.segments(); ++i) {
 814         intersections.reset();
 815
 816         int pathId = m_segments.pathId(i);
 817
 818         const QPathSegments::Intersection *isect = m_segments.intersectionAt(i);
 819         while (isect) {
 820             intersections << *isect;
 821
 822             if (isect->next) {
 823                 isect += isect->next;
 824             } else {
 825                 isect = 0;
 826             }
 827         }
 828
 829         qSort(intersections.data(), intersections.data() + intersections.size());
 830
 831         int first = m_segments.segmentAt(i).va;
 832         int second = m_segments.segmentAt(i).vb;
 833
 834         int last = first;
 835         for (int j = 0; j < intersections.size(); ++j) {
 836             const QPathSegments::Intersection &isect = intersections.at(j);
 837
 838             QPathEdge *ep = edge(addEdge(last, isect.vertex));
 839
 840             if (ep) {
 841                 const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(isect.vertex).y() ? 1 : -1;
 842                 if (pathId == 0)
 843                     ep->windingA += dir;
 844                 else
 845                     ep->windingB += dir;
 846             }
 847
 848             last = isect.vertex;
 849         }
 850
 851         QPathEdge *ep = edge(addEdge(last, second));
 852
 853         if (ep) {
 854             const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(second).y() ? 1 : -1;
 855             if (pathId == 0)
 856                 ep->windingA += dir;
 857             else
 858                 ep->windingB += dir;
 859         }
 860     }
 861 }
 862
 863 QWingedEdge::QWingedEdge() :
 864     m_edges(0),
 865     m_vertices(0),
 866     m_segments(0)
 867 {
 868 }
 869
 870 QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip) :
 871     m_edges(subject.elementCount()),
 872     m_vertices(subject.elementCount()),
 873     m_segments(subject.elementCount())
 874 {
 875     m_segments.setPath(subject);
 876     m_segments.addPath(clip);
 877
 878     intersectAndAdd();
 879 }
 880
 881 QWingedEdge::TraversalStatus QWingedEdge::next(const QWingedEdge::TraversalStatus &status) const
 882 {
 883     const QPathEdge *sp = edge(status.edge);
 884     Q_ASSERT(sp);
 885
 886     TraversalStatus result;
 887     result.edge = sp->next(status.traversal, status.direction);
 888     result.traversal = status.traversal;
 889     result.direction = status.direction;
 890
 891     const QPathEdge *rp = edge(result.edge);
 892     Q_ASSERT(rp);
 893
 894     if (sp->vertex(status.direction) == rp->vertex(status.direction))
 895         result.flip();
 896
 897     return result;
 898 }
 899
 900 static bool isLine(const QBezier &bezier)
 901 {
 902     const bool equal_1_2 = comparePoints(bezier.pt1(), bezier.pt2());
 903     const bool equal_2_3 = comparePoints(bezier.pt2(), bezier.pt3());
 904     const bool equal_3_4 = comparePoints(bezier.pt3(), bezier.pt4());
 905
 906     // point?
 907     if (equal_1_2 && equal_2_3 && equal_3_4)
 908         return true;
 909
 910     if (comparePoints(bezier.pt1(), bezier.pt4()))
 911         return equal_1_2 || equal_3_4;
 912
 913     return (equal_1_2 && equal_3_4) || (equal_1_2 && equal_2_3) || (equal_2_3 && equal_3_4);
 914 }
 915
 916 void QPathSegments::setPath(const QPainterPath &path)
 917 {
 918     m_points.reset();
 919     m_intersections.reset();
 920     m_segments.reset();
 921
 922     m_pathId = 0;
 923
 924     addPath(path);
 925 }
 926
 927 void QPathSegments::addPath(const QPainterPath &path)
 928 {
 929     int firstSegment = m_segments.size();
 930
 931     bool hasMoveTo = false;
 932     int lastMoveTo = 0;
 933     int last = 0;
 934     for (int i = 0; i < path.elementCount(); ++i) {
 935         int current = m_points.size();
 936
 937         QPointF currentPoint;
 938         if (path.elementAt(i).type == QPainterPath::CurveToElement)
 939             currentPoint = path.elementAt(i+2);
 940         else
 941             currentPoint = path.elementAt(i);
 942
 943         if (i > 0 && comparePoints(m_points.at(lastMoveTo), currentPoint))
 944             current = lastMoveTo;
 945         else
 946             m_points << currentPoint;
 947
 948         switch (path.elementAt(i).type) {
 949         case QPainterPath::MoveToElement:
 950             if (hasMoveTo && last != lastMoveTo && !comparePoints(m_points.at(last), m_points.at(lastMoveTo)))
 951                 m_segments << Segment(m_pathId, last, lastMoveTo);
 952             hasMoveTo = true;
 953             last = lastMoveTo = current;
 954             break;
 955         case QPainterPath::LineToElement:
 956             m_segments << Segment(m_pathId, last, current);
 957             last = current;
 958             break;
 959         case QPainterPath::CurveToElement:
 960             {
 961                 QBezier bezier = QBezier::fromPoints(m_points.at(last), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2));
 962                 if (isLine(bezier)) {
 963                     m_segments << Segment(m_pathId, last, current);
 964                 } else {
 965                     QRectF bounds = bezier.bounds();
 966
 967                     // threshold based on similar algorithm as in qtriangulatingstroker.cpp
 968                     int threshold = qMin<float>(64, qMax(bounds.width(), bounds.height()) * (2 * qreal(3.14) / 6));
 969
 970                     if (threshold < 3) threshold = 3;
 971                     qreal one_over_threshold_minus_1 = qreal(1) / (threshold - 1);
 972
 973                     for (int t = 1; t < threshold - 1; ++t) {
 974                         currentPoint = bezier.pointAt(t * one_over_threshold_minus_1);
 975
 976                         int index = m_points.size();
 977                         m_segments << Segment(m_pathId, last, index);
 978                         last = index;
 979
 980                         m_points << currentPoint;
 981                     }
 982
 983                     m_segments << Segment(m_pathId, last, current);
 984                 }
 985             }
 986             last = current;
 987             i += 2;
 988             break;
 989         default:
 990             Q_ASSERT(false);
 991             break;
 992         }
 993     }
 994
 995     if (hasMoveTo && last != lastMoveTo && !comparePoints(m_points.at(last), m_points.at(lastMoveTo)))
 996         m_segments << Segment(m_pathId, last, lastMoveTo);
 997
 998     for (int i = firstSegment; i < m_segments.size(); ++i) {
 999         const QLineF line = lineAt(i);
1000
1001         qreal x1 = line.p1().x();
1002         qreal y1 = line.p1().y();
1003         qreal x2 = line.p2().x();
1004         qreal y2 = line.p2().y();
1005
1006         if (x2 < x1)
1007             qSwap(x1, x2);
1008         if (y2 < y1)
1009             qSwap(y1, y2);
1010
1011         m_segments.at(i).bounds = QRectF(x1, y1, x2 - x1, y2 - y1);
1012     }
1013
1014     ++m_pathId;
1015 }
1016
1017 qreal QWingedEdge::delta(int vertex, int a, int b) const
1018 {
1019     const QPathEdge *ap = edge(a);
1020     const QPathEdge *bp = edge(b);
1021
1022     double a_angle = ap->angle;
1023     double b_angle = bp->angle;
1024
1025     if (vertex == ap->second)
1026         a_angle = ap->invAngle;
1027
1028     if (vertex == bp->second)
1029         b_angle = bp->invAngle;
1030
1031     double result = b_angle - a_angle;
1032
1033     if (result >= 128.)
1034         return result - 128.;
1035     else if (result < 0)
1036         return result + 128.;
1037     else
1038         return result;
1039 }
1040
1041 static inline QPointF midPoint(const QWingedEdge &list, int ei)
1042 {
1043     const QPathEdge *ep = list.edge(ei);
1044     Q_ASSERT(ep);
1045
1046     const QPointF a = *list.vertex(ep->first);
1047     const QPointF b = *list.vertex(ep->second);
1048     return a + 0.5 * (b - a);
1049 }
1050
1051 QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const
1052 {
1053     const QPathVertex *vp = vertex(vi);
1054
1055     Q_ASSERT(vp);
1056     Q_ASSERT(ei >= 0);
1057     Q_ASSERT(vp->edge >= 0);
1058
1059     int position = vp->edge;
1060     qreal d = 128.;
1061
1062     TraversalStatus status;
1063     status.direction = edge(vp->edge)->directionTo(vi);
1064     status.traversal = QPathEdge::RightTraversal;
1065     status.edge = vp->edge;
1066
1067 #ifdef QDEBUG_CLIPPER
1068     const QPathEdge *ep = edge(ei);
1069     qDebug() << "Finding insert status for edge" << ei << "at vertex" << QPointF(*vp) << ", angles: " << ep->angle << ep->invAngle;
1070 #endif
1071
1072     do {
1073         status = next(status);
1074         status.flip();
1075
1076         Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi);
1077         qreal d2 = delta(vi, ei, status.edge);
1078
1079 #ifdef QDEBUG_CLIPPER
1080         const QPathEdge *op = edge(status.edge);
1081         qDebug() << "Delta to edge" << status.edge << d2 << ", angles: " << op->angle << op->invAngle;
1082 #endif
1083
1084         if (d2 < d) {
1085             position = status.edge;
1086             d = d2;
1087         }
1088     } while (status.edge != vp->edge);
1089
1090     status.traversal = QPathEdge::LeftTraversal;
1091     status.direction = QPathEdge::Forward;
1092     status.edge = position;
1093
1094     if (edge(status.edge)->vertex(status.direction) != vi)
1095         status.flip();
1096
1097 #ifdef QDEBUG_CLIPPER
1098     qDebug() << "Inserting edge" << ei << "to" << (status.traversal == QPathEdge::LeftTraversal ? "left" : "right") << "of edge" << status.edge;
1099 #endif
1100
1101     Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi);
1102
1103     return status;
1104 }
1105
1106 void QWingedEdge::removeEdge(int ei)
1107 {
1108     QPathEdge *ep = edge(ei);
1109
1110     TraversalStatus status;
1111     status.direction = QPathEdge::Forward;
1112     status.traversal = QPathEdge::RightTraversal;
1113     status.edge = ei;
1114
1115     TraversalStatus forwardRight = next(status);
1116     forwardRight.flipDirection();
1117
1118     status.traversal = QPathEdge::LeftTraversal;
1119     TraversalStatus forwardLeft = next(status);
1120     forwardLeft.flipDirection();
1121
1122     status.direction = QPathEdge::Backward;
1123     TraversalStatus backwardLeft = next(status);
1124     backwardLeft.flipDirection();
1125
1126     status.traversal = QPathEdge::RightTraversal;
1127     TraversalStatus backwardRight = next(status);
1128     backwardRight.flipDirection();
1129
1130     edge(forwardRight.edge)->setNext(forwardRight.traversal, forwardRight.direction, forwardLeft.edge);
1131     edge(forwardLeft.edge)->setNext(forwardLeft.traversal, forwardLeft.direction, forwardRight.edge);
1132
1133     edge(backwardRight.edge)->setNext(backwardRight.traversal, backwardRight.direction, backwardLeft.edge);
1134     edge(backwardLeft.edge)->setNext(backwardLeft.traversal, backwardLeft.direction, backwardRight.edge);
1135
1136     ep->setNext(QPathEdge::Forward, ei);
1137     ep->setNext(QPathEdge::Backward, ei);
1138
1139     QPathVertex *a = vertex(ep->first);
1140     QPathVertex *b = vertex(ep->second);
1141
1142     a->edge = backwardRight.edge;
1143     b->edge = forwardRight.edge;
1144 }
1145
1146 static int commonEdge(const QWingedEdge &list, int a, int b)
1147 {
1148     const QPathVertex *ap = list.vertex(a);
1149     Q_ASSERT(ap);
1150
1151     const QPathVertex *bp = list.vertex(b);
1152     Q_ASSERT(bp);
1153
1154     if (ap->edge < 0 || bp->edge < 0)
1155         return -1;
1156
1157     QWingedEdge::TraversalStatus status;
1158     status.edge = ap->edge;
1159     status.direction = list.edge(status.edge)->directionTo(a);
1160     status.traversal = QPathEdge::RightTraversal;
1161
1162     do {
1163         const QPathEdge *ep = list.edge(status.edge);
1164
1165         if ((ep->first == a && ep->second == b)
1166             || (ep->first == b && ep->second == a))
1167             return status.edge;
1168
1169         status = list.next(status);
1170         status.flip();
1171     } while (status.edge != ap->edge);
1172
1173     return -1;
1174 }
1175
1176 static double computeAngle(const QPointF &v)
1177 {
1178 #if 1
1179     if (v.x() == 0) {
1180         return v.y() <= 0 ? 0 : 64.;
1181     } else if (v.y() == 0) {
1182         return v.x() <= 0 ? 32. : 96.;
1183     }
1184
1185     double vx = v.x();
1186     double vy = v.y();
1187     normalize(vx, vy);
1188     if (vy < 0) {
1189         if (vx < 0) { // 0 - 32
1190             return -32. * vx;
1191         } else { // 96 - 128
1192             return 128. - 32. * vx;
1193         }
1194     } else { // 32 - 96
1195         return 64. + 32. * vx;
1196     }
1197 #else
1198     // doesn't seem to be robust enough
1199     return qAtan2(v.x(), v.y()) + Q_PI;
1200 #endif
1201 }
1202
1203 int QWingedEdge::addEdge(const QPointF &a, const QPointF &b)
1204 {
1205     int fi = insert(a);
1206     int si = insert(b);
1207
1208     return addEdge(fi, si);
1209 }
1210
1211 int QWingedEdge::addEdge(int fi, int si)
1212 {
1213     if (fi == si)
1214         return -1;
1215
1216     int common = commonEdge(*this, fi, si);
1217     if (common >= 0)
1218         return common;
1219
1220     m_edges << QPathEdge(fi, si);
1221
1222     int ei = m_edges.size() - 1;
1223
1224     QPathVertex *fp = vertex(fi);
1225     QPathVertex *sp = vertex(si);
1226
1227     QPathEdge *ep = edge(ei);
1228
1229     const QPointF tangent = QPointF(*sp) - QPointF(*fp);
1230     ep->angle = computeAngle(tangent);
1231     ep->invAngle = ep->angle + 64;
1232     if (ep->invAngle >= 128)
1233         ep->invAngle -= 128;
1234
1235     QPathVertex *vertices[2] = { fp, sp };
1236     QPathEdge::Direction dirs[2] = { QPathEdge::Backward, QPathEdge::Forward };
1237
1238 #ifdef QDEBUG_CLIPPER
1239     printf("** Adding edge %d / vertices: %.07f %.07f, %.07f %.07f\n", ei, fp->x, fp->y, sp->x, sp->y);
1240 #endif
1241
1242     for (int i = 0; i < 2; ++i) {
1243         QPathVertex *vp = vertices[i];
1244         if (vp->edge < 0) {
1245             vp->edge = ei;
1246             ep->setNext(dirs[i], ei);
1247         } else {
1248             int vi = ep->vertex(dirs[i]);
1249             Q_ASSERT(vertex(vi) == vertices[i]);
1250
1251             TraversalStatus os = findInsertStatus(vi, ei);
1252             QPathEdge *op = edge(os.edge);
1253
1254             Q_ASSERT(vertex(op->vertex(os.direction)) == vertices[i]);
1255
1256             TraversalStatus ns = next(os);
1257             ns.flipDirection();
1258             QPathEdge *np = edge(ns.edge);
1259
1260             op->setNext(os.traversal, os.direction, ei);
1261             np->setNext(ns.traversal, ns.direction, ei);
1262
1263             int oe = os.edge;
1264             int ne = ns.edge;
1265
1266             os = next(os);
1267             ns = next(ns);
1268
1269             os.flipDirection();
1270             ns.flipDirection();
1271
1272             Q_ASSERT(os.edge == ei);
1273             Q_ASSERT(ns.edge == ei);
1274
1275             ep->setNext(os.traversal, os.direction, oe);
1276             ep->setNext(ns.traversal, ns.direction, ne);
1277         }
1278     }
1279
1280     Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Forward) >= 0);
1281     Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Backward) >= 0);
1282     Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Forward) >= 0);
1283     Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Backward) >= 0);
1284
1285     return ei;
1286 }
1287
1288 int QWingedEdge::insert(const QPathVertex &vertex)
1289 {
1290     if (!m_vertices.isEmpty()) {
1291         const QPathVertex &last = m_vertices.last();
1292         if (vertex.x == last.x && vertex.y == last.y)
1293             return m_vertices.size() - 1;
1294
1295         for (int i = 0; i < m_vertices.size(); ++i) {
1296             const QPathVertex &v = m_vertices.at(i);
1297             if (qFuzzyCompare(v.x, vertex.x) && qFuzzyCompare(v.y, vertex.y)) {
1298                 return i;
1299             }
1300         }
1301     }
1302
1303     m_vertices << vertex;
1304     return m_vertices.size() - 1;
1305 }
1306
1307 static void addLineTo(QPainterPath &path, const QPointF &point)
1308 {
1309     const int elementCount = path.elementCount();
1310     if (elementCount >= 2) {
1311         const QPainterPath::Element &middle = path.elementAt(elementCount - 1);
1312         if (middle.type == QPainterPath::LineToElement) {
1313             const QPointF first = path.elementAt(elementCount - 2);
1314             const QPointF d1 = point - first;
1315             const QPointF d2 = middle - first;
1316
1317             const QPointF p(-d1.y(), d1.x());
1318
1319             if (qFuzzyIsNull(dot(p, d2))) {
1320                 path.setElementPositionAt(elementCount - 1, point.x(), point.y());
1321                 return;
1322             }
1323         }
1324     }
1325
1326     path.lineTo(point);
1327 }
1328
1329 static void add(QPainterPath &path, const QWingedEdge &list, int edge, QPathEdge::Traversal traversal)
1330 {
1331     QWingedEdge::TraversalStatus status;
1332     status.edge = edge;
1333     status.traversal = traversal;
1334     status.direction = QPathEdge::Forward;
1335
1336     path.moveTo(*list.vertex(list.edge(edge)->first));
1337
1338     do {
1339         const QPathEdge *ep = list.edge(status.edge);
1340
1341         addLineTo(path, *list.vertex(ep->vertex(status.direction)));
1342
1343         if (status.traversal == QPathEdge::LeftTraversal)
1344             ep->flag &= ~16;
1345         else
1346             ep->flag &= ~32;
1347
1348         status = list.next(status);
1349     } while (status.edge != edge);
1350 }
1351
1352 void QWingedEdge::simplify()
1353 {
1354     for (int i = 0; i < edgeCount(); ++i) {
1355         const QPathEdge *ep = edge(i);
1356
1357         // if both sides are part of the inside then we can collapse the edge
1358         int flag = 0x3 << 4;
1359         if ((ep->flag & flag) == flag) {
1360             removeEdge(i);
1361
1362             ep->flag &= ~flag;
1363         }
1364     }
1365 }
1366
1367 QPainterPath QWingedEdge::toPath() const
1368 {
1369     QPainterPath path;
1370
1371     for (int i = 0; i < edgeCount(); ++i) {
1372         const QPathEdge *ep = edge(i);
1373
1374         if (ep->flag & 16) {
1375             add(path, *this, i, QPathEdge::LeftTraversal);
1376         }
1377
1378         if (ep->flag & 32)
1379             add(path, *this, i, QPathEdge::RightTraversal);
1380     }
1381
1382     return path;
1383 }
1384
1385 bool QPathClipper::intersect()
1386 {
1387     if (subjectPath == clipPath)
1388         return true;
1389
1390     QRectF r1 = subjectPath.controlPointRect();
1391     QRectF r2 = clipPath.controlPointRect();
1392     if (qMax(r1.x(), r2.x()) > qMin(r1.x() + r1.width(), r2.x() + r2.width()) ||
1393         qMax(r1.y(), r2.y()) > qMin(r1.y() + r1.height(), r2.y() + r2.height())) {
1394         // no way we could intersect
1395         return false;
1396     }
1397
1398     bool subjectIsRect = pathToRect(subjectPath);
1399     bool clipIsRect = pathToRect(clipPath);
1400
1401     if (subjectIsRect && clipIsRect)
1402         return true;
1403     else if (subjectIsRect)
1404         return clipPath.intersects(r1);
1405     else if (clipIsRect)
1406         return subjectPath.intersects(r2);
1407
1408     QPathSegments a(subjectPath.elementCount());
1409     a.setPath(subjectPath);
1410     QPathSegments b(clipPath.elementCount());
1411     b.setPath(clipPath);
1412
1413     QIntersectionFinder finder;
1414     if (finder.hasIntersections(a, b))
1415         return true;
1416
1417     for (int i = 0; i < clipPath.elementCount(); ++i) {
1418         if (clipPath.elementAt(i).type == QPainterPath::MoveToElement) {
1419             const QPointF point = clipPath.elementAt(i);
1420             if (r1.contains(point) && subjectPath.contains(point))
1421                 return true;
1422         }
1423     }
1424
1425     for (int i = 0; i < subjectPath.elementCount(); ++i) {
1426         if (subjectPath.elementAt(i).type == QPainterPath::MoveToElement) {
1427             const QPointF point = subjectPath.elementAt(i);
1428             if (r2.contains(point) && clipPath.contains(point))
1429                 return true;
1430         }
1431     }
1432
1433     return false;
1434 }
1435
1436 bool QPathClipper::contains()
1437 {
1438     if (subjectPath == clipPath)
1439         return false;
1440
1441     QRectF r1 = subjectPath.controlPointRect();
1442     QRectF r2 = clipPath.controlPointRect();
1443     if (qMax(r1.x(), r2.x()) > qMin(r1.x() + r1.width(), r2.x() + r2.width()) ||
1444         qMax(r1.y(), r2.y()) > qMin(r1.y() + r1.height(), r2.y() + r2.height())) {
1445         // no intersection -> not contained
1446         return false;
1447     }
1448
1449     bool clipIsRect = pathToRect(clipPath);
1450     if (clipIsRect)
1451         return subjectPath.contains(r2);
1452
1453     QPathSegments a(subjectPath.elementCount());
1454     a.setPath(subjectPath);
1455     QPathSegments b(clipPath.elementCount());
1456     b.setPath(clipPath);
1457
1458     QIntersectionFinder finder;
1459     if (finder.hasIntersections(a, b))
1460         return false;
1461
1462     for (int i = 0; i < clipPath.elementCount(); ++i) {
1463         if (clipPath.elementAt(i).type == QPainterPath::MoveToElement) {
1464             const QPointF point = clipPath.elementAt(i);
1465             if (!r1.contains(point) || !subjectPath.contains(point))
1466                 return false;
1467         }
1468     }
1469
1470     return true;
1471 }
1472
1473 QPathClipper::QPathClipper(const QPainterPath &subject,
1474                            const QPainterPath &clip)
1475     : subjectPath(subject)
1476     , clipPath(clip)
1477 {
1478     aMask = subjectPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1;
1479     bMask = clipPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1;
1480 }
1481
1482 template <typename Iterator, typename Equality>
1483 Iterator qRemoveDuplicates(Iterator begin, Iterator end, Equality eq)
1484 {
1485     if (begin == end)
1486         return end;
1487
1488     Iterator last = begin;
1489     ++begin;
1490     Iterator insert = begin;
1491     for (Iterator it = begin; it != end; ++it) {
1492         if (!eq(*it, *last)) {
1493             *insert++ = *it;
1494             last = it;
1495         }
1496     }
1497
1498     return insert;
1499 }
1500
1501 static void clear(QWingedEdge& list, int edge, QPathEdge::Traversal traversal)
1502 {
1503     QWingedEdge::TraversalStatus status;
1504     status.edge = edge;
1505     status.traversal = traversal;
1506     status.direction = QPathEdge::Forward;
1507
1508     do {
1509         if (status.traversal == QPathEdge::LeftTraversal)
1510             list.edge(status.edge)->flag |= 1;
1511         else
1512             list.edge(status.edge)->flag |= 2;
1513
1514         status = list.next(status);
1515     } while (status.edge != edge);
1516 }
1517
1518 template <typename InputIterator>
1519 InputIterator qFuzzyFind(InputIterator first, InputIterator last, qreal val)
1520 {
1521     while (first != last && !QT_PREPEND_NAMESPACE(qFuzzyCompare)(qreal(*first), qreal(val)))
1522         ++first;
1523     return first;
1524 }
1525
1526 static bool fuzzyCompare(qreal a, qreal b)
1527 {
1528     return qFuzzyCompare(a, b);
1529 }
1530
1531 bool QPathClipper::pathToRect(const QPainterPath &path, QRectF *rect)
1532 {
1533     if (path.elementCount() != 5)
1534         return false;
1535
1536     const bool mightBeRect = path.elementAt(0).isMoveTo()
1537         && path.elementAt(1).isLineTo()
1538         && path.elementAt(2).isLineTo()
1539         && path.elementAt(3).isLineTo()
1540         && path.elementAt(4).isLineTo();
1541
1542     if (!mightBeRect)
1543         return false;
1544
1545     const qreal x1 = path.elementAt(0).x;
1546     const qreal y1 = path.elementAt(0).y;
1547
1548     const qreal x2 = path.elementAt(1).x;
1549     const qreal y2 = path.elementAt(2).y;
1550
1551     if (path.elementAt(1).y != y1)
1552         return false;
1553
1554     if (path.elementAt(2).x != x2)
1555         return false;
1556
1557     if (path.elementAt(3).x != x1 || path.elementAt(3).y != y2)
1558         return false;
1559
1560     if (path.elementAt(4).x != x1 || path.elementAt(4).y != y1)
1561         return false;
1562
1563     if (rect)
1564         rect->setCoords(x1, y1, x2, y2);
1565
1566     return true;
1567 }
1568
1569
1570 QPainterPath QPathClipper::clip(Operation operation)
1571 {
1572     op = operation;
1573
1574     if (op != Simplify) {
1575         if (subjectPath == clipPath)
1576             return op == BoolSub ? QPainterPath() : subjectPath;
1577
1578         bool subjectIsRect = pathToRect(subjectPath, 0);
1579         bool clipIsRect = pathToRect(clipPath, 0);
1580
1581         const QRectF clipBounds = clipPath.boundingRect();
1582         const QRectF subjectBounds = subjectPath.boundingRect();
1583
1584         if (!clipBounds.intersects(subjectBounds)) {
1585             switch (op) {
1586             case BoolSub:
1587                 return subjectPath;
1588             case BoolAnd:
1589                 return QPainterPath();
1590             case BoolOr: {
1591                 QPainterPath result = subjectPath;
1592                 if (result.fillRule() == clipPath.fillRule()) {
1593                     result.addPath(clipPath);
1594                 } else if (result.fillRule() == Qt::WindingFill) {
1595                     result = result.simplified();
1596                     result.addPath(clipPath);
1597                 } else {
1598                     result.addPath(clipPath.simplified());
1599                 }
1600                 return result;
1601              }
1602             default:
1603                 break;
1604             }
1605         }
1606
1607         if (clipBounds.contains(subjectBounds)) {
1608             if (clipIsRect) {
1609                 switch (op) {
1610                 case BoolSub:
1611                     return QPainterPath();
1612                 case BoolAnd:
1613                     return subjectPath;
1614                 case BoolOr:
1615                     return clipPath;
1616                 default:
1617                     break;
1618                 }
1619             }
1620         } else if (subjectBounds.contains(clipBounds)) {
1621             if (subjectIsRect) {
1622                 switch (op) {
1623                 case BoolSub:
1624                     if (clipPath.fillRule() == Qt::OddEvenFill) {
1625                         QPainterPath result = clipPath;
1626                         result.addRect(subjectBounds);
1627                         return result;
1628                     } else {
1629                         QPainterPath result = clipPath.simplified();
1630                         result.addRect(subjectBounds);
1631                         return result;
1632                     }
1633                 case BoolAnd:
1634                     return clipPath;
1635                 case BoolOr:
1636                     return subjectPath;
1637                 default:
1638                     break;
1639                 }
1640             }
1641         }
1642
1643         if (op == BoolAnd) {
1644             if (subjectIsRect)
1645                 return intersect(clipPath, subjectBounds);
1646             else if (clipIsRect)
1647                 return intersect(subjectPath, clipBounds);
1648         }
1649     }
1650
1651     QWingedEdge list(subjectPath, clipPath);
1652
1653     doClip(list, ClipMode);
1654
1655     QPainterPath path = list.toPath();
1656     return path;
1657 }
1658
1659 bool QPathClipper::doClip(QWingedEdge &list, ClipperMode mode)
1660 {
1661     QVector<qreal> y_coords;
1662     y_coords.reserve(list.vertexCount());
1663     for (int i = 0; i < list.vertexCount(); ++i)
1664         y_coords << list.vertex(i)->y;
1665
1666     qSort(y_coords.begin(), y_coords.end());
1667     y_coords.resize(qRemoveDuplicates(y_coords.begin(), y_coords.end(), fuzzyCompare) - y_coords.begin());
1668
1669 #ifdef QDEBUG_CLIPPER
1670     printf("sorted y coords:\n");
1671     for (int i = 0; i < y_coords.size(); ++i) {
1672         printf("%.9f\n", y_coords[i]);
1673     }
1674 #endif
1675
1676     bool found;
1677     do {
1678         found = false;
1679         int index = 0;
1680         qreal maxHeight = 0;
1681         for (int i = 0; i < list.edgeCount(); ++i) {
1682             QPathEdge *edge = list.edge(i);
1683
1684             // have both sides of this edge already been handled?
1685             if ((edge->flag & 0x3) == 0x3)
1686                 continue;
1687
1688             QPathVertex *a = list.vertex(edge->first);
1689             QPathVertex *b = list.vertex(edge->second);
1690
1691             if (qFuzzyCompare(a->y, b->y))
1692                 continue;
1693
1694             found = true;
1695
1696             qreal height = qAbs(a->y - b->y);
1697             if (height > maxHeight) {
1698                 index = i;
1699                 maxHeight = height;
1700             }
1701         }
1702
1703         if (found) {
1704             QPathEdge *edge = list.edge(index);
1705
1706             QPathVertex *a = list.vertex(edge->first);
1707             QPathVertex *b = list.vertex(edge->second);
1708
1709             // FIXME: this can be optimized by using binary search
1710             const int first = qFuzzyFind(y_coords.begin(), y_coords.end(), qMin(a->y, b->y)) - y_coords.begin();
1711             const int last = qFuzzyFind(y_coords.begin() + first, y_coords.end(), qMax(a->y, b->y)) - y_coords.begin();
1712
1713             Q_ASSERT(first < y_coords.size() - 1);
1714             Q_ASSERT(last < y_coords.size());
1715
1716             qreal bestY = 0.5 * (y_coords[first] + y_coords[first+1]);
1717             qreal biggestGap = y_coords[first+1] - y_coords[first];
1718
1719             for (int i = first + 1; i < last; ++i) {
1720                 qreal gap = y_coords[i+1] - y_coords[i];
1721
1722                 if (gap > biggestGap) {
1723                     bestY = 0.5 * (y_coords[i] + y_coords[i+1]);
1724                     biggestGap = gap;
1725                 }
1726             }
1727
1728 #ifdef QDEBUG_CLIPPER
1729             printf("y: %.9f, gap: %.9f\n", bestY, biggestGap);
1730 #endif
1731
1732             if (handleCrossingEdges(list, bestY, mode) && mode == CheckMode)
1733                 return true;
1734
1735             edge->flag |= 0x3;
1736         }
1737     } while (found);
1738
1739     if (mode == ClipMode)
1740         list.simplify();
1741
1742     return false;
1743 }
1744
1745 static void traverse(QWingedEdge &list, int edge, QPathEdge::Traversal traversal)
1746 {
1747     QWingedEdge::TraversalStatus status;
1748     status.edge = edge;
1749     status.traversal = traversal;
1750     status.direction = QPathEdge::Forward;
1751
1752     do {
1753         int flag = status.traversal == QPathEdge::LeftTraversal ? 1 : 2;
1754
1755         QPathEdge *ep = list.edge(status.edge);
1756
1757         ep->flag |= (flag | (flag << 4));
1758
1759 #ifdef QDEBUG_CLIPPER
1760         qDebug() << "traverse: adding edge " << status.edge << ", mask:" << (flag << 4) <<ep->flag;
1761 #endif
1762
1763         status = list.next(status);
1764     } while (status.edge != edge);
1765 }
1766
1767 struct QCrossingEdge
1768 {
1769     int edge;
1770     qreal x;
1771
1772     bool operator<(const QCrossingEdge &edge) const
1773     {
1774         return x < edge.x;
1775     }
1776 };
1777
1778 static bool bool_op(bool a, bool b, QPathClipper::Operation op)
1779 {
1780     switch (op) {
1781     case QPathClipper::BoolAnd:
1782         return a && b;
1783     case QPathClipper::BoolOr: // fall-through
1784     case QPathClipper::Simplify:
1785         return a || b;
1786     case QPathClipper::BoolSub:
1787         return a && !b;
1788     default:
1789         Q_ASSERT(false);
1790         return false;
1791     }
1792 }
1793
1794 bool QWingedEdge::isInside(qreal x, qreal y) const
1795 {
1796     int winding = 0;
1797     for (int i = 0; i < edgeCount(); ++i) {
1798         const QPathEdge *ep = edge(i);
1799
1800         // left xor right
1801         int w = ((ep->flag >> 4) ^ (ep->flag >> 5)) & 1;
1802
1803         if (!w)
1804             continue;
1805
1806         QPointF a = *vertex(ep->first);
1807         QPointF b = *vertex(ep->second);
1808
1809         if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) {
1810             qreal intersectionX = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y());
1811
1812             if (intersectionX > x)
1813                 winding += w;
1814         }
1815     }
1816
1817     return winding & 1;
1818 }
1819
1820 static QVector<QCrossingEdge> findCrossings(const QWingedEdge &list, qreal y)
1821 {
1822     QVector<QCrossingEdge> crossings;
1823     for (int i = 0; i < list.edgeCount(); ++i) {
1824         const QPathEdge *edge = list.edge(i);
1825         QPointF a = *list.vertex(edge->first);
1826         QPointF b = *list.vertex(edge->second);
1827
1828         if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) {
1829             const qreal intersection = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y());
1830             const QCrossingEdge edge = { i, intersection };
1831             crossings << edge;
1832         }
1833     }
1834     return crossings;
1835 }
1836
1837 bool QPathClipper::handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode)
1838 {
1839     QVector<QCrossingEdge> crossings = findCrossings(list, y);
1840
1841     Q_ASSERT(!crossings.isEmpty());
1842     qSort(crossings.begin(), crossings.end());
1843
1844     int windingA = 0;
1845     int windingB = 0;
1846
1847     int windingD = 0;
1848
1849 #ifdef QDEBUG_CLIPPER
1850     qDebug() << "crossings:" << crossings.size();
1851 #endif
1852     for (int i = 0; i < crossings.size() - 1; ++i) {
1853         int ei = crossings.at(i).edge;
1854         const QPathEdge *edge = list.edge(ei);
1855
1856         windingA += edge->windingA;
1857         windingB += edge->windingB;
1858
1859         const bool hasLeft = (edge->flag >> 4) & 1;
1860         const bool hasRight = (edge->flag >> 4) & 2;
1861
1862         windingD += hasLeft ^ hasRight;
1863
1864         const bool inA = (windingA & aMask) != 0;
1865         const bool inB = (windingB & bMask) != 0;
1866         const bool inD = (windingD & 0x1) != 0;
1867
1868         const bool inside = bool_op(inA, inB, op);
1869         const bool add = inD ^ inside;
1870
1871 #ifdef QDEBUG_CLIPPER
1872         printf("y %f, x %f, inA: %d, inB: %d, inD: %d, inside: %d, flag: %x, bezier: %p, edge: %d\n", y, crossings.at(i).x, inA, inB, inD, inside, edge->flag, edge->bezier, ei);
1873 #endif
1874
1875         if (add) {
1876             if (mode == CheckMode)
1877                 return true;
1878
1879             qreal y0 = list.vertex(edge->first)->y;
1880             qreal y1 = list.vertex(edge->second)->y;
1881
1882             if (y0 < y1) {
1883                 if (!(edge->flag & 1))
1884                     traverse(list, ei, QPathEdge::LeftTraversal);
1885
1886                 if (!(edge->flag & 2))
1887                     clear(list, ei, QPathEdge::RightTraversal);
1888             } else {
1889                 if (!(edge->flag & 1))
1890                     clear(list, ei, QPathEdge::LeftTraversal);
1891
1892                 if (!(edge->flag & 2))
1893                     traverse(list, ei, QPathEdge::RightTraversal);
1894             }
1895
1896             ++windingD;
1897         } else {
1898             if (!(edge->flag & 1))
1899                 clear(list, ei, QPathEdge::LeftTraversal);
1900
1901             if (!(edge->flag & 2))
1902                 clear(list, ei, QPathEdge::RightTraversal);
1903         }
1904     }
1905
1906     return false;
1907 }
1908
1909 namespace {
1910
1911 QList<QPainterPath> toSubpaths(const QPainterPath &path)
1912 {
1913
1914     QList<QPainterPath> subpaths;
1915     if (path.isEmpty())
1916         return subpaths;
1917
1918     QPainterPath current;
1919     for (int i = 0; i < path.elementCount(); ++i) {
1920         const QPainterPath::Element &e = path.elementAt(i);
1921         switch (e.type) {
1922         case QPainterPath::MoveToElement:
1923             if (current.elementCount() > 1)
1924                 subpaths += current;
1925             current = QPainterPath();
1926             current.moveTo(e);
1927             break;
1928         case QPainterPath::LineToElement:
1929             current.lineTo(e);
1930             break;
1931         case QPainterPath::CurveToElement: {
1932             current.cubicTo(e, path.elementAt(i + 1), path.elementAt(i + 2));
1933             i+=2;
1934             break;
1935         }
1936         case QPainterPath::CurveToDataElement:
1937             Q_ASSERT(!"toSubpaths(), bad element type");
1938             break;
1939         }
1940     }
1941
1942     if (current.elementCount() > 1)
1943         subpaths << current;
1944
1945     return subpaths;
1946 }
1947
1948 enum Edge
1949 {
1950     Left, Top, Right, Bottom
1951 };
1952
1953 static bool isVertical(Edge edge)
1954 {
1955     return edge == Left || edge == Right;
1956 }
1957
1958 template <Edge edge>
1959 bool compare(const QPointF &p, qreal t)
1960 {
1961     switch (edge)
1962     {
1963     case Left:
1964         return p.x() < t;
1965     case Right:
1966         return p.x() > t;
1967     case Top:
1968         return p.y() < t;
1969     default:
1970         return p.y() > t;
1971     }
1972 }
1973
1974 template <Edge edge>
1975 QPointF intersectLine(const QPointF &a, const QPointF &b, qreal t)
1976 {
1977     QLineF line(a, b);
1978     switch (edge) {
1979     case Left: // fall-through
1980     case Right:
1981         return line.pointAt((t - a.x()) / (b.x() - a.x()));
1982     default:
1983         return line.pointAt((t - a.y()) / (b.y() - a.y()));
1984     }
1985 }
1986
1987 void addLine(QPainterPath &path, const QLineF &line)
1988 {
1989     if (path.elementCount() > 0)
1990         path.lineTo(line.p1());
1991     else
1992         path.moveTo(line.p1());
1993
1994     path.lineTo(line.p2());
1995 }
1996
1997 template <Edge edge>
1998 void clipLine(const QPointF &a, const QPointF &b, qreal t, QPainterPath &result)
1999 {
2000     bool outA = compare<edge>(a, t);
2001     bool outB = compare<edge>(b, t);
2002     if (outA && outB)
2003         return;
2004
2005     if (outA)
2006         addLine(result, QLineF(intersectLine<edge>(a, b, t), b));
2007     else if(outB)
2008         addLine(result, QLineF(a, intersectLine<edge>(a, b, t)));
2009     else
2010         addLine(result, QLineF(a, b));
2011 }
2012
2013 void addBezier(QPainterPath &path, const QBezier &bezier)
2014 {
2015     if (path.elementCount() > 0)
2016         path.lineTo(bezier.pt1());
2017     else
2018         path.moveTo(bezier.pt1());
2019
2020     path.cubicTo(bezier.pt2(), bezier.pt3(), bezier.pt4());
2021 }
2022
2023 template <Edge edge>
2024 void clipBezier(const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, qreal t, QPainterPath &result)
2025 {
2026     QBezier bezier = QBezier::fromPoints(a, b, c, d);
2027
2028     bool outA = compare<edge>(a, t);
2029     bool outB = compare<edge>(b, t);
2030     bool outC = compare<edge>(c, t);
2031     bool outD = compare<edge>(d, t);
2032
2033     int outCount = int(outA) + int(outB) + int(outC) + int(outD);
2034
2035     if (outCount == 4)
2036         return;
2037
2038     if (outCount == 0) {
2039         addBezier(result, bezier);
2040         return;
2041     }
2042
2043     QTransform flip = isVertical(edge) ? QTransform(0, 1, 1, 0, 0, 0) : QTransform();
2044     QBezier unflipped = bezier;
2045     QBezier flipped = bezier.mapBy(flip);
2046
2047     qreal t0 = 0, t1 = 1;
2048     int stationary = flipped.stationaryYPoints(t0, t1);
2049
2050     qreal segments[4];
2051     QPointF points[4];
2052     points[0] = unflipped.pt1();
2053     segments[0] = 0;
2054
2055     int segmentCount = 0;
2056     if (stationary > 0) {
2057         ++segmentCount;
2058         segments[segmentCount] = t0;
2059         points[segmentCount] = unflipped.pointAt(t0);
2060     }
2061     if (stationary > 1) {
2062         ++segmentCount;
2063         segments[segmentCount] = t1;
2064         points[segmentCount] = unflipped.pointAt(t1);
2065     }
2066     ++segmentCount;
2067     segments[segmentCount] = 1;
2068     points[segmentCount] = unflipped.pt4();
2069
2070     qreal lastIntersection = 0;
2071     for (int i = 0; i < segmentCount; ++i) {
2072         outA = compare<edge>(points[i], t);
2073         outB = compare<edge>(points[i+1], t);
2074
2075         if (outA != outB) {
2076             qreal intersection = flipped.tForY(segments[i], segments[i+1], t);
2077
2078             if (outB)
2079                 addBezier(result, unflipped.getSubRange(lastIntersection, intersection));
2080
2081             lastIntersection = intersection;
2082         }
2083     }
2084
2085     if (!outB)
2086         addBezier(result, unflipped.getSubRange(lastIntersection, 1));
2087 }
2088
2089 // clips a single subpath against a single edge
2090 template <Edge edge>
2091 QPainterPath clip(const QPainterPath &path, qreal t)
2092 {
2093     QPainterPath result;
2094     for (int i = 1; i < path.elementCount(); ++i) {
2095         const QPainterPath::Element &element = path.elementAt(i);
2096         Q_ASSERT(!element.isMoveTo());
2097         if (element.isLineTo()) {
2098             clipLine<edge>(path.elementAt(i-1), path.elementAt(i), t, result);
2099         } else {
2100             clipBezier<edge>(path.elementAt(i-1), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2), t, result);
2101             i += 2;
2102         }
2103     }
2104
2105     int last = path.elementCount() - 1;
2106     if (QPointF(path.elementAt(last)) != QPointF(path.elementAt(0)))
2107         clipLine<edge>(path.elementAt(last), path.elementAt(0), t, result);
2108
2109     return result;
2110 }
2111
2112 QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect)
2113 {
2114     QList<QPainterPath> subpaths = toSubpaths(path);
2115
2116     QPainterPath result;
2117     result.setFillRule(path.fillRule());
2118     for (int i = 0; i < subpaths.size(); ++i) {
2119         QPainterPath subPath = subpaths.at(i);
2120         QRectF bounds = subPath.boundingRect();
2121         if (bounds.intersects(rect)) {
2122             if (bounds.left() < rect.left())
2123                 subPath = clip<Left>(subPath, rect.left());
2124             if (bounds.right() > rect.right())
2125                 subPath = clip<Right>(subPath, rect.right());
2126
2127             bounds = subPath.boundingRect();
2128
2129             if (bounds.top() < rect.top())
2130                 subPath = clip<Top>(subPath, rect.top());
2131             if (bounds.bottom() > rect.bottom())
2132                 subPath = clip<Bottom>(subPath, rect.bottom());
2133
2134             if (subPath.elementCount() > 1)
2135                 result.addPath(subPath);
2136         }
2137     }
2138     return result;
2139 }
2140
2141 }
2142
2143 QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect)
2144 {
2145     return intersectPath(path, rect);
2146 }
2147
2148 QT_END_NAMESPACE