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