src/gui/painting/qpathclipper.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtGui module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  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                     break;
1634                 case BoolAnd:
1635                     return clipPath;
1636                 case BoolOr:
1637                     return subjectPath;
1638                 default:
1639                     break;
1640                 }
1641             }
1642         }
1643
1644         if (op == BoolAnd) {
1645             if (subjectIsRect)
1646                 return intersect(clipPath, subjectBounds);
1647             else if (clipIsRect)
1648                 return intersect(subjectPath, clipBounds);
1649         }
1650     }
1651
1652     QWingedEdge list(subjectPath, clipPath);
1653
1654     doClip(list, ClipMode);
1655
1656     QPainterPath path = list.toPath();
1657     return path;
1658 }
1659
1660 bool QPathClipper::doClip(QWingedEdge &list, ClipperMode mode)
1661 {
1662     QVector<qreal> y_coords;
1663     y_coords.reserve(list.vertexCount());
1664     for (int i = 0; i < list.vertexCount(); ++i)
1665         y_coords << list.vertex(i)->y;
1666
1667     qSort(y_coords.begin(), y_coords.end());
1668     y_coords.resize(qRemoveDuplicates(y_coords.begin(), y_coords.end(), fuzzyCompare) - y_coords.begin());
1669
1670 #ifdef QDEBUG_CLIPPER
1671     printf("sorted y coords:\n");
1672     for (int i = 0; i < y_coords.size(); ++i) {
1673         printf("%.9f\n", y_coords[i]);
1674     }
1675 #endif
1676
1677     bool found;
1678     do {
1679         found = false;
1680         int index = 0;
1681         qreal maxHeight = 0;
1682         for (int i = 0; i < list.edgeCount(); ++i) {
1683             QPathEdge *edge = list.edge(i);
1684
1685             // have both sides of this edge already been handled?
1686             if ((edge->flag & 0x3) == 0x3)
1687                 continue;
1688
1689             QPathVertex *a = list.vertex(edge->first);
1690             QPathVertex *b = list.vertex(edge->second);
1691
1692             if (qFuzzyCompare(a->y, b->y))
1693                 continue;
1694
1695             found = true;
1696
1697             qreal height = qAbs(a->y - b->y);
1698             if (height > maxHeight) {
1699                 index = i;
1700                 maxHeight = height;
1701             }
1702         }
1703
1704         if (found) {
1705             QPathEdge *edge = list.edge(index);
1706
1707             QPathVertex *a = list.vertex(edge->first);
1708             QPathVertex *b = list.vertex(edge->second);
1709
1710             // FIXME: this can be optimized by using binary search
1711             const int first = qFuzzyFind(y_coords.begin(), y_coords.end(), qMin(a->y, b->y)) - y_coords.begin();
1712             const int last = qFuzzyFind(y_coords.begin() + first, y_coords.end(), qMax(a->y, b->y)) - y_coords.begin();
1713
1714             Q_ASSERT(first < y_coords.size() - 1);
1715             Q_ASSERT(last < y_coords.size());
1716
1717             qreal bestY = 0.5 * (y_coords[first] + y_coords[first+1]);
1718             qreal biggestGap = y_coords[first+1] - y_coords[first];
1719
1720             for (int i = first + 1; i < last; ++i) {
1721                 qreal gap = y_coords[i+1] - y_coords[i];
1722
1723                 if (gap > biggestGap) {
1724                     bestY = 0.5 * (y_coords[i] + y_coords[i+1]);
1725                     biggestGap = gap;
1726                 }
1727             }
1728
1729 #ifdef QDEBUG_CLIPPER
1730             printf("y: %.9f, gap: %.9f\n", bestY, biggestGap);
1731 #endif
1732
1733             if (handleCrossingEdges(list, bestY, mode) && mode == CheckMode)
1734                 return true;
1735
1736             edge->flag |= 0x3;
1737         }
1738     } while (found);
1739
1740     if (mode == ClipMode)
1741         list.simplify();
1742
1743     return false;
1744 }
1745
1746 static void traverse(QWingedEdge &list, int edge, QPathEdge::Traversal traversal)
1747 {
1748     QWingedEdge::TraversalStatus status;
1749     status.edge = edge;
1750     status.traversal = traversal;
1751     status.direction = QPathEdge::Forward;
1752
1753     do {
1754         int flag = status.traversal == QPathEdge::LeftTraversal ? 1 : 2;
1755
1756         QPathEdge *ep = list.edge(status.edge);
1757
1758         ep->flag |= (flag | (flag << 4));
1759
1760 #ifdef QDEBUG_CLIPPER
1761         qDebug() << "traverse: adding edge " << status.edge << ", mask:" << (flag << 4) <<ep->flag;
1762 #endif
1763
1764         status = list.next(status);
1765     } while (status.edge != edge);
1766 }
1767
1768 struct QCrossingEdge
1769 {
1770     int edge;
1771     qreal x;
1772
1773     bool operator<(const QCrossingEdge &edge) const
1774     {
1775         return x < edge.x;
1776     }
1777 };
1778
1779 static bool bool_op(bool a, bool b, QPathClipper::Operation op)
1780 {
1781     switch (op) {
1782     case QPathClipper::BoolAnd:
1783         return a && b;
1784     case QPathClipper::BoolOr: // fall-through
1785     case QPathClipper::Simplify:
1786         return a || b;
1787     case QPathClipper::BoolSub:
1788         return a && !b;
1789     default:
1790         Q_ASSERT(false);
1791         return false;
1792     }
1793 }
1794
1795 bool QWingedEdge::isInside(qreal x, qreal y) const
1796 {
1797     int winding = 0;
1798     for (int i = 0; i < edgeCount(); ++i) {
1799         const QPathEdge *ep = edge(i);
1800
1801         // left xor right
1802         int w = ((ep->flag >> 4) ^ (ep->flag >> 5)) & 1;
1803
1804         if (!w)
1805             continue;
1806
1807         QPointF a = *vertex(ep->first);
1808         QPointF b = *vertex(ep->second);
1809
1810         if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) {
1811             qreal intersectionX = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y());
1812
1813             if (intersectionX > x)
1814                 winding += w;
1815         }
1816     }
1817
1818     return winding & 1;
1819 }
1820
1821 static QVector<QCrossingEdge> findCrossings(const QWingedEdge &list, qreal y)
1822 {
1823     QVector<QCrossingEdge> crossings;
1824     for (int i = 0; i < list.edgeCount(); ++i) {
1825         const QPathEdge *edge = list.edge(i);
1826         QPointF a = *list.vertex(edge->first);
1827         QPointF b = *list.vertex(edge->second);
1828
1829         if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) {
1830             const qreal intersection = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y());
1831             const QCrossingEdge edge = { i, intersection };
1832             crossings << edge;
1833         }
1834     }
1835     return crossings;
1836 }
1837
1838 bool QPathClipper::handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode)
1839 {
1840     QVector<QCrossingEdge> crossings = findCrossings(list, y);
1841
1842     Q_ASSERT(!crossings.isEmpty());
1843     qSort(crossings.begin(), crossings.end());
1844
1845     int windingA = 0;
1846     int windingB = 0;
1847
1848     int windingD = 0;
1849
1850 #ifdef QDEBUG_CLIPPER
1851     qDebug() << "crossings:" << crossings.size();
1852 #endif
1853     for (int i = 0; i < crossings.size() - 1; ++i) {
1854         int ei = crossings.at(i).edge;
1855         const QPathEdge *edge = list.edge(ei);
1856
1857         windingA += edge->windingA;
1858         windingB += edge->windingB;
1859
1860         const bool hasLeft = (edge->flag >> 4) & 1;
1861         const bool hasRight = (edge->flag >> 4) & 2;
1862
1863         windingD += hasLeft ^ hasRight;
1864
1865         const bool inA = (windingA & aMask) != 0;
1866         const bool inB = (windingB & bMask) != 0;
1867         const bool inD = (windingD & 0x1) != 0;
1868
1869         const bool inside = bool_op(inA, inB, op);
1870         const bool add = inD ^ inside;
1871
1872 #ifdef QDEBUG_CLIPPER
1873         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);
1874 #endif
1875
1876         if (add) {
1877             if (mode == CheckMode)
1878                 return true;
1879
1880             qreal y0 = list.vertex(edge->first)->y;
1881             qreal y1 = list.vertex(edge->second)->y;
1882
1883             if (y0 < y1) {
1884                 if (!(edge->flag & 1))
1885                     traverse(list, ei, QPathEdge::LeftTraversal);
1886
1887                 if (!(edge->flag & 2))
1888                     clear(list, ei, QPathEdge::RightTraversal);
1889             } else {
1890                 if (!(edge->flag & 1))
1891                     clear(list, ei, QPathEdge::LeftTraversal);
1892
1893                 if (!(edge->flag & 2))
1894                     traverse(list, ei, QPathEdge::RightTraversal);
1895             }
1896
1897             ++windingD;
1898         } else {
1899             if (!(edge->flag & 1))
1900                 clear(list, ei, QPathEdge::LeftTraversal);
1901
1902             if (!(edge->flag & 2))
1903                 clear(list, ei, QPathEdge::RightTraversal);
1904         }
1905     }
1906
1907     return false;
1908 }
1909
1910 namespace {
1911
1912 QList<QPainterPath> toSubpaths(const QPainterPath &path)
1913 {
1914
1915     QList<QPainterPath> subpaths;
1916     if (path.isEmpty())
1917         return subpaths;
1918
1919     QPainterPath current;
1920     for (int i = 0; i < path.elementCount(); ++i) {
1921         const QPainterPath::Element &e = path.elementAt(i);
1922         switch (e.type) {
1923         case QPainterPath::MoveToElement:
1924             if (current.elementCount() > 1)
1925                 subpaths += current;
1926             current = QPainterPath();
1927             current.moveTo(e);
1928             break;
1929         case QPainterPath::LineToElement:
1930             current.lineTo(e);
1931             break;
1932         case QPainterPath::CurveToElement: {
1933             current.cubicTo(e, path.elementAt(i + 1), path.elementAt(i + 2));
1934             i+=2;
1935             break;
1936         }
1937         case QPainterPath::CurveToDataElement:
1938             Q_ASSERT(!"toSubpaths(), bad element type");
1939             break;
1940         }
1941     }
1942
1943     if (current.elementCount() > 1)
1944         subpaths << current;
1945
1946     return subpaths;
1947 }
1948
1949 enum Edge
1950 {
1951     Left, Top, Right, Bottom
1952 };
1953
1954 static bool isVertical(Edge edge)
1955 {
1956     return edge == Left || edge == Right;
1957 }
1958
1959 template <Edge edge>
1960 bool compare(const QPointF &p, qreal t)
1961 {
1962     switch (edge)
1963     {
1964     case Left:
1965         return p.x() < t;
1966     case Right:
1967         return p.x() > t;
1968     case Top:
1969         return p.y() < t;
1970     default:
1971         return p.y() > t;
1972     }
1973 }
1974
1975 template <Edge edge>
1976 QPointF intersectLine(const QPointF &a, const QPointF &b, qreal t)
1977 {
1978     QLineF line(a, b);
1979     switch (edge) {
1980     case Left: // fall-through
1981     case Right:
1982         return line.pointAt((t - a.x()) / (b.x() - a.x()));
1983     default:
1984         return line.pointAt((t - a.y()) / (b.y() - a.y()));
1985     }
1986 }
1987
1988 void addLine(QPainterPath &path, const QLineF &line)
1989 {
1990     if (path.elementCount() > 0)
1991         path.lineTo(line.p1());
1992     else
1993         path.moveTo(line.p1());
1994
1995     path.lineTo(line.p2());
1996 }
1997
1998 template <Edge edge>
1999 void clipLine(const QPointF &a, const QPointF &b, qreal t, QPainterPath &result)
2000 {
2001     bool outA = compare<edge>(a, t);
2002     bool outB = compare<edge>(b, t);
2003     if (outA && outB)
2004         return;
2005
2006     if (outA)
2007         addLine(result, QLineF(intersectLine<edge>(a, b, t), b));
2008     else if(outB)
2009         addLine(result, QLineF(a, intersectLine<edge>(a, b, t)));
2010     else
2011         addLine(result, QLineF(a, b));
2012 }
2013
2014 void addBezier(QPainterPath &path, const QBezier &bezier)
2015 {
2016     if (path.elementCount() > 0)
2017         path.lineTo(bezier.pt1());
2018     else
2019         path.moveTo(bezier.pt1());
2020
2021     path.cubicTo(bezier.pt2(), bezier.pt3(), bezier.pt4());
2022 }
2023
2024 template <Edge edge>
2025 void clipBezier(const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, qreal t, QPainterPath &result)
2026 {
2027     QBezier bezier = QBezier::fromPoints(a, b, c, d);
2028
2029     bool outA = compare<edge>(a, t);
2030     bool outB = compare<edge>(b, t);
2031     bool outC = compare<edge>(c, t);
2032     bool outD = compare<edge>(d, t);
2033
2034     int outCount = int(outA) + int(outB) + int(outC) + int(outD);
2035
2036     if (outCount == 4)
2037         return;
2038
2039     if (outCount == 0) {
2040         addBezier(result, bezier);
2041         return;
2042     }
2043
2044     QTransform flip = isVertical(edge) ? QTransform(0, 1, 1, 0, 0, 0) : QTransform();
2045     QBezier unflipped = bezier;
2046     QBezier flipped = bezier.mapBy(flip);
2047
2048     qreal t0 = 0, t1 = 1;
2049     int stationary = flipped.stationaryYPoints(t0, t1);
2050
2051     qreal segments[4];
2052     QPointF points[4];
2053     points[0] = unflipped.pt1();
2054     segments[0] = 0;
2055
2056     int segmentCount = 0;
2057     if (stationary > 0) {
2058         ++segmentCount;
2059         segments[segmentCount] = t0;
2060         points[segmentCount] = unflipped.pointAt(t0);
2061     }
2062     if (stationary > 1) {
2063         ++segmentCount;
2064         segments[segmentCount] = t1;
2065         points[segmentCount] = unflipped.pointAt(t1);
2066     }
2067     ++segmentCount;
2068     segments[segmentCount] = 1;
2069     points[segmentCount] = unflipped.pt4();
2070
2071     qreal lastIntersection = 0;
2072     for (int i = 0; i < segmentCount; ++i) {
2073         outA = compare<edge>(points[i], t);
2074         outB = compare<edge>(points[i+1], t);
2075
2076         if (outA != outB) {
2077             qreal intersection = flipped.tForY(segments[i], segments[i+1], t);
2078
2079             if (outB)
2080                 addBezier(result, unflipped.getSubRange(lastIntersection, intersection));
2081
2082             lastIntersection = intersection;
2083         }
2084     }
2085
2086     if (!outB)
2087         addBezier(result, unflipped.getSubRange(lastIntersection, 1));
2088 }
2089
2090 // clips a single subpath against a single edge
2091 template <Edge edge>
2092 QPainterPath clip(const QPainterPath &path, qreal t)
2093 {
2094     QPainterPath result;
2095     for (int i = 1; i < path.elementCount(); ++i) {
2096         const QPainterPath::Element &element = path.elementAt(i);
2097         Q_ASSERT(!element.isMoveTo());
2098         if (element.isLineTo()) {
2099             clipLine<edge>(path.elementAt(i-1), path.elementAt(i), t, result);
2100         } else {
2101             clipBezier<edge>(path.elementAt(i-1), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2), t, result);
2102             i += 2;
2103         }
2104     }
2105
2106     int last = path.elementCount() - 1;
2107     if (QPointF(path.elementAt(last)) != QPointF(path.elementAt(0)))
2108         clipLine<edge>(path.elementAt(last), path.elementAt(0), t, result);
2109
2110     return result;
2111 }
2112
2113 QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect)
2114 {
2115     QList<QPainterPath> subpaths = toSubpaths(path);
2116
2117     QPainterPath result;
2118     result.setFillRule(path.fillRule());
2119     for (int i = 0; i < subpaths.size(); ++i) {
2120         QPainterPath subPath = subpaths.at(i);
2121         QRectF bounds = subPath.boundingRect();
2122         if (bounds.intersects(rect)) {
2123             if (bounds.left() < rect.left())
2124                 subPath = clip<Left>(subPath, rect.left());
2125             if (bounds.right() > rect.right())
2126                 subPath = clip<Right>(subPath, rect.right());
2127
2128             bounds = subPath.boundingRect();
2129
2130             if (bounds.top() < rect.top())
2131                 subPath = clip<Top>(subPath, rect.top());
2132             if (bounds.bottom() > rect.bottom())
2133                 subPath = clip<Bottom>(subPath, rect.bottom());
2134
2135             if (subPath.elementCount() > 1)
2136                 result.addPath(subPath);
2137         }
2138     }
2139     return result;
2140 }
2141
2142 }
2143
2144 QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect)
2145 {
2146     return intersectPath(path, rect);
2147 }
2148
2149 QT_END_NAMESPACE