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
66	QT_BEGIN_NAMESPACE
67
68	static inline bool fuzzyIsNull(qreal d)
69	{
70	if (sizeof(qreal) == sizeof(double))
71	return qAbs(t: d) <= 1e-12;
72	else
73	return qAbs(t: d) <= 1e-5f;
74	}
75
76	static inline bool comparePoints(const QPointF &a, const QPointF &b)
77	{
78	return fuzzyIsNull(d: a.x() - b.x())
79	&& fuzzyIsNull(d: a.y() - b.y());
80	}
81
82	//#define QDEBUG_CLIPPER
83	static qreal dot(const QPointF &a, const QPointF &b)
84	{
85	return a.x() * b.x() + a.y() * b.y();
86	}
87
88	static void normalize(double &x, double &y)
89	{
90	double reciprocal = 1 / qSqrt(v: x * x + y * y);
91	x *= reciprocal;
92	y *= reciprocal;
93	}
94
95	struct QIntersection
96	{
97	qreal alphaA;
98	qreal alphaB;
99
100	QPointF pos;
101	};
102
103	class QIntersectionFinder
104	{
105	public:
106	void produceIntersections(QPathSegments &segments);
107	bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const;
108
109	private:
110	bool linesIntersect(const QLineF &a, const QLineF &b) const;
111	};
112
113	bool 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(a: p1, b: p2) || comparePoints(a: q1, b: q2))
122	return false;
123
124	const bool p1_equals_q1 = comparePoints(a: p1, b: q1);
125	const bool p2_equals_q2 = comparePoints(a: p2, b: q2);
126
127	if (p1_equals_q1 && p2_equals_q2)
128	return true;
129
130	const bool p1_equals_q2 = comparePoints(a: p1, b: q2);
131	const bool p2_equals_q1 = comparePoints(a: p2, b: 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(d: par)) {
142	const QPointF normal(-pDelta.y(), pDelta.x());
143
144	// coinciding?
145	if (qFuzzyIsNull(d: dot(a: normal, b: q1 - p1))) {
146	const qreal dp = dot(a: pDelta, b: pDelta);
147
148	const qreal tq1 = dot(a: pDelta, b: q1 - p1);
149	const qreal tq2 = dot(a: pDelta, b: q2 - p1);
150
151	if ((tq1 > 0 && tq1 < dp) || (tq2 > 0 && tq2 < dp))
152	return true;
153
154	const qreal dq = dot(a: qDelta, b: qDelta);
155
156	const qreal tp1 = dot(a: qDelta, b: p1 - q1);
157	const qreal tp2 = dot(a: qDelta, b: 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
180	bool 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(index: 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(index: i);
194	minX = qMin(a: minX, b: r.left());
195	minY = qMin(a: minY, b: r.top());
196	maxX = qMax(a: maxX, b: r.right());
197	maxY = qMax(a: maxY, b: 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(index: 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(index: 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: a.lineAt(index: i), b: b.lineAt(index: j)))
219	return true;
220	}
221	}
222
223	return false;
224	}
225
226	namespace {
227	struct 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
248	struct RectF
249	{
250	qreal x1;
251	qreal y1;
252	qreal x2;
253	qreal y2;
254	};
255
256	class SegmentTree
257	{
258	public:
259	SegmentTree(QPathSegments &segments);
260
261	void produceIntersections(int segment);
262
263	private:
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	QVector<int> m_index;
272
273	RectF m_bounds;
274
275	QVector<TreeNode> m_tree;
276	QDataBuffer<QIntersection> m_intersections;
277	};
278
279	SegmentTree::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(asize: 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(index: 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(asize: 1);
306
307	TreeNode root = buildTree(first: 0, last: m_index.size(), depth: 0, bounds: m_bounds);
308	m_tree[0] = root;
309	}
310
311	static inline qreal coordinate(const QPointF &pos, int axis)
312	{
313	return axis == 0 ? pos.x() : pos.y();
314	}
315
316	TreeNode 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(asize: 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(i: l);
353	const QRectF &segmentBounds = m_segments.elementBounds(index);
354
355	qreal lowCoordinate = coordinate(pos: segmentBounds.topLeft(), axis: splitAxis);
356
357	if (coordinate(pos: segmentBounds.center(), axis: splitAxis) < split) {
358	qreal highCoordinate = coordinate(pos: segmentBounds.bottomRight(), axis: 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(value1&: m_index[l], value2&: 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, last: l, depth: depth + 1, bounds: lbounds);
381	m_tree[node.index.children.left] = left;
382
383	TreeNode right = buildTree(first: l, last, depth: depth + 1, bounds: rbounds);
384	m_tree[node.index.children.right] = right;
385
386	return node;
387	}
388
389	void 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(a: p1, b: p2) || comparePoints(a: q1, b: q2))
398	return;
399
400	const bool p1_equals_q1 = comparePoints(a: p1, b: q1);
401	const bool p2_equals_q2 = comparePoints(a: p2, b: q2);
402
403	if (p1_equals_q1 && p2_equals_q2)
404	return;
405
406	const bool p1_equals_q2 = comparePoints(a: p1, b: q2);
407	const bool p2_equals_q1 = comparePoints(a: p2, b: 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(d: par)) {
418	const QPointF normal(-pDelta.y(), pDelta.x());
419
420	// coinciding?
421	if (qFuzzyIsNull(d: dot(a: normal, b: q1 - p1))) {
422	const qreal invDp = 1 / dot(a: pDelta, b: pDelta);
423
424	const qreal tq1 = dot(a: pDelta, b: q1 - p1) * invDp;
425	const qreal tq2 = dot(a: pDelta, b: 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(t: 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(t: intersection);
441	}
442
443	const qreal invDq = 1 / dot(a: qDelta, b: qDelta);
444
445	const qreal tp1 = dot(a: qDelta, b: p1 - q1) * invDq;
446	const qreal tp2 = dot(a: qDelta, b: 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(t: 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(t: 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(d: tp);
483	const bool p_one = qFuzzyIsNull(d: tp - 1);
484
485	const bool q_zero = qFuzzyIsNull(d: tq);
486	const bool q_one = qFuzzyIsNull(d: 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(t: intersection);
509	}
510
511	void SegmentTree::produceIntersections(int segment)
512	{
513	const QRectF &segmentBounds = m_segments.elementBounds(index: 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(node: m_tree.at(i: 0), segment, segmentBounds: sbounds, nodeBounds: m_bounds, axis: 0);
522	}
523
524	void SegmentTree::produceIntersectionsLeaf(const TreeNode &node, int segment)
525	{
526	const QRectF &r1 = m_segments.elementBounds(index: segment);
527	const QLineF lineA = m_segments.lineAt(index: 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(index: 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(index: other);
544
545	intersectLines(a: lineA, b: lineB, intersections&: 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(i: k).alphaA;
550	j_isect.t = m_intersections.at(i: k).alphaB;
551
552	i_isect.vertex = j_isect.vertex = m_segments.addPoint(point: m_intersections.at(i: k).pos);
553
554	i_isect.next = 0;
555	j_isect.next = 0;
556
557	m_segments.addIntersection(index: segment, intersection: i_isect);
558	m_segments.addIntersection(index: other, intersection: j_isect);
559	}
560	}
561	}
562
563	void 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(node: m_tree.at(i: node.index.children.left), segment, segmentBounds, nodeBounds: lbounds, axis: !axis);
578
579	if (segment > node.lowestRightIndex && (&segmentBounds.x2)[axis] >= node.splitRight)
580	produceIntersections(node: m_tree.at(i: node.index.children.right), segment, segmentBounds, nodeBounds: rbounds, axis: !axis);
581	}
582
583	}
584
585	void QIntersectionFinder::produceIntersections(QPathSegments &segments)
586	{
587	SegmentTree tree(segments);
588
589	for (int i = 0; i < segments.segments(); ++i)
590	tree.produceIntersections(segment: i);
591	}
592
593	class QKdPointTree
594	{
595	public:
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(size: 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(begin: 0, end: 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(i: m_rootNode);
631	}
632
633	inline int nextId()
634	{
635	return m_id++;
636	}
637
638	private:
639	const QPathSegments *m_segments;
640	QDataBuffer<Node> m_nodes;
641
642	int m_rootNode;
643	int m_id;
644	};
645
646	template <typename T>
647	void 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
661	static 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
668	int QKdPointTree::build(int begin, int end, int depth)
669	{
670	Q_ASSERT(end > begin);
671
672	const qreal pivot = component(point: m_segments->pointAt(i: m_nodes.at(i: begin).point), i: depth & 1);
673
674	int first = begin + 1;
675	int last = end - 1;
676
677	while (first <= last) {
678	const qreal value = component(point: m_segments->pointAt(i: m_nodes.at(i: first).point), i: depth & 1);
679
680	if (value < pivot)
681	++first;
682	else {
683	qSwap(value1&: m_nodes.at(i: first), value2&: m_nodes.at(i: last));
684	--last;
685	}
686	}
687
688	qSwap(value1&: m_nodes.at(i: last), value2&: m_nodes.at(i: begin));
689
690	if (last > begin)
691	m_nodes.at(i: last).left = &m_nodes.at(i: build(begin, end: last, depth: depth + 1));
692	else
693	m_nodes.at(i: last).left = nullptr;
694
695	if (last + 1 < end)
696	m_nodes.at(i: last).right = &m_nodes.at(i: build(begin: last + 1, end, depth: depth + 1));
697	else
698	m_nodes.at(i: last).right = nullptr;
699
700	return last;
701	}
702
703	class QKdPointFinder
704	{
705	public:
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(i: point).x();
712	pointComponents[1] = segments.pointAt(i: 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(i: 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(d: pivot - value)) {
728	const qreal pivot2 = pivotComponents[(depth + 1) & 1];
729	const qreal value2 = pointComponents[(depth + 1) & 1];
730
731	if (fuzzyIsNull(d: 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
751	private:
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
759	void 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>)(node&: *tree.rootNode(), t&: 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(i: m_segments.at(i).va);
781	m_segments.at(i).vb = pointIndices.at(i: 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(i: m_intersections.at(i).vertex);
786
787	m_points.swap(other&: mergedPoints);
788	}
789	}
790
791	void QWingedEdge::intersectAndAdd()
792	{
793	QIntersectionFinder finder;
794	finder.produceIntersections(segments&: m_segments);
795
796	m_segments.mergePoints();
797
798	for (int i = 0; i < m_segments.points(); ++i)
799	addVertex(p: 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(index: i);
806
807	const QPathSegments::Intersection *isect = m_segments.intersectionAt(index: 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(first: intersections.data(), last: intersections.data() + intersections.size());
819
820	int first = m_segments.segmentAt(index: i).va;
821	int second = m_segments.segmentAt(index: i).vb;
822
823	int last = first;
824	for (int j = 0; j < intersections.size(); ++j) {
825	const QPathSegments::Intersection &isect = intersections.at(i: j);
826
827	QPathEdge *ep = edge(edge: addEdge(vertexA: last, vertexB: isect.vertex));
828
829	if (ep) {
830	const int dir = m_segments.pointAt(i: last).y() < m_segments.pointAt(i: 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(edge: addEdge(vertexA: last, vertexB: second));
841
842	if (ep) {
843	const int dir = m_segments.pointAt(i: last).y() < m_segments.pointAt(i: second).y() ? 1 : -1;
844	if (pathId == 0)
845	ep->windingA += dir;
846	else
847	ep->windingB += dir;
848	}
849	}
850	}
851
852	QWingedEdge::QWingedEdge() :
853	m_edges(0),
854	m_vertices(0),
855	m_segments(0)
856	{
857	}
858
859	QWingedEdge::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(path: clip);
866
867	intersectAndAdd();
868	}
869
870	QWingedEdge::TraversalStatus QWingedEdge::next(const QWingedEdge::TraversalStatus &status) const
871	{
872	const QPathEdge *sp = edge(edge: status.edge);
873	Q_ASSERT(sp);
874
875	TraversalStatus result;
876	result.edge = sp->next(traversal: status.traversal, direction: status.direction);
877	result.traversal = status.traversal;
878	result.direction = status.direction;
879
880	const QPathEdge *rp = edge(edge: result.edge);
881	Q_ASSERT(rp);
882
883	if (sp->vertex(direction: status.direction) == rp->vertex(direction: status.direction))
884	result.flip();
885
886	return result;
887	}
888
889	static bool isLine(const QBezier &bezier)
890	{
891	const bool equal_1_2 = comparePoints(a: bezier.pt1(), b: bezier.pt2());
892	const bool equal_2_3 = comparePoints(a: bezier.pt2(), b: bezier.pt3());
893	const bool equal_3_4 = comparePoints(a: bezier.pt3(), b: bezier.pt4());
894
895	// point?
896	if (equal_1_2 && equal_2_3 && equal_3_4)
897	return true;
898
899	if (comparePoints(a: bezier.pt1(), b: 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
905	void 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
916	void 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: i+2);
929	else
930	currentPoint = path.elementAt(i);
931
932	if (i > 0 && comparePoints(a: m_points.at(i: lastMoveTo), b: 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(a: m_points.at(i: last), b: m_points.at(i: 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(p1: m_points.at(i: last), p2: path.elementAt(i), p3: path.elementAt(i: i+1), p4: path.elementAt(i: 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>(a: 64, b: qMax(a: bounds.width(), b: 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: 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(a: m_points.at(i: last), b: m_points.at(i: 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(index: 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(value1&: x1, value2&: x2);
997	if (y2 < y1)
998	qSwap(value1&: y1, value2&: y2);
999
1000	m_segments.at(i).bounds = QRectF(x1, y1, x2 - x1, y2 - y1);
1001	}
1002
1003	++m_pathId;
1004	}
1005
1006	qreal QWingedEdge::delta(int vertex, int a, int b) const
1007	{
1008	const QPathEdge *ap = edge(edge: a);
1009	const QPathEdge *bp = edge(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
1030	QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const
1031	{
1032	const QPathVertex *vp = vertex(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(edge: vp->edge)->directionTo(vertex: 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(vertex: vi, a: ei, b: 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(edge: status.edge)->vertex(direction: 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
1085	void QWingedEdge::removeEdge(int ei)
1086	{
1087	QPathEdge *ep = edge(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(edge: forwardRight.edge)->setNext(traversal: forwardRight.traversal, direction: forwardRight.direction, next: forwardLeft.edge);
1110	edge(edge: forwardLeft.edge)->setNext(traversal: forwardLeft.traversal, direction: forwardLeft.direction, next: forwardRight.edge);
1111
1112	edge(edge: backwardRight.edge)->setNext(traversal: backwardRight.traversal, direction: backwardRight.direction, next: backwardLeft.edge);
1113	edge(edge: backwardLeft.edge)->setNext(traversal: backwardLeft.traversal, direction: backwardLeft.direction, next: backwardRight.edge);
1114
1115	ep->setNext(direction: QPathEdge::Forward, next: ei);
1116	ep->setNext(direction: QPathEdge::Backward, next: ei);
1117
1118	QPathVertex *a = vertex(vertex: ep->first);
1119	QPathVertex *b = vertex(vertex: ep->second);
1120
1121	a->edge = backwardRight.edge;
1122	b->edge = forwardRight.edge;
1123	}
1124
1125	static int commonEdge(const QWingedEdge &list, int a, int b)
1126	{
1127	const QPathVertex *ap = list.vertex(vertex: a);
1128	Q_ASSERT(ap);
1129
1130	const QPathVertex *bp = list.vertex(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(edge: status.edge)->directionTo(vertex: a);
1139	status.traversal = QPathEdge::RightTraversal;
1140
1141	do {
1142	const QPathEdge *ep = list.edge(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
1155	static 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(x&: vx, y&: 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
1182	int QWingedEdge::addEdge(const QPointF &a, const QPointF &b)
1183	{
1184	int fi = insert(vertex: a);
1185	int si = insert(vertex: b);
1186
1187	return addEdge(vertexA: fi, vertexB: si);
1188	}
1189
1190	int QWingedEdge::addEdge(int fi, int si)
1191	{
1192	if (fi == si)
1193	return -1;
1194
1195	int common = commonEdge(list: *this, a: fi, b: 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(vertex: fi);
1204	QPathVertex *sp = vertex(vertex: si);
1205
1206	QPathEdge *ep = edge(edge: ei);
1207
1208	const QPointF tangent = QPointF(*sp) - QPointF(*fp);
1209	ep->angle = computeAngle(v: 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(direction: dirs[i], next: ei);
1226	} else {
1227	int vi = ep->vertex(direction: dirs[i]);
1228	Q_ASSERT(vertex(vi) == vertices[i]);
1229
1230	TraversalStatus os = findInsertStatus(vi, ei);
1231	QPathEdge *op = edge(edge: os.edge);
1232
1233	Q_ASSERT(vertex(op->vertex(os.direction)) == vertices[i]);
1234
1235	TraversalStatus ns = next(status: os);
1236	ns.flipDirection();
1237	QPathEdge *np = edge(edge: ns.edge);
1238
1239	op->setNext(traversal: os.traversal, direction: os.direction, next: ei);
1240	np->setNext(traversal: ns.traversal, direction: ns.direction, next: ei);
1241
1242	int oe = os.edge;
1243	int ne = ns.edge;
1244
1245	os = next(status: os);
1246	ns = next(status: 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(traversal: os.traversal, direction: os.direction, next: oe);
1255	ep->setNext(traversal: ns.traversal, direction: ns.direction, next: 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
1267	int 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(p1: v.x, p2: vertex.x) && qFuzzyCompare(p1: v.y, p2: vertex.y)) {
1277	return i;
1278	}
1279	}
1280	}
1281
1282	m_vertices << vertex;
1283	return m_vertices.size() - 1;
1284	}
1285
1286	static 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(i: elementCount - 1);
1291	if (middle.type == QPainterPath::LineToElement) {
1292	const QPointF first = path.elementAt(i: 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(d: dot(a: p, b: d2))) {
1299	path.setElementPositionAt(i: elementCount - 1, x: point.x(), y: point.y());
1300	return;
1301	}
1302	}
1303	}
1304
1305	path.lineTo(p: point);
1306	}
1307
1308	static 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(p: *list.vertex(vertex: list.edge(edge)->first));
1316
1317	do {
1318	const QPathEdge *ep = list.edge(edge: status.edge);
1319
1320	addLineTo(path, point: *list.vertex(vertex: ep->vertex(direction: 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
1331	void QWingedEdge::simplify()
1332	{
1333	for (int i = 0; i < edgeCount(); ++i) {
1334	const QPathEdge *ep = edge(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(ei: i);
1340
1341	ep->flag &= ~flag;
1342	}
1343	}
1344	}
1345
1346	QPainterPath QWingedEdge::toPath() const
1347	{
1348	QPainterPath path;
1349
1350	for (int i = 0; i < edgeCount(); ++i) {
1351	const QPathEdge *ep = edge(edge: i);
1352
1353	if (ep->flag & 16) {
1354	add(path, list: *this, edge: i, traversal: QPathEdge::LeftTraversal);
1355	}
1356
1357	if (ep->flag & 32)
1358	add(path, list: *this, edge: i, traversal: QPathEdge::RightTraversal);
1359	}
1360
1361	return path;
1362	}
1363
1364	bool QPathClipper::intersect()
1365	{
1366	if (subjectPath == clipPath)
1367	return true;
1368
1369	QRectF r1 = subjectPath.controlPointRect();
1370	QRectF r2 = clipPath.controlPointRect();
1371	if (qMax(a: r1.x(), b: r2.x()) > qMin(a: r1.x() + r1.width(), b: r2.x() + r2.width()) ||
1372	qMax(a: r1.y(), b: r2.y()) > qMin(a: r1.y() + r1.height(), b: r2.y() + r2.height())) {
1373	// no way we could intersect
1374	return false;
1375	}
1376
1377	bool subjectIsRect = pathToRect(path: subjectPath);
1378	bool clipIsRect = pathToRect(path: clipPath);
1379
1380	if (subjectIsRect && clipIsRect)
1381	return true;
1382	else if (subjectIsRect)
1383	return clipPath.intersects(rect: r1);
1384	else if (clipIsRect)
1385	return subjectPath.intersects(rect: 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(p: point) && subjectPath.contains(pt: 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(p: point) && clipPath.contains(pt: point))
1408	return true;
1409	}
1410	}
1411
1412	return false;
1413	}
1414
1415	bool QPathClipper::contains()
1416	{
1417	if (subjectPath == clipPath)
1418	return false;
1419
1420	QRectF r1 = subjectPath.controlPointRect();
1421	QRectF r2 = clipPath.controlPointRect();
1422	if (qMax(a: r1.x(), b: r2.x()) > qMin(a: r1.x() + r1.width(), b: r2.x() + r2.width()) ||
1423	qMax(a: r1.y(), b: r2.y()) > qMin(a: r1.y() + r1.height(), b: r2.y() + r2.height())) {
1424	// no intersection -> not contained
1425	return false;
1426	}
1427
1428	bool clipIsRect = pathToRect(path: clipPath);
1429	if (clipIsRect)
1430	return subjectPath.contains(rect: 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(p: point) || !subjectPath.contains(pt: point))
1445	return false;
1446	}
1447	}
1448
1449	return true;
1450	}
1451
1452	QPathClipper::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
1461	static 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(edge: status.edge)->flag |= 1;
1471	else
1472	list.edge(edge: status.edge)->flag |= 2;
1473
1474	status = list.next(status);
1475	} while (status.edge != edge);
1476	}
1477
1478	template <typename InputIterator>
1479	InputIterator qFuzzyFind(InputIterator first, InputIterator last, qreal val)
1480	{
1481	while (first != last && !QT_PREPEND_NAMESPACE(qFuzzyCompare)(p1: qreal(*first), p2: qreal(val)))
1482	++first;
1483	return first;
1484	}
1485
1486	static bool fuzzyCompare(qreal a, qreal b)
1487	{
1488	return qFuzzyCompare(p1: a, p2: b);
1489	}
1490
1491	bool QPathClipper::pathToRect(const QPainterPath &path, QRectF *rect)
1492	{
1493	if (path.elementCount() != 5)
1494	return false;
1495
1496	const bool mightBeRect = path.elementAt(i: 0).isMoveTo()
1497	&& path.elementAt(i: 1).isLineTo()
1498	&& path.elementAt(i: 2).isLineTo()
1499	&& path.elementAt(i: 3).isLineTo()
1500	&& path.elementAt(i: 4).isLineTo();
1501
1502	if (!mightBeRect)
1503	return false;
1504
1505	const qreal x1 = path.elementAt(i: 0).x;
1506	const qreal y1 = path.elementAt(i: 0).y;
1507
1508	const qreal x2 = path.elementAt(i: 1).x;
1509	const qreal y2 = path.elementAt(i: 2).y;
1510
1511	if (path.elementAt(i: 1).y != y1)
1512	return false;
1513
1514	if (path.elementAt(i: 2).x != x2)
1515	return false;
1516
1517	if (path.elementAt(i: 3).x != x1 || path.elementAt(i: 3).y != y2)
1518	return false;
1519
1520	if (path.elementAt(i: 4).x != x1 || path.elementAt(i: 4).y != y1)
1521	return false;
1522
1523	if (rect)
1524	rect->setCoords(xp1: x1, yp1: y1, xp2: x2, yp2: y2);
1525
1526	return true;
1527	}
1528
1529
1530	QPainterPath 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(path: subjectPath, rect: nullptr);
1539	bool clipIsRect = pathToRect(path: clipPath, rect: nullptr);
1540
1541	const QRectF clipBounds = clipPath.boundingRect();
1542	const QRectF subjectBounds = subjectPath.boundingRect();
1543
1544	if (!clipBounds.intersects(r: 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(path: clipPath);
1554	} else if (result.fillRule() == Qt::WindingFill) {
1555	result = result.simplified();
1556	result.addPath(path: clipPath);
1557	} else {
1558	result.addPath(path: clipPath.simplified());
1559	}
1560	return result;
1561	}
1562	default:
1563	break;
1564	}
1565	}
1566
1567	if (clipBounds.contains(r: 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(r: clipBounds)) {
1581	if (subjectIsRect) {
1582	switch (op) {
1583	case BoolSub:
1584	if (clipPath.fillRule() == Qt::OddEvenFill) {
1585	QPainterPath result = clipPath;
1586	result.addRect(rect: subjectBounds);
1587	return result;
1588	} else {
1589	QPainterPath result = clipPath.simplified();
1590	result.addRect(rect: 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(path: clipPath, rect: subjectBounds);
1606	else if (clipIsRect)
1607	return intersect(path: subjectPath, rect: clipBounds);
1608	}
1609	}
1610
1611	QWingedEdge list(subjectPath, clipPath);
1612
1613	doClip(list, mode: ClipMode);
1614
1615	QPainterPath path = list.toPath();
1616	return path;
1617	}
1618
1619	bool QPathClipper::doClip(QWingedEdge &list, ClipperMode mode)
1620	{
1621	QVector<qreal> y_coords;
1622	y_coords.reserve(asize: list.vertexCount());
1623	for (int i = 0; i < list.vertexCount(); ++i)
1624	y_coords << list.vertex(vertex: i)->y;
1625
1626	std::sort(first: y_coords.begin(), last: y_coords.end());
1627	y_coords.erase(abegin: std::unique(first: y_coords.begin(), last: y_coords.end(), binary_pred: fuzzyCompare), aend: 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(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(vertex: edge->first);
1649	QPathVertex *b = list.vertex(vertex: edge->second);
1650
1651	if (qFuzzyCompare(p1: a->y, p2: b->y))
1652	continue;
1653
1654	found = true;
1655
1656	qreal height = qAbs(t: 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(edge: index);
1665
1666	QPathVertex *a = list.vertex(vertex: edge->first);
1667	QPathVertex *b = list.vertex(vertex: edge->second);
1668
1669	// FIXME: this can be optimized by using binary search
1670	const int first = qFuzzyFind(first: y_coords.cbegin(), last: y_coords.cend(), val: qMin(a: a->y, b: b->y)) - y_coords.cbegin();
1671	const int last = qFuzzyFind(first: y_coords.cbegin() + first, last: y_coords.cend(), val: qMax(a: a->y, b: 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(i: first + 1) - y_coords.at(i: first);
1677	int bestIdx = first;
1678	for (int i = first + 1; i < last; ++i) {
1679	qreal gap = y_coords.at(i: 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(i: bestIdx) + y_coords.at(i: bestIdx + 1));
1687
1688	#ifdef QDEBUG_CLIPPER
1689	printf("y: %.9f, gap: %.9f\n", bestY, biggestGap);
1690	#endif
1691
1692	if (handleCrossingEdges(list, y: 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
1705	static 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(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
1727	struct QCrossingEdge
1728	{
1729	int edge;
1730	qreal x;
1731
1732	bool operator<(const QCrossingEdge &edge) const
1733	{
1734	return x < edge.x;
1735	}
1736	};
1737	Q_DECLARE_TYPEINFO(QCrossingEdge, Q_PRIMITIVE_TYPE);
1738
1739	static 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
1755	bool 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(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(vertex: ep->first);
1768	QPointF b = *vertex(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
1781	static QVector<QCrossingEdge> findCrossings(const QWingedEdge &list, qreal y)
1782	{
1783	QVector<QCrossingEdge> crossings;
1784	for (int i = 0; i < list.edgeCount(); ++i) {
1785	const QPathEdge *edge = list.edge(edge: i);
1786	QPointF a = *list.vertex(vertex: edge->first);
1787	QPointF b = *list.vertex(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 = { .edge: i, .x: intersection };
1792	crossings << edge;
1793	}
1794	}
1795	return crossings;
1796	}
1797
1798	bool QPathClipper::handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode)
1799	{
1800	QVector<QCrossingEdge> crossings = findCrossings(list, y);
1801
1802	Q_ASSERT(!crossings.isEmpty());
1803	std::sort(first: crossings.begin(), last: 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(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(a: inA, b: 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(vertex: edge->first)->y;
1841	qreal y1 = list.vertex(vertex: edge->second)->y;
1842
1843	if (y0 < y1) {
1844	if (!(edge->flag & 1))
1845	traverse(list, edge: ei, traversal: QPathEdge::LeftTraversal);
1846
1847	if (!(edge->flag & 2))
1848	clear(list, edge: ei, traversal: QPathEdge::RightTraversal);
1849	} else {
1850	if (!(edge->flag & 1))
1851	clear(list, edge: ei, traversal: QPathEdge::LeftTraversal);
1852
1853	if (!(edge->flag & 2))
1854	traverse(list, edge: ei, traversal: QPathEdge::RightTraversal);
1855	}
1856
1857	++windingD;
1858	} else {
1859	if (!(edge->flag & 1))
1860	clear(list, edge: ei, traversal: QPathEdge::LeftTraversal);
1861
1862	if (!(edge->flag & 2))
1863	clear(list, edge: ei, traversal: QPathEdge::RightTraversal);
1864	}
1865	}
1866
1867	return false;
1868	}
1869
1870	namespace {
1871
1872	QVector<QPainterPath> toSubpaths(const QPainterPath &path)
1873	{
1874
1875	QVector<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(p: e);
1888	break;
1889	case QPainterPath::LineToElement:
1890	current.lineTo(p: e);
1891	break;
1892	case QPainterPath::CurveToElement: {
1893	current.cubicTo(ctrlPt1: e, ctrlPt2: path.elementAt(i: i + 1), endPt: path.elementAt(i: 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
1909	enum Edge
1910	{
1911	Left, Top, Right, Bottom
1912	};
1913
1914	static bool isVertical(Edge edge)
1915	{
1916	return edge == Left || edge == Right;
1917	}
1918
1919	template <Edge edge>
1920	bool 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
1935	template <Edge edge>
1936	QPointF 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: (t - a.x()) / (b.x() - a.x()));
1943	default:
1944	return line.pointAt(t: (t - a.y()) / (b.y() - a.y()));
1945	}
1946	}
1947
1948	void addLine(QPainterPath &path, const QLineF &line)
1949	{
1950	if (path.elementCount() > 0)
1951	path.lineTo(p: line.p1());
1952	else
1953	path.moveTo(p: line.p1());
1954
1955	path.lineTo(p: line.p2());
1956	}
1957
1958	template <Edge edge>
1959	void 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(path&: result, line: QLineF(intersectLine<edge>(a, b, t), b));
1968	else if(outB)
1969	addLine(path&: result, line: QLineF(a, intersectLine<edge>(a, b, t)));
1970	else
1971	addLine(path&: result, line: QLineF(a, b));
1972	}
1973
1974	void addBezier(QPainterPath &path, const QBezier &bezier)
1975	{
1976	if (path.elementCount() > 0)
1977	path.lineTo(p: bezier.pt1());
1978	else
1979	path.moveTo(p: bezier.pt1());
1980
1981	path.cubicTo(ctrlPt1: bezier.pt2(), ctrlPt2: bezier.pt3(), endPt: bezier.pt4());
1982	}
1983
1984	template <Edge edge>
1985	void clipBezier(const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, qreal t, QPainterPath &result)
1986	{
1987	QBezier bezier = QBezier::fromPoints(p1: a, p2: b, p3: c, p4: 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(path&: 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(transform: 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(t: t0);
2021	}
2022	if (stationary > 1) {
2023	++segmentCount;
2024	segments[segmentCount] = t1;
2025	points[segmentCount] = unflipped.pointAt(t: 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(t0: segments[i], t1: segments[i+1], y: t);
2038
2039	if (outB)
2040	addBezier(path&: result, bezier: unflipped.getSubRange(t0: lastIntersection, t1: intersection));
2041
2042	lastIntersection = intersection;
2043	}
2044	}
2045
2046	if (!outB)
2047	addBezier(path&: result, bezier: unflipped.getSubRange(t0: lastIntersection, t1: 1));
2048	}
2049
2050	// clips a single subpath against a single edge
2051	template <Edge edge>
2052	QPainterPath 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: i-1), path.elementAt(i), t, result);
2060	} else {
2061	clipBezier<edge>(path.elementAt(i: i-1), path.elementAt(i), path.elementAt(i: i+1), path.elementAt(i: i+2), t, result);
2062	i += 2;
2063	}
2064	}
2065
2066	int last = path.elementCount() - 1;
2067	if (QPointF(path.elementAt(i: last)) != QPointF(path.elementAt(i: 0)))
2068	clipLine<edge>(path.elementAt(i: last), path.elementAt(i: 0), t, result);
2069
2070	return result;
2071	}
2072
2073	QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect)
2074	{
2075	QVector<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(r: rect)) {
2083	if (bounds.left() < rect.left())
2084	subPath = clip<Left>(path: subPath, t: rect.left());
2085	if (bounds.right() > rect.right())
2086	subPath = clip<Right>(path: subPath, t: rect.right());
2087
2088	bounds = subPath.boundingRect();
2089
2090	if (bounds.top() < rect.top())
2091	subPath = clip<Top>(path: subPath, t: rect.top());
2092	if (bounds.bottom() > rect.bottom())
2093	subPath = clip<Bottom>(path: subPath, t: rect.bottom());
2094
2095	if (subPath.elementCount() > 1)
2096	result.addPath(path: 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
2109	QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect)
2110	{
2111	return intersectPath(path, rect);
2112	}
2113
2114	QT_END_NAMESPACE
2115