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