1 /****************************************************************************
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/
6 ** This file is part of the QtGui module of the Qt Toolkit.
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.
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.
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.
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.
40 ****************************************************************************/
42 #include "qpathclipper_p.h"
44 #include <private/qbezier_p.h>
45 #include <private/qdatabuffer_p.h>
46 #include <private/qnumeric_p.h>
50 The algorithm is as follows:
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.
69 static inline bool fuzzyIsNull(qreal d)
71 if (sizeof(qreal) == sizeof(double))
72 return qAbs(d) <= 1e-12;
74 return qAbs(d) <= 1e-5f;
77 static inline bool comparePoints(const QPointF &a, const QPointF &b)
79 return fuzzyIsNull(a.x() - b.x())
80 && fuzzyIsNull(a.y() - b.y());
83 //#define QDEBUG_CLIPPER
84 static qreal dot(const QPointF &a, const QPointF &b)
86 return a.x() * b.x() + a.y() * b.y();
89 static void normalize(double &x, double &y)
91 double reciprocal = 1 / qSqrt(x * x + y * y);
104 class QIntersectionFinder
107 void produceIntersections(QPathSegments &segments);
108 bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const;
111 bool linesIntersect(const QLineF &a, const QLineF &b) const;
114 bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const
116 const QPointF p1 = a.p1();
117 const QPointF p2 = a.p2();
119 const QPointF q1 = b.p1();
120 const QPointF q2 = b.p2();
122 if (comparePoints(p1, p2) || comparePoints(q1, q2))
125 const bool p1_equals_q1 = comparePoints(p1, q1);
126 const bool p2_equals_q2 = comparePoints(p2, q2);
128 if (p1_equals_q1 && p2_equals_q2)
131 const bool p1_equals_q2 = comparePoints(p1, q2);
132 const bool p2_equals_q1 = comparePoints(p2, q1);
134 if (p1_equals_q2 && p2_equals_q1)
137 const QPointF pDelta = p2 - p1;
138 const QPointF qDelta = q2 - q1;
140 const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x();
142 if (qFuzzyIsNull(par)) {
143 const QPointF normal(-pDelta.y(), pDelta.x());
146 if (qFuzzyIsNull(dot(normal, q1 - p1))) {
147 const qreal dp = dot(pDelta, pDelta);
149 const qreal tq1 = dot(pDelta, q1 - p1);
150 const qreal tq2 = dot(pDelta, q2 - p1);
152 if ((tq1 > 0 && tq1 < dp) || (tq2 > 0 && tq2 < dp))
155 const qreal dq = dot(qDelta, qDelta);
157 const qreal tp1 = dot(qDelta, p1 - q1);
158 const qreal tp2 = dot(qDelta, p2 - q1);
160 if ((tp1 > 0 && tp1 < dq) || (tp2 > 0 && tp2 < dq))
167 const qreal invPar = 1 / par;
169 const qreal tp = (qDelta.y() * (q1.x() - p1.x()) -
170 qDelta.x() * (q1.y() - p1.y())) * invPar;
172 if (tp < 0 || tp > 1)
175 const qreal tq = (pDelta.y() * (q1.x() - p1.x()) -
176 pDelta.x() * (q1.y() - p1.y())) * invPar;
178 return tq >= 0 && tq <= 1;
181 bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const
183 if (a.segments() == 0 || b.segments() == 0)
186 const QRectF &rb0 = b.elementBounds(0);
188 qreal minX = rb0.left();
189 qreal minY = rb0.top();
190 qreal maxX = rb0.right();
191 qreal maxY = rb0.bottom();
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());
201 QRectF rb(minX, minY, maxX - minX, maxY - minY);
203 for (int i = 0; i < a.segments(); ++i) {
204 const QRectF &r1 = a.elementBounds(i);
206 if (r1.left() > rb.right() || rb.left() > r1.right())
208 if (r1.top() > rb.bottom() || rb.top() > r1.bottom())
211 for (int j = 0; j < b.segments(); ++j) {
212 const QRectF &r2 = b.elementBounds(j);
214 if (r1.left() > r2.right() || r2.left() > r1.right())
216 if (r1.top() > r2.bottom() || r2.top() > r1.bottom())
219 if (linesIntersect(a.lineAt(i), b.lineAt(j)))
235 int lowestRightIndex;
260 SegmentTree(QPathSegments &segments);
262 QRectF boundingRect() const;
264 void produceIntersections(int segment);
267 TreeNode buildTree(int first, int last, int depth, const RectF &bounds);
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);
273 QPathSegments &m_segments;
274 QVector<int> m_index;
278 QVector<TreeNode> m_tree;
279 QDataBuffer<QIntersection> m_intersections;
282 SegmentTree::SegmentTree(QPathSegments &segments)
283 : m_segments(segments),
286 m_bounds.x1 = qt_inf();
287 m_bounds.y1 = qt_inf();
288 m_bounds.x2 = -qt_inf();
289 m_bounds.y2 = -qt_inf();
291 m_index.resize(m_segments.segments());
293 for (int i = 0; i < m_index.size(); ++i) {
296 const QRectF &segmentBounds = m_segments.elementBounds(i);
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();
310 TreeNode root = buildTree(0, m_index.size(), 0, m_bounds);
314 QRectF SegmentTree::boundingRect() const
316 return QRectF(QPointF(m_bounds.x1, m_bounds.y1),
317 QPointF(m_bounds.x2, m_bounds.y2));
320 static inline qreal coordinate(const QPointF &pos, int axis)
322 return axis == 0 ? pos.x() : pos.y();
325 TreeNode SegmentTree::buildTree(int first, int last, int depth, const RectF &bounds)
327 if (depth >= 24 || (last - first) <= 10) {
330 node.index.interval.first = first;
331 node.index.interval.last = last;
336 int splitAxis = (depth & 1);
341 qreal split = 0.5f * ((&bounds.x1)[splitAxis] + (&bounds.x2)[splitAxis]);
343 node.splitLeft = (&bounds.x1)[splitAxis];
344 node.splitRight = (&bounds.x2)[splitAxis];
346 node.lowestLeftIndex = INT_MAX;
347 node.lowestRightIndex = INT_MAX;
349 const int treeSize = m_tree.size();
351 node.index.children.left = treeSize;
352 node.index.children.right = treeSize + 1;
354 m_tree.resize(treeSize + 2);
359 // partition into left and right sets
361 const int index = m_index.at(l);
362 const QRectF &segmentBounds = m_segments.elementBounds(index);
364 qreal lowCoordinate = coordinate(segmentBounds.topLeft(), splitAxis);
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;
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]);
383 RectF lbounds = bounds;
384 (&lbounds.x2)[splitAxis] = node.splitLeft;
386 RectF rbounds = bounds;
387 (&rbounds.x1)[splitAxis] = node.splitRight;
389 TreeNode left = buildTree(first, l, depth + 1, lbounds);
390 m_tree[node.index.children.left] = left;
392 TreeNode right = buildTree(l, last, depth + 1, rbounds);
393 m_tree[node.index.children.right] = right;
398 void SegmentTree::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections)
400 const QPointF p1 = a.p1();
401 const QPointF p2 = a.p2();
403 const QPointF q1 = b.p1();
404 const QPointF q2 = b.p2();
406 if (comparePoints(p1, p2) || comparePoints(q1, q2))
409 const bool p1_equals_q1 = comparePoints(p1, q1);
410 const bool p2_equals_q2 = comparePoints(p2, q2);
412 if (p1_equals_q1 && p2_equals_q2)
415 const bool p1_equals_q2 = comparePoints(p1, q2);
416 const bool p2_equals_q1 = comparePoints(p2, q1);
418 if (p1_equals_q2 && p2_equals_q1)
421 const QPointF pDelta = p2 - p1;
422 const QPointF qDelta = q2 - q1;
424 const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x();
426 if (qFuzzyIsNull(par)) {
427 const QPointF normal(-pDelta.y(), pDelta.x());
430 if (qFuzzyIsNull(dot(normal, q1 - p1))) {
431 const qreal invDp = 1 / dot(pDelta, pDelta);
433 const qreal tq1 = dot(pDelta, q1 - p1) * invDp;
434 const qreal tq2 = dot(pDelta, q2 - p1) * invDp;
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);
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);
452 const qreal invDq = 1 / dot(qDelta, qDelta);
454 const qreal tp1 = dot(qDelta, p1 - q1) * invDq;
455 const qreal tp2 = dot(qDelta, p2 - q1) * invDq;
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);
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);
477 // if the lines are not parallel and share a common end point, then they
479 if (p1_equals_q1 || p1_equals_q2 || p2_equals_q1 || p2_equals_q2)
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;
488 if (tp<0 || tp>1 || tq<0 || tq>1)
491 const bool p_zero = qFuzzyIsNull(tp);
492 const bool p_one = qFuzzyIsNull(tp - 1);
494 const bool q_zero = qFuzzyIsNull(tq);
495 const bool q_one = qFuzzyIsNull(tq - 1);
497 if ((q_zero || q_one) && (p_zero || p_one))
510 pt = q1 + (q2 - q1) * tq;
513 QIntersection intersection;
514 intersection.alphaA = tp;
515 intersection.alphaB = tq;
516 intersection.pos = pt;
517 intersections.add(intersection);
520 void SegmentTree::produceIntersections(int segment)
522 const QRectF &segmentBounds = m_segments.elementBounds(segment);
525 sbounds.x1 = segmentBounds.left();
526 sbounds.y1 = segmentBounds.top();
527 sbounds.x2 = segmentBounds.right();
528 sbounds.y2 = segmentBounds.bottom();
530 produceIntersections(m_tree.at(0), segment, sbounds, m_bounds, 0);
533 void SegmentTree::produceIntersectionsLeaf(const TreeNode &node, int segment)
535 const QRectF &r1 = m_segments.elementBounds(segment);
536 const QLineF lineA = m_segments.lineAt(segment);
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)
543 const QRectF &r2 = m_segments.elementBounds(other);
545 if (r1.left() > r2.right() || r2.left() > r1.right())
547 if (r1.top() > r2.bottom() || r2.top() > r1.bottom())
550 m_intersections.reset();
552 const QLineF lineB = m_segments.lineAt(other);
554 intersectLines(lineA, lineB, m_intersections);
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);
560 i_isect.t = m_intersections.at(k).alphaA;
561 j_isect.t = m_intersections.at(k).alphaB;
566 m_segments.addIntersection(segment, i_isect);
567 m_segments.addIntersection(other, j_isect);
572 void SegmentTree::produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis)
575 produceIntersectionsLeaf(node, segment);
579 RectF lbounds = nodeBounds;
580 (&lbounds.x2)[axis] = node.splitLeft;
582 RectF rbounds = nodeBounds;
583 (&rbounds.x1)[axis] = node.splitRight;
585 if (segment > node.lowestLeftIndex && (&segmentBounds.x1)[axis] <= node.splitLeft)
586 produceIntersections(m_tree.at(node.index.children.left), segment, segmentBounds, lbounds, !axis);
588 if (segment > node.lowestRightIndex && (&segmentBounds.x2)[axis] >= node.splitRight)
589 produceIntersections(m_tree.at(node.index.children.right), segment, segmentBounds, rbounds, !axis);
594 void QIntersectionFinder::produceIntersections(QPathSegments &segments)
596 SegmentTree tree(segments);
598 for (int i = 0; i < segments.segments(); ++i)
599 tree.produceIntersections(i);
620 QKdPointTree(const QPathSegments &segments)
621 : m_segments(&segments)
622 , m_nodes(m_segments->points())
625 m_nodes.resize(m_segments->points());
627 for (int i = 0; i < m_nodes.size(); ++i) {
628 m_nodes.at(i).point = i;
629 m_nodes.at(i).id = -1;
632 m_rootNode = build(0, m_nodes.size());
635 int build(int begin, int end, int depth = 0);
639 return &m_nodes.at(m_rootNode);
648 const QPathSegments *m_segments;
649 QDataBuffer<Node> m_nodes;
655 template <typename T>
656 void qTraverseKdPointTree(QKdPointTree::Node &node, T &t, int depth = 0)
658 QKdPointTree::Traversal status = t(node, depth);
660 const bool traverseRight = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseRight);
661 const bool traverseLeft = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseLeft);
663 if (traverseLeft && node.left)
664 QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.left, t, depth + 1);
666 if (traverseRight && node.right)
667 QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.right, t, depth + 1);
670 static inline qreal component(const QPointF &point, unsigned int i)
673 const qreal components[] = { point.x(), point.y() };
674 return components[i];
677 int QKdPointTree::build(int begin, int end, int depth)
679 Q_ASSERT(end > begin);
681 const qreal pivot = component(m_segments->pointAt(m_nodes.at(begin).point), depth & 1);
683 int first = begin + 1;
686 while (first <= last) {
687 const qreal value = component(m_segments->pointAt(m_nodes.at(first).point), depth & 1);
692 qSwap(m_nodes.at(first), m_nodes.at(last));
697 qSwap(m_nodes.at(last), m_nodes.at(begin));
700 m_nodes.at(last).left = &m_nodes.at(build(begin, last, depth + 1));
702 m_nodes.at(last).left = 0;
705 m_nodes.at(last).right = &m_nodes.at(build(last + 1, end, depth + 1));
707 m_nodes.at(last).right = 0;
715 QKdPointFinder(int point, const QPathSegments &segments, QKdPointTree &tree)
718 , m_segments(&segments)
721 pointComponents[0] = segments.pointAt(point).x();
722 pointComponents[1] = segments.pointAt(point).y();
725 inline QKdPointTree::Traversal operator()(QKdPointTree::Node &node, int depth)
728 return QKdPointTree::TraverseNone;
730 const QPointF &nodePoint = m_segments->pointAt(node.point);
732 const qreal pivotComponents[] = { nodePoint.x(), nodePoint.y() };
734 const qreal pivot = pivotComponents[depth & 1];
735 const qreal value = pointComponents[depth & 1];
737 if (fuzzyIsNull(pivot - value)) {
738 const qreal pivot2 = pivotComponents[(depth + 1) & 1];
739 const qreal value2 = pointComponents[(depth + 1) & 1];
741 if (fuzzyIsNull(pivot2 - value2)) {
743 node.id = m_tree->nextId();
746 return QKdPointTree::TraverseNone;
748 return QKdPointTree::TraverseBoth;
749 } else if (value < pivot) {
750 return QKdPointTree::TraverseLeft;
752 return QKdPointTree::TraverseRight;
763 qreal pointComponents[2];
765 const QPathSegments *m_segments;
766 QKdPointTree *m_tree;
769 // merge all points that are within qFuzzyCompare range of each other
770 void QPathSegments::mergePoints()
772 QKdPointTree tree(*this);
774 if (tree.rootNode()) {
775 QDataBuffer<QPointF> mergedPoints(points());
776 QDataBuffer<int> pointIndices(points());
778 for (int i = 0; i < points(); ++i) {
779 QKdPointFinder finder(i, *this, tree);
780 QT_PREPEND_NAMESPACE(qTraverseKdPointTree<QKdPointFinder>)(*tree.rootNode(), finder);
782 Q_ASSERT(finder.result() != -1);
784 if (finder.result() >= mergedPoints.size())
785 mergedPoints << m_points.at(i);
787 pointIndices << finder.result();
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);
795 for (int i = 0; i < m_intersections.size(); ++i)
796 m_intersections.at(i).vertex = pointIndices.at(m_intersections.at(i).vertex);
798 m_points.swap(mergedPoints);
802 void QWingedEdge::intersectAndAdd()
804 QIntersectionFinder finder;
805 finder.produceIntersections(m_segments);
807 m_segments.mergePoints();
809 for (int i = 0; i < m_segments.points(); ++i)
810 addVertex(m_segments.pointAt(i));
812 QDataBuffer<QPathSegments::Intersection> intersections(m_segments.segments());
813 for (int i = 0; i < m_segments.segments(); ++i) {
814 intersections.reset();
816 int pathId = m_segments.pathId(i);
818 const QPathSegments::Intersection *isect = m_segments.intersectionAt(i);
820 intersections << *isect;
823 isect += isect->next;
829 qSort(intersections.data(), intersections.data() + intersections.size());
831 int first = m_segments.segmentAt(i).va;
832 int second = m_segments.segmentAt(i).vb;
835 for (int j = 0; j < intersections.size(); ++j) {
836 const QPathSegments::Intersection &isect = intersections.at(j);
838 QPathEdge *ep = edge(addEdge(last, isect.vertex));
841 const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(isect.vertex).y() ? 1 : -1;
851 QPathEdge *ep = edge(addEdge(last, second));
854 const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(second).y() ? 1 : -1;
863 QWingedEdge::QWingedEdge() :
870 QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip) :
871 m_edges(subject.elementCount()),
872 m_vertices(subject.elementCount()),
873 m_segments(subject.elementCount())
875 m_segments.setPath(subject);
876 m_segments.addPath(clip);
881 QWingedEdge::TraversalStatus QWingedEdge::next(const QWingedEdge::TraversalStatus &status) const
883 const QPathEdge *sp = edge(status.edge);
886 TraversalStatus result;
887 result.edge = sp->next(status.traversal, status.direction);
888 result.traversal = status.traversal;
889 result.direction = status.direction;
891 const QPathEdge *rp = edge(result.edge);
894 if (sp->vertex(status.direction) == rp->vertex(status.direction))
900 static bool isLine(const QBezier &bezier)
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());
907 if (equal_1_2 && equal_2_3 && equal_3_4)
910 if (comparePoints(bezier.pt1(), bezier.pt4()))
911 return equal_1_2 || equal_3_4;
913 return (equal_1_2 && equal_3_4) || (equal_1_2 && equal_2_3) || (equal_2_3 && equal_3_4);
916 void QPathSegments::setPath(const QPainterPath &path)
919 m_intersections.reset();
927 void QPathSegments::addPath(const QPainterPath &path)
929 int firstSegment = m_segments.size();
931 bool hasMoveTo = false;
934 for (int i = 0; i < path.elementCount(); ++i) {
935 int current = m_points.size();
937 QPointF currentPoint;
938 if (path.elementAt(i).type == QPainterPath::CurveToElement)
939 currentPoint = path.elementAt(i+2);
941 currentPoint = path.elementAt(i);
943 if (i > 0 && comparePoints(m_points.at(lastMoveTo), currentPoint))
944 current = lastMoveTo;
946 m_points << currentPoint;
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);
953 last = lastMoveTo = current;
955 case QPainterPath::LineToElement:
956 m_segments << Segment(m_pathId, last, current);
959 case QPainterPath::CurveToElement:
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);
965 QRectF bounds = bezier.bounds();
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));
970 if (threshold < 3) threshold = 3;
971 qreal one_over_threshold_minus_1 = qreal(1) / (threshold - 1);
973 for (int t = 1; t < threshold - 1; ++t) {
974 currentPoint = bezier.pointAt(t * one_over_threshold_minus_1);
976 int index = m_points.size();
977 m_segments << Segment(m_pathId, last, index);
980 m_points << currentPoint;
983 m_segments << Segment(m_pathId, last, current);
995 if (hasMoveTo && last != lastMoveTo && !comparePoints(m_points.at(last), m_points.at(lastMoveTo)))
996 m_segments << Segment(m_pathId, last, lastMoveTo);
998 for (int i = firstSegment; i < m_segments.size(); ++i) {
999 const QLineF line = lineAt(i);
1001 qreal x1 = line.p1().x();
1002 qreal y1 = line.p1().y();
1003 qreal x2 = line.p2().x();
1004 qreal y2 = line.p2().y();
1011 m_segments.at(i).bounds = QRectF(x1, y1, x2 - x1, y2 - y1);
1017 qreal QWingedEdge::delta(int vertex, int a, int b) const
1019 const QPathEdge *ap = edge(a);
1020 const QPathEdge *bp = edge(b);
1022 double a_angle = ap->angle;
1023 double b_angle = bp->angle;
1025 if (vertex == ap->second)
1026 a_angle = ap->invAngle;
1028 if (vertex == bp->second)
1029 b_angle = bp->invAngle;
1031 double result = b_angle - a_angle;
1034 return result - 128.;
1035 else if (result < 0)
1036 return result + 128.;
1041 static inline QPointF midPoint(const QWingedEdge &list, int ei)
1043 const QPathEdge *ep = list.edge(ei);
1046 const QPointF a = *list.vertex(ep->first);
1047 const QPointF b = *list.vertex(ep->second);
1048 return a + 0.5 * (b - a);
1051 QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const
1053 const QPathVertex *vp = vertex(vi);
1057 Q_ASSERT(vp->edge >= 0);
1059 int position = vp->edge;
1062 TraversalStatus status;
1063 status.direction = edge(vp->edge)->directionTo(vi);
1064 status.traversal = QPathEdge::RightTraversal;
1065 status.edge = vp->edge;
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;
1073 status = next(status);
1076 Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi);
1077 qreal d2 = delta(vi, ei, status.edge);
1079 #ifdef QDEBUG_CLIPPER
1080 const QPathEdge *op = edge(status.edge);
1081 qDebug() << "Delta to edge" << status.edge << d2 << ", angles: " << op->angle << op->invAngle;
1085 position = status.edge;
1088 } while (status.edge != vp->edge);
1090 status.traversal = QPathEdge::LeftTraversal;
1091 status.direction = QPathEdge::Forward;
1092 status.edge = position;
1094 if (edge(status.edge)->vertex(status.direction) != vi)
1097 #ifdef QDEBUG_CLIPPER
1098 qDebug() << "Inserting edge" << ei << "to" << (status.traversal == QPathEdge::LeftTraversal ? "left" : "right") << "of edge" << status.edge;
1101 Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi);
1106 void QWingedEdge::removeEdge(int ei)
1108 QPathEdge *ep = edge(ei);
1110 TraversalStatus status;
1111 status.direction = QPathEdge::Forward;
1112 status.traversal = QPathEdge::RightTraversal;
1115 TraversalStatus forwardRight = next(status);
1116 forwardRight.flipDirection();
1118 status.traversal = QPathEdge::LeftTraversal;
1119 TraversalStatus forwardLeft = next(status);
1120 forwardLeft.flipDirection();
1122 status.direction = QPathEdge::Backward;
1123 TraversalStatus backwardLeft = next(status);
1124 backwardLeft.flipDirection();
1126 status.traversal = QPathEdge::RightTraversal;
1127 TraversalStatus backwardRight = next(status);
1128 backwardRight.flipDirection();
1130 edge(forwardRight.edge)->setNext(forwardRight.traversal, forwardRight.direction, forwardLeft.edge);
1131 edge(forwardLeft.edge)->setNext(forwardLeft.traversal, forwardLeft.direction, forwardRight.edge);
1133 edge(backwardRight.edge)->setNext(backwardRight.traversal, backwardRight.direction, backwardLeft.edge);
1134 edge(backwardLeft.edge)->setNext(backwardLeft.traversal, backwardLeft.direction, backwardRight.edge);
1136 ep->setNext(QPathEdge::Forward, ei);
1137 ep->setNext(QPathEdge::Backward, ei);
1139 QPathVertex *a = vertex(ep->first);
1140 QPathVertex *b = vertex(ep->second);
1142 a->edge = backwardRight.edge;
1143 b->edge = forwardRight.edge;
1146 static int commonEdge(const QWingedEdge &list, int a, int b)
1148 const QPathVertex *ap = list.vertex(a);
1151 const QPathVertex *bp = list.vertex(b);
1154 if (ap->edge < 0 || bp->edge < 0)
1157 QWingedEdge::TraversalStatus status;
1158 status.edge = ap->edge;
1159 status.direction = list.edge(status.edge)->directionTo(a);
1160 status.traversal = QPathEdge::RightTraversal;
1163 const QPathEdge *ep = list.edge(status.edge);
1165 if ((ep->first == a && ep->second == b)
1166 || (ep->first == b && ep->second == a))
1169 status = list.next(status);
1171 } while (status.edge != ap->edge);
1176 static double computeAngle(const QPointF &v)
1180 return v.y() <= 0 ? 0 : 64.;
1181 } else if (v.y() == 0) {
1182 return v.x() <= 0 ? 32. : 96.;
1189 if (vx < 0) { // 0 - 32
1191 } else { // 96 - 128
1192 return 128. - 32. * vx;
1195 return 64. + 32. * vx;
1198 // doesn't seem to be robust enough
1199 return qAtan2(v.x(), v.y()) + Q_PI;
1203 int QWingedEdge::addEdge(const QPointF &a, const QPointF &b)
1208 return addEdge(fi, si);
1211 int QWingedEdge::addEdge(int fi, int si)
1216 int common = commonEdge(*this, fi, si);
1220 m_edges << QPathEdge(fi, si);
1222 int ei = m_edges.size() - 1;
1224 QPathVertex *fp = vertex(fi);
1225 QPathVertex *sp = vertex(si);
1227 QPathEdge *ep = edge(ei);
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;
1235 QPathVertex *vertices[2] = { fp, sp };
1236 QPathEdge::Direction dirs[2] = { QPathEdge::Backward, QPathEdge::Forward };
1238 #ifdef QDEBUG_CLIPPER
1239 printf("** Adding edge %d / vertices: %.07f %.07f, %.07f %.07f\n", ei, fp->x, fp->y, sp->x, sp->y);
1242 for (int i = 0; i < 2; ++i) {
1243 QPathVertex *vp = vertices[i];
1246 ep->setNext(dirs[i], ei);
1248 int vi = ep->vertex(dirs[i]);
1249 Q_ASSERT(vertex(vi) == vertices[i]);
1251 TraversalStatus os = findInsertStatus(vi, ei);
1252 QPathEdge *op = edge(os.edge);
1254 Q_ASSERT(vertex(op->vertex(os.direction)) == vertices[i]);
1256 TraversalStatus ns = next(os);
1258 QPathEdge *np = edge(ns.edge);
1260 op->setNext(os.traversal, os.direction, ei);
1261 np->setNext(ns.traversal, ns.direction, ei);
1272 Q_ASSERT(os.edge == ei);
1273 Q_ASSERT(ns.edge == ei);
1275 ep->setNext(os.traversal, os.direction, oe);
1276 ep->setNext(ns.traversal, ns.direction, ne);
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);
1288 int QWingedEdge::insert(const QPathVertex &vertex)
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;
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)) {
1303 m_vertices << vertex;
1304 return m_vertices.size() - 1;
1307 static void addLineTo(QPainterPath &path, const QPointF &point)
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;
1317 const QPointF p(-d1.y(), d1.x());
1319 if (qFuzzyIsNull(dot(p, d2))) {
1320 path.setElementPositionAt(elementCount - 1, point.x(), point.y());
1329 static void add(QPainterPath &path, const QWingedEdge &list, int edge, QPathEdge::Traversal traversal)
1331 QWingedEdge::TraversalStatus status;
1333 status.traversal = traversal;
1334 status.direction = QPathEdge::Forward;
1336 path.moveTo(*list.vertex(list.edge(edge)->first));
1339 const QPathEdge *ep = list.edge(status.edge);
1341 addLineTo(path, *list.vertex(ep->vertex(status.direction)));
1343 if (status.traversal == QPathEdge::LeftTraversal)
1348 status = list.next(status);
1349 } while (status.edge != edge);
1352 void QWingedEdge::simplify()
1354 for (int i = 0; i < edgeCount(); ++i) {
1355 const QPathEdge *ep = edge(i);
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) {
1367 QPainterPath QWingedEdge::toPath() const
1371 for (int i = 0; i < edgeCount(); ++i) {
1372 const QPathEdge *ep = edge(i);
1374 if (ep->flag & 16) {
1375 add(path, *this, i, QPathEdge::LeftTraversal);
1379 add(path, *this, i, QPathEdge::RightTraversal);
1385 bool QPathClipper::intersect()
1387 if (subjectPath == clipPath)
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
1398 bool subjectIsRect = pathToRect(subjectPath);
1399 bool clipIsRect = pathToRect(clipPath);
1401 if (subjectIsRect && clipIsRect)
1403 else if (subjectIsRect)
1404 return clipPath.intersects(r1);
1405 else if (clipIsRect)
1406 return subjectPath.intersects(r2);
1408 QPathSegments a(subjectPath.elementCount());
1409 a.setPath(subjectPath);
1410 QPathSegments b(clipPath.elementCount());
1411 b.setPath(clipPath);
1413 QIntersectionFinder finder;
1414 if (finder.hasIntersections(a, b))
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))
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))
1436 bool QPathClipper::contains()
1438 if (subjectPath == clipPath)
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
1449 bool clipIsRect = pathToRect(clipPath);
1451 return subjectPath.contains(r2);
1453 QPathSegments a(subjectPath.elementCount());
1454 a.setPath(subjectPath);
1455 QPathSegments b(clipPath.elementCount());
1456 b.setPath(clipPath);
1458 QIntersectionFinder finder;
1459 if (finder.hasIntersections(a, b))
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))
1473 QPathClipper::QPathClipper(const QPainterPath &subject,
1474 const QPainterPath &clip)
1475 : subjectPath(subject)
1478 aMask = subjectPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1;
1479 bMask = clipPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1;
1482 template <typename Iterator, typename Equality>
1483 Iterator qRemoveDuplicates(Iterator begin, Iterator end, Equality eq)
1488 Iterator last = begin;
1490 Iterator insert = begin;
1491 for (Iterator it = begin; it != end; ++it) {
1492 if (!eq(*it, *last)) {
1501 static void clear(QWingedEdge& list, int edge, QPathEdge::Traversal traversal)
1503 QWingedEdge::TraversalStatus status;
1505 status.traversal = traversal;
1506 status.direction = QPathEdge::Forward;
1509 if (status.traversal == QPathEdge::LeftTraversal)
1510 list.edge(status.edge)->flag |= 1;
1512 list.edge(status.edge)->flag |= 2;
1514 status = list.next(status);
1515 } while (status.edge != edge);
1518 template <typename InputIterator>
1519 InputIterator qFuzzyFind(InputIterator first, InputIterator last, qreal val)
1521 while (first != last && !QT_PREPEND_NAMESPACE(qFuzzyCompare)(qreal(*first), qreal(val)))
1526 static bool fuzzyCompare(qreal a, qreal b)
1528 return qFuzzyCompare(a, b);
1531 bool QPathClipper::pathToRect(const QPainterPath &path, QRectF *rect)
1533 if (path.elementCount() != 5)
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();
1545 const qreal x1 = path.elementAt(0).x;
1546 const qreal y1 = path.elementAt(0).y;
1548 const qreal x2 = path.elementAt(1).x;
1549 const qreal y2 = path.elementAt(2).y;
1551 if (path.elementAt(1).y != y1)
1554 if (path.elementAt(2).x != x2)
1557 if (path.elementAt(3).x != x1 || path.elementAt(3).y != y2)
1560 if (path.elementAt(4).x != x1 || path.elementAt(4).y != y1)
1564 rect->setCoords(x1, y1, x2, y2);
1570 QPainterPath QPathClipper::clip(Operation operation)
1574 if (op != Simplify) {
1575 if (subjectPath == clipPath)
1576 return op == BoolSub ? QPainterPath() : subjectPath;
1578 bool subjectIsRect = pathToRect(subjectPath, 0);
1579 bool clipIsRect = pathToRect(clipPath, 0);
1581 const QRectF clipBounds = clipPath.boundingRect();
1582 const QRectF subjectBounds = subjectPath.boundingRect();
1584 if (!clipBounds.intersects(subjectBounds)) {
1589 return QPainterPath();
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);
1598 result.addPath(clipPath.simplified());
1607 if (clipBounds.contains(subjectBounds)) {
1611 return QPainterPath();
1620 } else if (subjectBounds.contains(clipBounds)) {
1621 if (subjectIsRect) {
1624 if (clipPath.fillRule() == Qt::OddEvenFill) {
1625 QPainterPath result = clipPath;
1626 result.addRect(subjectBounds);
1629 QPainterPath result = clipPath.simplified();
1630 result.addRect(subjectBounds);
1644 if (op == BoolAnd) {
1646 return intersect(clipPath, subjectBounds);
1647 else if (clipIsRect)
1648 return intersect(subjectPath, clipBounds);
1652 QWingedEdge list(subjectPath, clipPath);
1654 doClip(list, ClipMode);
1656 QPainterPath path = list.toPath();
1660 bool QPathClipper::doClip(QWingedEdge &list, ClipperMode mode)
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;
1667 qSort(y_coords.begin(), y_coords.end());
1668 y_coords.resize(qRemoveDuplicates(y_coords.begin(), y_coords.end(), fuzzyCompare) - y_coords.begin());
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]);
1681 qreal maxHeight = 0;
1682 for (int i = 0; i < list.edgeCount(); ++i) {
1683 QPathEdge *edge = list.edge(i);
1685 // have both sides of this edge already been handled?
1686 if ((edge->flag & 0x3) == 0x3)
1689 QPathVertex *a = list.vertex(edge->first);
1690 QPathVertex *b = list.vertex(edge->second);
1692 if (qFuzzyCompare(a->y, b->y))
1697 qreal height = qAbs(a->y - b->y);
1698 if (height > maxHeight) {
1705 QPathEdge *edge = list.edge(index);
1707 QPathVertex *a = list.vertex(edge->first);
1708 QPathVertex *b = list.vertex(edge->second);
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();
1714 Q_ASSERT(first < y_coords.size() - 1);
1715 Q_ASSERT(last < y_coords.size());
1717 qreal bestY = 0.5 * (y_coords[first] + y_coords[first+1]);
1718 qreal biggestGap = y_coords[first+1] - y_coords[first];
1720 for (int i = first + 1; i < last; ++i) {
1721 qreal gap = y_coords[i+1] - y_coords[i];
1723 if (gap > biggestGap) {
1724 bestY = 0.5 * (y_coords[i] + y_coords[i+1]);
1729 #ifdef QDEBUG_CLIPPER
1730 printf("y: %.9f, gap: %.9f\n", bestY, biggestGap);
1733 if (handleCrossingEdges(list, bestY, mode) && mode == CheckMode)
1740 if (mode == ClipMode)
1746 static void traverse(QWingedEdge &list, int edge, QPathEdge::Traversal traversal)
1748 QWingedEdge::TraversalStatus status;
1750 status.traversal = traversal;
1751 status.direction = QPathEdge::Forward;
1754 int flag = status.traversal == QPathEdge::LeftTraversal ? 1 : 2;
1756 QPathEdge *ep = list.edge(status.edge);
1758 ep->flag |= (flag | (flag << 4));
1760 #ifdef QDEBUG_CLIPPER
1761 qDebug() << "traverse: adding edge " << status.edge << ", mask:" << (flag << 4) <<ep->flag;
1764 status = list.next(status);
1765 } while (status.edge != edge);
1768 struct QCrossingEdge
1773 bool operator<(const QCrossingEdge &edge) const
1779 static bool bool_op(bool a, bool b, QPathClipper::Operation op)
1782 case QPathClipper::BoolAnd:
1784 case QPathClipper::BoolOr: // fall-through
1785 case QPathClipper::Simplify:
1787 case QPathClipper::BoolSub:
1795 bool QWingedEdge::isInside(qreal x, qreal y) const
1798 for (int i = 0; i < edgeCount(); ++i) {
1799 const QPathEdge *ep = edge(i);
1802 int w = ((ep->flag >> 4) ^ (ep->flag >> 5)) & 1;
1807 QPointF a = *vertex(ep->first);
1808 QPointF b = *vertex(ep->second);
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());
1813 if (intersectionX > x)
1821 static QVector<QCrossingEdge> findCrossings(const QWingedEdge &list, qreal y)
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);
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 };
1838 bool QPathClipper::handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode)
1840 QVector<QCrossingEdge> crossings = findCrossings(list, y);
1842 Q_ASSERT(!crossings.isEmpty());
1843 qSort(crossings.begin(), crossings.end());
1850 #ifdef QDEBUG_CLIPPER
1851 qDebug() << "crossings:" << crossings.size();
1853 for (int i = 0; i < crossings.size() - 1; ++i) {
1854 int ei = crossings.at(i).edge;
1855 const QPathEdge *edge = list.edge(ei);
1857 windingA += edge->windingA;
1858 windingB += edge->windingB;
1860 const bool hasLeft = (edge->flag >> 4) & 1;
1861 const bool hasRight = (edge->flag >> 4) & 2;
1863 windingD += hasLeft ^ hasRight;
1865 const bool inA = (windingA & aMask) != 0;
1866 const bool inB = (windingB & bMask) != 0;
1867 const bool inD = (windingD & 0x1) != 0;
1869 const bool inside = bool_op(inA, inB, op);
1870 const bool add = inD ^ inside;
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);
1877 if (mode == CheckMode)
1880 qreal y0 = list.vertex(edge->first)->y;
1881 qreal y1 = list.vertex(edge->second)->y;
1884 if (!(edge->flag & 1))
1885 traverse(list, ei, QPathEdge::LeftTraversal);
1887 if (!(edge->flag & 2))
1888 clear(list, ei, QPathEdge::RightTraversal);
1890 if (!(edge->flag & 1))
1891 clear(list, ei, QPathEdge::LeftTraversal);
1893 if (!(edge->flag & 2))
1894 traverse(list, ei, QPathEdge::RightTraversal);
1899 if (!(edge->flag & 1))
1900 clear(list, ei, QPathEdge::LeftTraversal);
1902 if (!(edge->flag & 2))
1903 clear(list, ei, QPathEdge::RightTraversal);
1912 QList<QPainterPath> toSubpaths(const QPainterPath &path)
1915 QList<QPainterPath> subpaths;
1919 QPainterPath current;
1920 for (int i = 0; i < path.elementCount(); ++i) {
1921 const QPainterPath::Element &e = path.elementAt(i);
1923 case QPainterPath::MoveToElement:
1924 if (current.elementCount() > 1)
1925 subpaths += current;
1926 current = QPainterPath();
1929 case QPainterPath::LineToElement:
1932 case QPainterPath::CurveToElement: {
1933 current.cubicTo(e, path.elementAt(i + 1), path.elementAt(i + 2));
1937 case QPainterPath::CurveToDataElement:
1938 Q_ASSERT(!"toSubpaths(), bad element type");
1943 if (current.elementCount() > 1)
1944 subpaths << current;
1951 Left, Top, Right, Bottom
1954 static bool isVertical(Edge edge)
1956 return edge == Left || edge == Right;
1959 template <Edge edge>
1960 bool compare(const QPointF &p, qreal t)
1975 template <Edge edge>
1976 QPointF intersectLine(const QPointF &a, const QPointF &b, qreal t)
1980 case Left: // fall-through
1982 return line.pointAt((t - a.x()) / (b.x() - a.x()));
1984 return line.pointAt((t - a.y()) / (b.y() - a.y()));
1988 void addLine(QPainterPath &path, const QLineF &line)
1990 if (path.elementCount() > 0)
1991 path.lineTo(line.p1());
1993 path.moveTo(line.p1());
1995 path.lineTo(line.p2());
1998 template <Edge edge>
1999 void clipLine(const QPointF &a, const QPointF &b, qreal t, QPainterPath &result)
2001 bool outA = compare<edge>(a, t);
2002 bool outB = compare<edge>(b, t);
2007 addLine(result, QLineF(intersectLine<edge>(a, b, t), b));
2009 addLine(result, QLineF(a, intersectLine<edge>(a, b, t)));
2011 addLine(result, QLineF(a, b));
2014 void addBezier(QPainterPath &path, const QBezier &bezier)
2016 if (path.elementCount() > 0)
2017 path.lineTo(bezier.pt1());
2019 path.moveTo(bezier.pt1());
2021 path.cubicTo(bezier.pt2(), bezier.pt3(), bezier.pt4());
2024 template <Edge edge>
2025 void clipBezier(const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, qreal t, QPainterPath &result)
2027 QBezier bezier = QBezier::fromPoints(a, b, c, d);
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);
2034 int outCount = int(outA) + int(outB) + int(outC) + int(outD);
2039 if (outCount == 0) {
2040 addBezier(result, bezier);
2044 QTransform flip = isVertical(edge) ? QTransform(0, 1, 1, 0, 0, 0) : QTransform();
2045 QBezier unflipped = bezier;
2046 QBezier flipped = bezier.mapBy(flip);
2048 qreal t0 = 0, t1 = 1;
2049 int stationary = flipped.stationaryYPoints(t0, t1);
2053 points[0] = unflipped.pt1();
2056 int segmentCount = 0;
2057 if (stationary > 0) {
2059 segments[segmentCount] = t0;
2060 points[segmentCount] = unflipped.pointAt(t0);
2062 if (stationary > 1) {
2064 segments[segmentCount] = t1;
2065 points[segmentCount] = unflipped.pointAt(t1);
2068 segments[segmentCount] = 1;
2069 points[segmentCount] = unflipped.pt4();
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);
2077 qreal intersection = flipped.tForY(segments[i], segments[i+1], t);
2080 addBezier(result, unflipped.getSubRange(lastIntersection, intersection));
2082 lastIntersection = intersection;
2087 addBezier(result, unflipped.getSubRange(lastIntersection, 1));
2090 // clips a single subpath against a single edge
2091 template <Edge edge>
2092 QPainterPath clip(const QPainterPath &path, qreal t)
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);
2101 clipBezier<edge>(path.elementAt(i-1), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2), t, result);
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);
2113 QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect)
2115 QList<QPainterPath> subpaths = toSubpaths(path);
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());
2128 bounds = subPath.boundingRect();
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());
2135 if (subPath.elementCount() > 1)
2136 result.addPath(subPath);
2144 QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect)
2146 return intersectPath(path, rect);