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 "qpainterpath.h"
5	#include "qpainterpath_p.h"
6
7	#include <qbitmap.h>
8	#include <qdebug.h>
9	#include <qiodevice.h>
10	#include <qlist.h>
11	#include <qpen.h>
12	#include <qpolygon.h>
13	#include <qtextlayout.h>
14	#include <qvarlengtharray.h>
15	#include <qmath.h>
16
17	#include <private/qbezier_p.h>
18	#include <private/qfontengine_p.h>
19	#include <private/qnumeric_p.h>
20	#include <private/qobject_p.h>
21	#include <private/qpathclipper_p.h>
22	#include <private/qstroker_p.h>
23	#include <private/qtextengine_p.h>
24
25	#include <cmath>
26
27	#include <limits.h>
28
29	#if 0
30	#include <performance.h>
31	#else
32	#define PM_INIT
33	#define PM_MEASURE(x)
34	#define PM_DISPLAY
35	#endif
36
37	QT_BEGIN_NAMESPACE
38
39	static inline bool isValidCoord(qreal c)
40	{
41	if (sizeof(qreal) >= sizeof(double))
42	return qIsFinite(d: c) && fabs(x: c) < 1e128;
43	else
44	return qIsFinite(d: c) && fabsf(x: float(c)) < 1e16f;
45	}
46
47	static bool hasValidCoords(QPointF p)
48	{
49	return isValidCoord(c: p.x()) && isValidCoord(c: p.y());
50	}
51
52	static bool hasValidCoords(QRectF r)
53	{
54	return isValidCoord(c: r.x()) && isValidCoord(c: r.y()) && isValidCoord(c: r.width()) && isValidCoord(c: r.height());
55	}
56
57	// This value is used to determine the length of control point vectors
58	// when approximating arc segments as curves. The factor is multiplied
59	// with the radius of the circle.
60
61	// #define QPP_DEBUG
62	// #define QPP_STROKE_DEBUG
63	//#define QPP_FILLPOLYGONS_DEBUG
64
65	QPainterPath qt_stroke_dash(const QPainterPath &path, qreal *dashes, int dashCount);
66
67	void qt_find_ellipse_coords(const QRectF &r, qreal angle, qreal length,
68	QPointF* startPoint, QPointF *endPoint)
69	{
70	if (r.isNull()) {
71	if (startPoint)
72	*startPoint = QPointF();
73	if (endPoint)
74	*endPoint = QPointF();
75	return;
76	}
77
78	qreal w2 = r.width() / 2;
79	qreal h2 = r.height() / 2;
80
81	qreal angles[2] = { angle, angle + length };
82	QPointF *points[2] = { startPoint, endPoint };
83
84	for (int i = 0; i < 2; ++i) {
85	if (!points[i])
86	continue;
87
88	qreal theta = angles[i] - 360 * qFloor(v: angles[i] / 360);
89	qreal t = theta / 90;
90	// truncate
91	int quadrant = int(t);
92	t -= quadrant;
93
94	t = qt_t_for_arc_angle(angle: 90 * t);
95
96	// swap x and y?
97	if (quadrant & 1)
98	t = 1 - t;
99
100	qreal a, b, c, d;
101	QBezier::coefficients(t, a, b, c, d);
102	QPointF p(a + b + c*QT_PATH_KAPPA, d + c + b*QT_PATH_KAPPA);
103
104	// left quadrants
105	if (quadrant == 1 || quadrant == 2)
106	p.rx() = -p.x();
107
108	// top quadrants
109	if (quadrant == 0 || quadrant == 1)
110	p.ry() = -p.y();
111
112	*points[i] = r.center() + QPointF(w2 * p.x(), h2 * p.y());
113	}
114	}
115
116	#ifdef QPP_DEBUG
117	static void qt_debug_path(const QPainterPath &path)
118	{
119	const char *names[] = {
120	"MoveTo ",
121	"LineTo ",
122	"CurveTo ",
123	"CurveToData"
124	};
125
126	printf("\nQPainterPath: elementCount=%d\n", path.elementCount());
127	for (int i=0; i<path.elementCount(); ++i) {
128	const QPainterPath::Element &e = path.elementAt(i);
129	Q_ASSERT(e.type >= 0 && e.type <= QPainterPath::CurveToDataElement);
130	printf(" - %3d:: %s, (%.2f, %.2f)\n", i, names[e.type], e.x, e.y);
131	}
132	}
133	#endif
134
135	/*!
136	\class QPainterPath
137	\ingroup painting
138	\inmodule QtGui
139
140	\reentrant
141
142	\brief The QPainterPath class provides a container for painting operations,
143	enabling graphical shapes to be constructed and reused.
144
145	A painter path is an object composed of a number of graphical
146	building blocks, such as rectangles, ellipses, lines, and curves.
147	Building blocks can be joined in closed subpaths, for example as a
148	rectangle or an ellipse. A closed path has coinciding start and
149	end points. Or they can exist independently as unclosed subpaths,
150	such as lines and curves.
151
152	A QPainterPath object can be used for filling, outlining, and
153	clipping. To generate fillable outlines for a given painter path,
154	use the QPainterPathStroker class. The main advantage of painter
155	paths over normal drawing operations is that complex shapes only
156	need to be created once; then they can be drawn many times using
157	only calls to the QPainter::drawPath() function.
158
159	QPainterPath provides a collection of functions that can be used
160	to obtain information about the path and its elements. In addition
161	it is possible to reverse the order of the elements using the
162	toReversed() function. There are also several functions to convert
163	this painter path object into a polygon representation.
164
165	\section1 Composing a QPainterPath
166
167	A QPainterPath object can be constructed as an empty path, with a
168	given start point, or as a copy of another QPainterPath object.
169	Once created, lines and curves can be added to the path using the
170	lineTo(), arcTo(), cubicTo() and quadTo() functions. The lines and
171	curves stretch from the currentPosition() to the position passed
172	as argument.
173
174	The currentPosition() of the QPainterPath object is always the end
175	position of the last subpath that was added (or the initial start
176	point). Use the moveTo() function to move the currentPosition()
177	without adding a component. The moveTo() function implicitly
178	starts a new subpath, and closes the previous one. Another way of
179	starting a new subpath is to call the closeSubpath() function
180	which closes the current path by adding a line from the
181	currentPosition() back to the path's start position. Note that the
182	new path will have (0, 0) as its initial currentPosition().
183
184	QPainterPath class also provides several convenience functions to
185	add closed subpaths to a painter path: addEllipse(), addPath(),
186	addRect(), addRegion() and addText(). The addPolygon() function
187	adds an \e unclosed subpath. In fact, these functions are all
188	collections of moveTo(), lineTo() and cubicTo() operations.
189
190	In addition, a path can be added to the current path using the
191	connectPath() function. But note that this function will connect
192	the last element of the current path to the first element of given
193	one by adding a line.
194
195	Below is a code snippet that shows how a QPainterPath object can
196	be used:
197
198	\table 70%
199	\row
200	\li \inlineimage qpainterpath-construction.png
201	\li
202	\snippet code/src_gui_painting_qpainterpath.cpp 0
203	\endtable
204
205	The painter path is initially empty when constructed. We first add
206	a rectangle, which is a closed subpath. Then we add two bezier
207	curves which together form a closed subpath even though they are
208	not closed individually. Finally we draw the entire path. The path
209	is filled using the default fill rule, Qt::OddEvenFill. Qt
210	provides two methods for filling paths:
211
212	\table
213	\header
214	\li Qt::OddEvenFill
215	\li Qt::WindingFill
216	\row
217	\li \inlineimage qt-fillrule-oddeven.png
218	\li \inlineimage qt-fillrule-winding.png
219	\endtable
220
221	See the Qt::FillRule documentation for the definition of the
222	rules. A painter path's currently set fill rule can be retrieved
223	using the fillRule() function, and altered using the setFillRule()
224	function.
225
226	\section1 QPainterPath Information
227
228	The QPainterPath class provides a collection of functions that
229	returns information about the path and its elements.
230
231	The currentPosition() function returns the end point of the last
232	subpath that was added (or the initial start point). The
233	elementAt() function can be used to retrieve the various subpath
234	elements, the \e number of elements can be retrieved using the
235	elementCount() function, and the isEmpty() function tells whether
236	this QPainterPath object contains any elements at all.
237
238	The controlPointRect() function returns the rectangle containing
239	all the points and control points in this path. This function is
240	significantly faster to compute than the exact boundingRect()
241	which returns the bounding rectangle of this painter path with
242	floating point precision.
243
244	Finally, QPainterPath provides the contains() function which can
245	be used to determine whether a given point or rectangle is inside
246	the path, and the intersects() function which determines if any of
247	the points inside a given rectangle also are inside this path.
248
249	\section1 QPainterPath Conversion
250
251	For compatibility reasons, it might be required to simplify the
252	representation of a painter path: QPainterPath provides the
253	toFillPolygon(), toFillPolygons() and toSubpathPolygons()
254	functions which convert the painter path into a polygon. The
255	toFillPolygon() returns the painter path as one single polygon,
256	while the two latter functions return a list of polygons.
257
258	The toFillPolygons() and toSubpathPolygons() functions are
259	provided because it is usually faster to draw several small
260	polygons than to draw one large polygon, even though the total
261	number of points drawn is the same. The difference between the two
262	is the \e number of polygons they return: The toSubpathPolygons()
263	creates one polygon for each subpath regardless of intersecting
264	subpaths (i.e. overlapping bounding rectangles), while the
265	toFillPolygons() functions creates only one polygon for
266	overlapping subpaths.
267
268	The toFillPolygon() and toFillPolygons() functions first convert
269	all the subpaths to polygons, then uses a rewinding technique to
270	make sure that overlapping subpaths can be filled using the
271	correct fill rule. Note that rewinding inserts additional lines in
272	the polygon so the outline of the fill polygon does not match the
273	outline of the path.
274
275	\section1 Examples
276
277	Qt provides the \l {painting/painterpaths}{Painter Paths Example}
278	and the \l {painting/deform}{Vector Deformation example} which are
279	located in Qt's example directory.
280
281	The \l {painting/painterpaths}{Painter Paths Example} shows how
282	painter paths can be used to build complex shapes for rendering
283	and lets the user experiment with the filling and stroking. The
284	\l {painting/deform}{Vector Deformation Example} shows how to use
285	QPainterPath to draw text.
286
287	\table
288	\header
289	\li \l {painting/painterpaths}{Painter Paths Example}
290	\li \l {painting/deform}{Vector Deformation Example}
291	\row
292	\li \inlineimage qpainterpath-example.png
293	\li \inlineimage qpainterpath-demo.png
294	\endtable
295
296	\sa QPainterPathStroker, QPainter, QRegion, {Painter Paths Example}
297	*/
298
299	/*!
300	\enum QPainterPath::ElementType
301
302	This enum describes the types of elements used to connect vertices
303	in subpaths.
304
305	Note that elements added as closed subpaths using the
306	addEllipse(), addPath(), addPolygon(), addRect(), addRegion() and
307	addText() convenience functions, is actually added to the path as
308	a collection of separate elements using the moveTo(), lineTo() and
309	cubicTo() functions.
310
311	\value MoveToElement A new subpath. See also moveTo().
312	\value LineToElement A line. See also lineTo().
313	\value CurveToElement A curve. See also cubicTo() and quadTo().
314	\value CurveToDataElement The extra data required to describe a curve in
315	a CurveToElement element.
316
317	\sa elementAt(), elementCount()
318	*/
319
320	/*!
321	\class QPainterPath::Element
322	\inmodule QtGui
323
324	\brief The QPainterPath::Element class specifies the position and
325	type of a subpath.
326
327	Once a QPainterPath object is constructed, subpaths like lines and
328	curves can be added to the path (creating
329	QPainterPath::LineToElement and QPainterPath::CurveToElement
330	components).
331
332	The lines and curves stretch from the currentPosition() to the
333	position passed as argument. The currentPosition() of the
334	QPainterPath object is always the end position of the last subpath
335	that was added (or the initial start point). The moveTo() function
336	can be used to move the currentPosition() without adding a line or
337	curve, creating a QPainterPath::MoveToElement component.
338
339	\sa QPainterPath
340	*/
341
342	/*!
343	\variable QPainterPath::Element::x
344	\brief the x coordinate of the element's position.
345
346	\sa {operator QPointF()}
347	*/
348
349	/*!
350	\variable QPainterPath::Element::y
351	\brief the y coordinate of the element's position.
352
353	\sa {operator QPointF()}
354	*/
355
356	/*!
357	\variable QPainterPath::Element::type
358	\brief the type of element
359
360	\sa isCurveTo(), isLineTo(), isMoveTo()
361	*/
362
363	/*!
364	\fn bool QPainterPath::Element::operator==(const Element &other) const
365	\since 4.2
366
367	Returns \c true if this element is equal to \a other;
368	otherwise returns \c false.
369
370	\sa operator!=()
371	*/
372
373	/*!
374	\fn bool QPainterPath::Element::operator!=(const Element &other) const
375	\since 4.2
376
377	Returns \c true if this element is not equal to \a other;
378	otherwise returns \c false.
379
380	\sa operator==()
381	*/
382
383	/*!
384	\fn bool QPainterPath::Element::isCurveTo () const
385
386	Returns \c true if the element is a curve, otherwise returns \c false.
387
388	\sa type, QPainterPath::CurveToElement
389	*/
390
391	/*!
392	\fn bool QPainterPath::Element::isLineTo () const
393
394	Returns \c true if the element is a line, otherwise returns \c false.
395
396	\sa type, QPainterPath::LineToElement
397	*/
398
399	/*!
400	\fn bool QPainterPath::Element::isMoveTo () const
401
402	Returns \c true if the element is moving the current position,
403	otherwise returns \c false.
404
405	\sa type, QPainterPath::MoveToElement
406	*/
407
408	/*!
409	\fn QPainterPath::Element::operator QPointF () const
410
411	Returns the element's position.
412
413	\sa x, y
414	*/
415
416	/*!
417	\fn void QPainterPath::addEllipse(qreal x, qreal y, qreal width, qreal height)
418	\overload
419
420	Creates an ellipse within the bounding rectangle defined by its top-left
421	corner at (\a x, \a y), \a width and \a height, and adds it to the
422	painter path as a closed subpath.
423	*/
424
425	/*!
426	\since 4.4
427
428	\fn void QPainterPath::addEllipse(const QPointF &center, qreal rx, qreal ry)
429	\overload
430
431	Creates an ellipse positioned at \a{center} with radii \a{rx} and \a{ry},
432	and adds it to the painter path as a closed subpath.
433	*/
434
435	/*!
436	\fn void QPainterPath::addText(qreal x, qreal y, const QFont &font, const QString &text)
437	\overload
438
439	Adds the given \a text to this path as a set of closed subpaths created
440	from the \a font supplied. The subpaths are positioned so that the left
441	end of the text's baseline lies at the point specified by (\a x, \a y).
442	*/
443
444	/*!
445	\fn int QPainterPath::elementCount() const
446
447	Returns the number of path elements in the painter path.
448
449	\sa ElementType, elementAt(), isEmpty()
450	*/
451
452	int QPainterPath::elementCount() const
453	{
454	return d_ptr ? d_ptr->elements.size() : 0;
455	}
456
457	/*!
458	\fn QPainterPath::Element QPainterPath::elementAt(int index) const
459
460	Returns the element at the given \a index in the painter path.
461
462	\sa ElementType, elementCount(), isEmpty()
463	*/
464
465	QPainterPath::Element QPainterPath::elementAt(int i) const
466	{
467	Q_ASSERT(d_ptr);
468	Q_ASSERT(i >= 0 && i < elementCount());
469	return d_ptr->elements.at(i);
470	}
471
472	/*!
473	\fn void QPainterPath::setElementPositionAt(int index, qreal x, qreal y)
474	\since 4.2
475
476	Sets the x and y coordinate of the element at index \a index to \a
477	x and \a y.
478	*/
479
480	void QPainterPath::setElementPositionAt(int i, qreal x, qreal y)
481	{
482	Q_ASSERT(d_ptr);
483	Q_ASSERT(i >= 0 && i < elementCount());
484	setDirty(true);
485	QPainterPath::Element &e = d_ptr->elements[i];
486	e.x = x;
487	e.y = y;
488	}
489
490
491	/*###
492	\fn QPainterPath &QPainterPath::operator +=(const QPainterPath &other)
493
494	Appends the \a other painter path to this painter path and returns a
495	reference to the result.
496	*/
497
498	/*!
499	Constructs an empty QPainterPath object.
500	*/
501	QPainterPath::QPainterPath() noexcept
502	: d_ptr(nullptr)
503	{
504	}
505
506	/*!
507	\fn QPainterPath::QPainterPath(const QPainterPath &path)
508
509	Creates a QPainterPath object that is a copy of the given \a path.
510
511	\sa operator=()
512	*/
513	QPainterPath::QPainterPath(const QPainterPath &other)
514	: d_ptr(other.d_ptr ? new QPainterPathPrivate(*other.d_ptr) : nullptr)
515	{
516	}
517
518	/*!
519	\fn QPainterPath::QPainterPath(QPainterPath &&other)
520	\since 6.10
521
522	Move-constructs a new painter path from \a other.
523
524	The moved-from object \a other is placed in the default-constructed state.
525	*/
526
527	/*!
528	Creates a QPainterPath object with the given \a startPoint as its
529	current position.
530	*/
531
532	QPainterPath::QPainterPath(const QPointF &startPoint)
533	: d_ptr(new QPainterPathPrivate(startPoint))
534	{
535	}
536
537	/*!
538	\internal
539	*/
540	void QPainterPath::ensureData_helper()
541	{
542	Q_ASSERT(d_ptr == nullptr);
543	QPainterPathPrivate *data = new QPainterPathPrivate;
544	data->elements.reserve(asize: 16);
545	QPainterPath::Element e = { .x: 0, .y: 0, .type: QPainterPath::MoveToElement };
546	data->elements << e;
547	d_ptr = data;
548	Q_ASSERT(d_ptr != nullptr);
549	}
550
551	/*!
552	\fn QPainterPath &QPainterPath::operator=(const QPainterPath &path)
553
554	Assigns the given \a path to this painter path.
555
556	\sa QPainterPath()
557	*/
558	QPainterPath &QPainterPath::operator=(const QPainterPath &other)
559	{
560	QPainterPath copy(other);
561	swap(other&: copy);
562	return *this;
563	}
564
565	/*!
566	\fn QPainterPath &QPainterPath::operator=(QPainterPath &&other)
567
568	Move-assigns \a other to this QPainterPath instance.
569
570	\since 5.2
571	*/
572
573	/*!
574	\fn void QPainterPath::swap(QPainterPath &other)
575	\since 4.8
576	\memberswap{painer path}
577	*/
578
579	/*!
580	Destroys this QPainterPath object.
581	*/
582	QPainterPath::~QPainterPath()
583	{
584	delete d_ptr;
585	}
586
587	/*!
588	Clears the path elements stored.
589
590	This allows the path to reuse previous memory allocations.
591
592	\sa reserve(), capacity()
593	\since 5.13
594	*/
595	void QPainterPath::clear()
596	{
597	if (!d_ptr)
598	return;
599
600	setDirty(true);
601	d_func()->clear();
602	d_func()->elements.append( t: {.x: 0, .y: 0, .type: MoveToElement} );
603	}
604
605	/*!
606	Reserves a given amount of elements in QPainterPath's internal memory.
607
608	Attempts to allocate memory for at least \a size elements.
609
610	\sa clear(), capacity(), QList::reserve()
611	\since 5.13
612	*/
613	void QPainterPath::reserve(int size)
614	{
615	Q_D(QPainterPath);
616	if ((!d && size > 0) || (d && d->elements.capacity() < size)) {
617	ensureData();
618	setDirty(true);
619	d_func()->elements.reserve(asize: size);
620	}
621	}
622
623	/*!
624	Returns the number of elements allocated by the QPainterPath.
625
626	\sa clear(), reserve()
627	\since 5.13
628	*/
629	int QPainterPath::capacity() const
630	{
631	Q_D(QPainterPath);
632	if (d)
633	return d->elements.capacity();
634
635	return 0;
636	}
637
638	/*!
639	Closes the current subpath by drawing a line to the beginning of
640	the subpath, automatically starting a new path. The current point
641	of the new path is (0, 0).
642
643	If the subpath does not contain any elements, this function does
644	nothing.
645
646	\sa moveTo(), {QPainterPath#Composing a QPainterPath}{Composing
647	a QPainterPath}
648	*/
649	void QPainterPath::closeSubpath()
650	{
651	#ifdef QPP_DEBUG
652	printf("QPainterPath::closeSubpath()\n");
653	#endif
654	if (isEmpty())
655	return;
656	setDirty(true);
657
658	d_func()->close();
659	}
660
661	/*!
662	\fn void QPainterPath::moveTo(qreal x, qreal y)
663
664	\overload
665
666	Moves the current position to (\a{x}, \a{y}) and starts a new
667	subpath, implicitly closing the previous path.
668	*/
669
670	/*!
671	\fn void QPainterPath::moveTo(const QPointF &point)
672
673	Moves the current point to the given \a point, implicitly starting
674	a new subpath and closing the previous one.
675
676	\sa closeSubpath(), {QPainterPath#Composing a
677	QPainterPath}{Composing a QPainterPath}
678	*/
679	void QPainterPath::moveTo(const QPointF &p)
680	{
681	#ifdef QPP_DEBUG
682	printf("QPainterPath::moveTo() (%.2f,%.2f)\n", p.x(), p.y());
683	#endif
684
685	if (!hasValidCoords(p)) {
686	#ifndef QT_NO_DEBUG
687	qWarning(msg: "QPainterPath::moveTo: Adding point with invalid coordinates, ignoring call");
688	#endif
689	return;
690	}
691
692	ensureData();
693	setDirty(true);
694
695	QPainterPathPrivate *d = d_func();
696	Q_ASSERT(!d->elements.isEmpty());
697
698	d->require_moveTo = false;
699
700	if (d->elements.constLast().type == MoveToElement) {
701	d->elements.last().x = p.x();
702	d->elements.last().y = p.y();
703	} else {
704	Element elm = { .x: p.x(), .y: p.y(), .type: MoveToElement };
705	d->elements.append(t: elm);
706	}
707	d->cStart = d->elements.size() - 1;
708	}
709
710	/*!
711	\fn void QPainterPath::lineTo(qreal x, qreal y)
712
713	\overload
714
715	Draws a line from the current position to the point (\a{x},
716	\a{y}).
717	*/
718
719	/*!
720	\fn void QPainterPath::lineTo(const QPointF &endPoint)
721
722	Adds a straight line from the current position to the given \a
723	endPoint. After the line is drawn, the current position is updated
724	to be at the end point of the line.
725
726	\sa addPolygon(), addRect(), {QPainterPath#Composing a
727	QPainterPath}{Composing a QPainterPath}
728	*/
729	void QPainterPath::lineTo(const QPointF &p)
730	{
731	#ifdef QPP_DEBUG
732	printf("QPainterPath::lineTo() (%.2f,%.2f)\n", p.x(), p.y());
733	#endif
734
735	if (!hasValidCoords(p)) {
736	#ifndef QT_NO_DEBUG
737	qWarning(msg: "QPainterPath::lineTo: Adding point with invalid coordinates, ignoring call");
738	#endif
739	return;
740	}
741
742	ensureData();
743	setDirty(true);
744
745	QPainterPathPrivate *d = d_func();
746	Q_ASSERT(!d->elements.isEmpty());
747	d->maybeMoveTo();
748	if (p == QPointF(d->elements.constLast()))
749	return;
750	Element elm = { .x: p.x(), .y: p.y(), .type: LineToElement };
751	d->elements.append(t: elm);
752
753	d->convex = d->elements.size() == 3 || (d->elements.size() == 4 && d->isClosed());
754	}
755
756	/*!
757	\fn void QPainterPath::cubicTo(qreal c1X, qreal c1Y, qreal c2X,
758	qreal c2Y, qreal endPointX, qreal endPointY);
759
760	\overload
761
762	Adds a cubic Bezier curve between the current position and the end
763	point (\a{endPointX}, \a{endPointY}) with control points specified
764	by (\a{c1X}, \a{c1Y}) and (\a{c2X}, \a{c2Y}).
765	*/
766
767	/*!
768	\fn void QPainterPath::cubicTo(const QPointF &c1, const QPointF &c2, const QPointF &endPoint)
769
770	Adds a cubic Bezier curve between the current position and the
771	given \a endPoint using the control points specified by \a c1, and
772	\a c2.
773
774	After the curve is added, the current position is updated to be at
775	the end point of the curve.
776
777	\table 100%
778	\row
779	\li \inlineimage qpainterpath-cubicto.png
780	\li
781	\snippet code/src_gui_painting_qpainterpath.cpp 1
782	\endtable
783
784	\sa quadTo(), {QPainterPath#Composing a QPainterPath}{Composing
785	a QPainterPath}
786	*/
787	void QPainterPath::cubicTo(const QPointF &c1, const QPointF &c2, const QPointF &e)
788	{
789	#ifdef QPP_DEBUG
790	printf("QPainterPath::cubicTo() (%.2f,%.2f), (%.2f,%.2f), (%.2f,%.2f)\n",
791	c1.x(), c1.y(), c2.x(), c2.y(), e.x(), e.y());
792	#endif
793
794	if (!hasValidCoords(p: c1) || !hasValidCoords(p: c2) || !hasValidCoords(p: e)) {
795	#ifndef QT_NO_DEBUG
796	qWarning(msg: "QPainterPath::cubicTo: Adding point with invalid coordinates, ignoring call");
797	#endif
798	return;
799	}
800
801	ensureData();
802	setDirty(true);
803
804	QPainterPathPrivate *d = d_func();
805	Q_ASSERT(!d->elements.isEmpty());
806
807
808	// Abort on empty curve as a stroker cannot handle this and the
809	// curve is irrelevant anyway.
810	if (d->elements.constLast() == c1 && c1 == c2 && c2 == e)
811	return;
812
813	d->maybeMoveTo();
814
815	Element ce1 = { .x: c1.x(), .y: c1.y(), .type: CurveToElement };
816	Element ce2 = { .x: c2.x(), .y: c2.y(), .type: CurveToDataElement };
817	Element ee = { .x: e.x(), .y: e.y(), .type: CurveToDataElement };
818	d->elements << ce1 << ce2 << ee;
819	}
820
821	/*!
822	\fn void QPainterPath::quadTo(qreal cx, qreal cy, qreal endPointX, qreal endPointY);
823
824	\overload
825
826	Adds a quadratic Bezier curve between the current point and the endpoint
827	(\a{endPointX}, \a{endPointY}) with the control point specified by
828	(\a{cx}, \a{cy}).
829	*/
830
831	/*!
832	\fn void QPainterPath::quadTo(const QPointF &c, const QPointF &endPoint)
833
834	Adds a quadratic Bezier curve between the current position and the
835	given \a endPoint with the control point specified by \a c.
836
837	After the curve is added, the current point is updated to be at
838	the end point of the curve.
839
840	\sa cubicTo(), {QPainterPath#Composing a QPainterPath}{Composing a
841	QPainterPath}
842	*/
843	void QPainterPath::quadTo(const QPointF &c, const QPointF &e)
844	{
845	#ifdef QPP_DEBUG
846	printf("QPainterPath::quadTo() (%.2f,%.2f), (%.2f,%.2f)\n",
847	c.x(), c.y(), e.x(), e.y());
848	#endif
849
850	if (!hasValidCoords(p: c) || !hasValidCoords(p: e)) {
851	#ifndef QT_NO_DEBUG
852	qWarning(msg: "QPainterPath::quadTo: Adding point with invalid coordinates, ignoring call");
853	#endif
854	return;
855	}
856
857	ensureData();
858	setDirty(true);
859
860	Q_D(QPainterPath);
861	Q_ASSERT(!d->elements.isEmpty());
862	const QPainterPath::Element &elm = d->elements.at(i: elementCount()-1);
863	QPointF prev(elm.x, elm.y);
864
865	// Abort on empty curve as a stroker cannot handle this and the
866	// curve is irrelevant anyway.
867	if (prev == c && c == e)
868	return;
869
870	QPointF c1((prev.x() + 2*c.x()) / 3, (prev.y() + 2*c.y()) / 3);
871	QPointF c2((e.x() + 2*c.x()) / 3, (e.y() + 2*c.y()) / 3);
872	cubicTo(c1, c2, e);
873	}
874
875	/*!
876	\fn void QPainterPath::arcTo(qreal x, qreal y, qreal width, qreal
877	height, qreal startAngle, qreal sweepLength)
878
879	\overload
880
881	Creates an arc that occupies the rectangle QRectF(\a x, \a y, \a
882	width, \a height), beginning at the specified \a startAngle and
883	extending \a sweepLength degrees counter-clockwise.
884
885	*/
886
887	/*!
888	\fn void QPainterPath::arcTo(const QRectF &rectangle, qreal startAngle, qreal sweepLength)
889
890	Creates an arc that occupies the given \a rectangle, beginning at
891	the specified \a startAngle and extending \a sweepLength degrees
892	counter-clockwise.
893
894	Angles are specified in degrees. Clockwise arcs can be specified
895	using negative angles.
896
897	Note that this function connects the starting point of the arc to
898	the current position if they are not already connected. After the
899	arc has been added, the current position is the last point in
900	arc. To draw a line back to the first point, use the
901	closeSubpath() function.
902
903	\table 100%
904	\row
905	\li \inlineimage qpainterpath-arcto.png
906	\li
907	\snippet code/src_gui_painting_qpainterpath.cpp 2
908	\endtable
909
910	\sa arcMoveTo(), addEllipse(), QPainter::drawArc(), QPainter::drawPie(),
911	{QPainterPath#Composing a QPainterPath}{Composing a
912	QPainterPath}
913	*/
914	void QPainterPath::arcTo(const QRectF &rect, qreal startAngle, qreal sweepLength)
915	{
916	#ifdef QPP_DEBUG
917	printf("QPainterPath::arcTo() (%.2f, %.2f, %.2f, %.2f, angle=%.2f, sweep=%.2f\n",
918	rect.x(), rect.y(), rect.width(), rect.height(), startAngle, sweepLength);
919	#endif
920
921	if (!hasValidCoords(r: rect) || !isValidCoord(c: startAngle) || !isValidCoord(c: sweepLength)) {
922	#ifndef QT_NO_DEBUG
923	qWarning(msg: "QPainterPath::arcTo: Adding point with invalid coordinates, ignoring call");
924	#endif
925	return;
926	}
927
928	if (rect.isNull())
929	return;
930
931	ensureData();
932	setDirty(true);
933
934	int point_count;
935	QPointF pts[15];
936	QPointF curve_start = qt_curves_for_arc(rect, startAngle, sweepLength, controlPoints: pts, point_count: &point_count);
937
938	lineTo(p: curve_start);
939	for (int i=0; i<point_count; i+=3) {
940	cubicTo(ctrlPt1x: pts[i].x(), ctrlPt1y: pts[i].y(),
941	ctrlPt2x: pts[i+1].x(), ctrlPt2y: pts[i+1].y(),
942	endPtx: pts[i+2].x(), endPty: pts[i+2].y());
943	}
944
945	}
946
947
948	/*!
949	\fn void QPainterPath::arcMoveTo(qreal x, qreal y, qreal width, qreal height, qreal angle)
950	\overload
951	\since 4.2
952
953	Creates a move to that lies on the arc that occupies the
954	QRectF(\a x, \a y, \a width, \a height) at \a angle.
955	*/
956
957
958	/*!
959	\fn void QPainterPath::arcMoveTo(const QRectF &rectangle, qreal angle)
960	\since 4.2
961
962	Creates a move to that lies on the arc that occupies the given \a
963	rectangle at \a angle.
964
965	Angles are specified in degrees. Clockwise arcs can be specified
966	using negative angles.
967
968	\sa moveTo(), arcTo()
969	*/
970
971	void QPainterPath::arcMoveTo(const QRectF &rect, qreal angle)
972	{
973	if (rect.isNull())
974	return;
975
976	QPointF pt;
977	qt_find_ellipse_coords(r: rect, angle, length: 0, startPoint: &pt, endPoint: nullptr);
978	moveTo(p: pt);
979	}
980
981
982
983	/*!
984	\fn QPointF QPainterPath::currentPosition() const
985
986	Returns the current position of the path.
987	*/
988	QPointF QPainterPath::currentPosition() const
989	{
990	return !d_ptr || d_func()->elements.isEmpty()
991	? QPointF()
992	: QPointF(d_func()->elements.constLast().x, d_func()->elements.constLast().y);
993	}
994
995
996	/*!
997	\fn void QPainterPath::addRect(qreal x, qreal y, qreal width, qreal height)
998
999	\overload
1000
1001	Adds a rectangle at position (\a{x}, \a{y}), with the given \a
1002	width and \a height, as a closed subpath.
1003	*/
1004
1005	/*!
1006	\fn void QPainterPath::addRect(const QRectF &rectangle)
1007
1008	Adds the given \a rectangle to this path as a closed subpath.
1009
1010	The \a rectangle is added as a clockwise set of lines. The painter
1011	path's current position after the \a rectangle has been added is
1012	at the top-left corner of the rectangle.
1013
1014	\table 100%
1015	\row
1016	\li \inlineimage qpainterpath-addrectangle.png
1017	\li
1018	\snippet code/src_gui_painting_qpainterpath.cpp 3
1019	\endtable
1020
1021	\sa addRegion(), lineTo(), {QPainterPath#Composing a
1022	QPainterPath}{Composing a QPainterPath}
1023	*/
1024	void QPainterPath::addRect(const QRectF &r)
1025	{
1026	if (!hasValidCoords(r)) {
1027	#ifndef QT_NO_DEBUG
1028	qWarning(msg: "QPainterPath::addRect: Adding point with invalid coordinates, ignoring call");
1029	#endif
1030	return;
1031	}
1032
1033	if (r.isNull())
1034	return;
1035
1036	ensureData();
1037	setDirty(true);
1038
1039	bool first = d_func()->elements.size() < 2;
1040
1041	moveTo(x: r.x(), y: r.y());
1042
1043	Element l1 = { .x: r.x() + r.width(), .y: r.y(), .type: LineToElement };
1044	Element l2 = { .x: r.x() + r.width(), .y: r.y() + r.height(), .type: LineToElement };
1045	Element l3 = { .x: r.x(), .y: r.y() + r.height(), .type: LineToElement };
1046	Element l4 = { .x: r.x(), .y: r.y(), .type: LineToElement };
1047
1048	d_func()->elements << l1 << l2 << l3 << l4;
1049	d_func()->require_moveTo = true;
1050	d_func()->convex = first;
1051	}
1052
1053	/*!
1054	Adds the given \a polygon to the path as an (unclosed) subpath.
1055
1056	Note that the current position after the polygon has been added,
1057	is the last point in \a polygon. To draw a line back to the first
1058	point, use the closeSubpath() function.
1059
1060	\table 100%
1061	\row
1062	\li \inlineimage qpainterpath-addpolygon.png
1063	\li
1064	\snippet code/src_gui_painting_qpainterpath.cpp 4
1065	\endtable
1066
1067	\sa lineTo(), {QPainterPath#Composing a QPainterPath}{Composing
1068	a QPainterPath}
1069	*/
1070	void QPainterPath::addPolygon(const QPolygonF &polygon)
1071	{
1072	if (polygon.isEmpty())
1073	return;
1074
1075	ensureData();
1076	setDirty(true);
1077
1078	moveTo(p: polygon.constFirst());
1079	for (int i=1; i<polygon.size(); ++i) {
1080	Element elm = { .x: polygon.at(i).x(), .y: polygon.at(i).y(), .type: LineToElement };
1081	d_func()->elements << elm;
1082	}
1083	}
1084
1085	/*!
1086	\fn void QPainterPath::addEllipse(const QRectF &boundingRectangle)
1087
1088	Creates an ellipse within the specified \a boundingRectangle
1089	and adds it to the painter path as a closed subpath.
1090
1091	The ellipse is composed of a clockwise curve, starting and
1092	finishing at zero degrees (the 3 o'clock position).
1093
1094	\table 100%
1095	\row
1096	\li \inlineimage qpainterpath-addellipse.png
1097	\li
1098	\snippet code/src_gui_painting_qpainterpath.cpp 5
1099	\endtable
1100
1101	\sa arcTo(), QPainter::drawEllipse(), {QPainterPath#Composing a
1102	QPainterPath}{Composing a QPainterPath}
1103	*/
1104	void QPainterPath::addEllipse(const QRectF &boundingRect)
1105	{
1106	if (!hasValidCoords(r: boundingRect)) {
1107	#ifndef QT_NO_DEBUG
1108	qWarning(msg: "QPainterPath::addEllipse: Adding point with invalid coordinates, ignoring call");
1109	#endif
1110	return;
1111	}
1112
1113	if (boundingRect.isNull())
1114	return;
1115
1116	ensureData();
1117	setDirty(true);
1118
1119	bool first = d_func()->elements.size() < 2;
1120
1121	QPointF pts[12];
1122	int point_count;
1123	QPointF start = qt_curves_for_arc(rect: boundingRect, startAngle: 0, sweepLength: -360, controlPoints: pts, point_count: &point_count);
1124
1125	moveTo(p: start);
1126	cubicTo(c1: pts[0], c2: pts[1], e: pts[2]); // 0 -> 270
1127	cubicTo(c1: pts[3], c2: pts[4], e: pts[5]); // 270 -> 180
1128	cubicTo(c1: pts[6], c2: pts[7], e: pts[8]); // 180 -> 90
1129	cubicTo(c1: pts[9], c2: pts[10], e: pts[11]); // 90 - >0
1130	d_func()->require_moveTo = true;
1131
1132	d_func()->convex = first;
1133	}
1134
1135	/*!
1136	\fn void QPainterPath::addText(const QPointF &point, const QFont &font, const QString &text)
1137
1138	Adds the given \a text to this path as a set of closed subpaths
1139	created from the \a font supplied. The subpaths are positioned so
1140	that the left end of the text's baseline lies at the specified \a
1141	point.
1142
1143	Some fonts may yield overlapping subpaths and will require the
1144	\c Qt::WindingFill fill rule for correct rendering.
1145
1146	\table 100%
1147	\row
1148	\li \inlineimage qpainterpath-addtext.png
1149	\li
1150	\snippet code/src_gui_painting_qpainterpath.cpp 6
1151	\endtable
1152
1153	\sa QPainter::drawText(), {QPainterPath#Composing a
1154	QPainterPath}{Composing a QPainterPath}, setFillRule()
1155	*/
1156	void QPainterPath::addText(const QPointF &point, const QFont &f, const QString &text)
1157	{
1158	if (text.isEmpty())
1159	return;
1160
1161	ensureData();
1162	setDirty(true);
1163
1164	QTextLayout layout(text, f);
1165	layout.setCacheEnabled(true);
1166
1167	QTextOption opt = layout.textOption();
1168	opt.setUseDesignMetrics(true);
1169	layout.setTextOption(opt);
1170
1171	QTextEngine *eng = layout.engine();
1172	layout.beginLayout();
1173	QTextLine line = layout.createLine();
1174	Q_UNUSED(line);
1175	layout.endLayout();
1176	const QScriptLine &sl = eng->lines[0];
1177	if (!sl.length || !eng->layoutData)
1178	return;
1179
1180	int nItems = eng->layoutData->items.size();
1181
1182	qreal x(point.x());
1183	qreal y(point.y());
1184
1185	QVarLengthArray<int> visualOrder(nItems);
1186	QVarLengthArray<uchar> levels(nItems);
1187	for (int i = 0; i < nItems; ++i)
1188	levels[i] = eng->layoutData->items.at(i).analysis.bidiLevel;
1189	QTextEngine::bidiReorder(numRuns: nItems, levels: levels.data(), visualOrder: visualOrder.data());
1190
1191	for (int i = 0; i < nItems; ++i) {
1192	int item = visualOrder[i];
1193	const QScriptItem &si = eng->layoutData->items.at(i: item);
1194
1195	if (si.analysis.flags < QScriptAnalysis::TabOrObject) {
1196	QGlyphLayout glyphs = eng->shapedGlyphs(si: &si);
1197	QFontEngine *fe = eng->fontEngine(si);
1198	Q_ASSERT(fe);
1199	fe->addOutlineToPath(x, y, glyphs, this,
1200	flags: si.analysis.bidiLevel % 2
1201	? QTextItem::RenderFlags(QTextItem::RightToLeft)
1202	: QTextItem::RenderFlags{});
1203
1204	const qreal lw = fe->lineThickness().toReal();
1205	if (f.d->underline) {
1206	qreal pos = fe->underlinePosition().toReal();
1207	addRect(x, y: y + pos, w: si.width.toReal(), h: lw);
1208	}
1209	if (f.d->overline) {
1210	qreal pos = fe->ascent().toReal() + 1;
1211	addRect(x, y: y - pos, w: si.width.toReal(), h: lw);
1212	}
1213	if (f.d->strikeOut) {
1214	qreal pos = fe->ascent().toReal() / 3;
1215	addRect(x, y: y - pos, w: si.width.toReal(), h: lw);
1216	}
1217	}
1218	x += si.width.toReal();
1219	}
1220	}
1221
1222	/*!
1223	\fn void QPainterPath::addPath(const QPainterPath &path)
1224
1225	Adds the given \a path to \e this path as a closed subpath.
1226
1227	\sa connectPath(), {QPainterPath#Composing a
1228	QPainterPath}{Composing a QPainterPath}
1229	*/
1230	void QPainterPath::addPath(const QPainterPath &other)
1231	{
1232	if (other.isEmpty())
1233	return;
1234
1235	ensureData();
1236	setDirty(true);
1237
1238	QPainterPathPrivate *d = d_func();
1239	// Remove last moveto so we don't get multiple moveto's
1240	if (d->elements.constLast().type == MoveToElement)
1241	d->elements.remove(i: d->elements.size()-1);
1242
1243	// Locate where our own current subpath will start after the other path is added.
1244	int cStart = d->elements.size() + other.d_func()->cStart;
1245	d->elements += other.d_func()->elements;
1246	d->cStart = cStart;
1247
1248	d->require_moveTo = other.d_func()->isClosed();
1249	}
1250
1251
1252	/*!
1253	\fn void QPainterPath::connectPath(const QPainterPath &path)
1254
1255	Connects the given \a path to \e this path by adding a line from the
1256	last element of this path to the first element of the given path.
1257
1258	\sa addPath(), {QPainterPath#Composing a QPainterPath}{Composing
1259	a QPainterPath}
1260	*/
1261	void QPainterPath::connectPath(const QPainterPath &other)
1262	{
1263	if (other.isEmpty())
1264	return;
1265
1266	ensureData();
1267	setDirty(true);
1268
1269	QPainterPathPrivate *d = d_func();
1270	// Remove last moveto so we don't get multiple moveto's
1271	if (d->elements.constLast().type == MoveToElement)
1272	d->elements.remove(i: d->elements.size()-1);
1273
1274	// Locate where our own current subpath will start after the other path is added.
1275	int cStart = d->elements.size() + other.d_func()->cStart;
1276	int first = d->elements.size();
1277	d->elements += other.d_func()->elements;
1278
1279	if (first != 0)
1280	d->elements[first].type = LineToElement;
1281
1282	// avoid duplicate points
1283	if (first > 0 && QPointF(d->elements.at(i: first)) == QPointF(d->elements.at(i: first - 1))) {
1284	d->elements.remove(i: first--);
1285	--cStart;
1286	}
1287
1288	if (cStart != first)
1289	d->cStart = cStart;
1290	}
1291
1292	/*!
1293	Adds the given \a region to the path by adding each rectangle in
1294	the region as a separate closed subpath.
1295
1296	\sa addRect(), {QPainterPath#Composing a QPainterPath}{Composing
1297	a QPainterPath}
1298	*/
1299	void QPainterPath::addRegion(const QRegion &region)
1300	{
1301	ensureData();
1302	setDirty(true);
1303
1304	for (const QRect &rect : region)
1305	addRect(r: rect);
1306	}
1307
1308
1309	/*!
1310	Returns the painter path's currently set fill rule.
1311
1312	\sa setFillRule()
1313	*/
1314	Qt::FillRule QPainterPath::fillRule() const
1315	{
1316	return d_func() && d_func()->hasWindingFill ? Qt::WindingFill : Qt::OddEvenFill;
1317	}
1318
1319	/*!
1320	\fn void QPainterPath::setFillRule(Qt::FillRule fillRule)
1321
1322	Sets the fill rule of the painter path to the given \a
1323	fillRule. Qt provides two methods for filling paths:
1324
1325	\table
1326	\header
1327	\li Qt::OddEvenFill (default)
1328	\li Qt::WindingFill
1329	\row
1330	\li \inlineimage qt-fillrule-oddeven.png
1331	\li \inlineimage qt-fillrule-winding.png
1332	\endtable
1333
1334	\sa fillRule()
1335	*/
1336	void QPainterPath::setFillRule(Qt::FillRule fillRule)
1337	{
1338	ensureData();
1339	const bool isWindingRequested = (fillRule == Qt::WindingFill);
1340	if (d_func()->hasWindingFill == isWindingRequested)
1341	return;
1342	setDirty(true);
1343
1344	d_func()->hasWindingFill = isWindingRequested;
1345	}
1346
1347	#define QT_BEZIER_A(bezier, coord) 3 * (-bezier.coord##1 \
1348	+ 3*bezier.coord##2 \
1349	- 3*bezier.coord##3 \
1350	+bezier.coord##4)
1351
1352	#define QT_BEZIER_B(bezier, coord) 6 * (bezier.coord##1 \
1353	- 2*bezier.coord##2 \
1354	+ bezier.coord##3)
1355
1356	#define QT_BEZIER_C(bezier, coord) 3 * (- bezier.coord##1 \
1357	+ bezier.coord##2)
1358
1359	#define QT_BEZIER_CHECK_T(bezier, t) \
1360	if (t >= 0 && t <= 1) { \
1361	QPointF p(b.pointAt(t)); \
1362	if (p.x() < minx) minx = p.x(); \
1363	else if (p.x() > maxx) maxx = p.x(); \
1364	if (p.y() < miny) miny = p.y(); \
1365	else if (p.y() > maxy) maxy = p.y(); \
1366	}
1367
1368
1369	static QRectF qt_painterpath_bezier_extrema(const QBezier &b)
1370	{
1371	qreal minx, miny, maxx, maxy;
1372
1373	// initialize with end points
1374	if (b.x1 < b.x4) {
1375	minx = b.x1;
1376	maxx = b.x4;
1377	} else {
1378	minx = b.x4;
1379	maxx = b.x1;
1380	}
1381	if (b.y1 < b.y4) {
1382	miny = b.y1;
1383	maxy = b.y4;
1384	} else {
1385	miny = b.y4;
1386	maxy = b.y1;
1387	}
1388
1389	// Update for the X extrema
1390	{
1391	qreal ax = QT_BEZIER_A(b, x);
1392	qreal bx = QT_BEZIER_B(b, x);
1393	qreal cx = QT_BEZIER_C(b, x);
1394	// specialcase quadratic curves to avoid div by zero
1395	if (qFuzzyIsNull(d: ax)) {
1396
1397	// linear curves are covered by initialization.
1398	if (!qFuzzyIsNull(d: bx)) {
1399	qreal t = -cx / bx;
1400	QT_BEZIER_CHECK_T(b, t);
1401	}
1402
1403	} else {
1404	const qreal tx = bx * bx - 4 * ax * cx;
1405
1406	if (tx >= 0) {
1407	qreal temp = qSqrt(v: tx);
1408	qreal rcp = 1 / (2 * ax);
1409	qreal t1 = (-bx + temp) * rcp;
1410	QT_BEZIER_CHECK_T(b, t1);
1411
1412	qreal t2 = (-bx - temp) * rcp;
1413	QT_BEZIER_CHECK_T(b, t2);
1414	}
1415	}
1416	}
1417
1418	// Update for the Y extrema
1419	{
1420	qreal ay = QT_BEZIER_A(b, y);
1421	qreal by = QT_BEZIER_B(b, y);
1422	qreal cy = QT_BEZIER_C(b, y);
1423
1424	// specialcase quadratic curves to avoid div by zero
1425	if (qFuzzyIsNull(d: ay)) {
1426
1427	// linear curves are covered by initialization.
1428	if (!qFuzzyIsNull(d: by)) {
1429	qreal t = -cy / by;
1430	QT_BEZIER_CHECK_T(b, t);
1431	}
1432
1433	} else {
1434	const qreal ty = by * by - 4 * ay * cy;
1435
1436	if (ty > 0) {
1437	qreal temp = qSqrt(v: ty);
1438	qreal rcp = 1 / (2 * ay);
1439	qreal t1 = (-by + temp) * rcp;
1440	QT_BEZIER_CHECK_T(b, t1);
1441
1442	qreal t2 = (-by - temp) * rcp;
1443	QT_BEZIER_CHECK_T(b, t2);
1444	}
1445	}
1446	}
1447	return QRectF(minx, miny, maxx - minx, maxy - miny);
1448	}
1449
1450	/*!
1451	Returns the bounding rectangle of this painter path as a rectangle with
1452	floating point precision.
1453
1454	\sa controlPointRect()
1455	*/
1456	QRectF QPainterPath::boundingRect() const
1457	{
1458	if (!d_ptr)
1459	return QRectF();
1460	QPainterPathPrivate *d = d_func();
1461
1462	if (d->dirtyBounds)
1463	computeBoundingRect();
1464	return d->bounds;
1465	}
1466
1467	/*!
1468	Returns the rectangle containing all the points and control points
1469	in this path.
1470
1471	This function is significantly faster to compute than the exact
1472	boundingRect(), and the returned rectangle is always a superset of
1473	the rectangle returned by boundingRect().
1474
1475	\sa boundingRect()
1476	*/
1477	QRectF QPainterPath::controlPointRect() const
1478	{
1479	if (!d_ptr)
1480	return QRectF();
1481	QPainterPathPrivate *d = d_func();
1482
1483	if (d->dirtyControlBounds)
1484	computeControlPointRect();
1485	return d->controlBounds;
1486	}
1487
1488
1489	/*!
1490	\fn bool QPainterPath::isEmpty() const
1491
1492	Returns \c true if either there are no elements in this path, or if the only
1493	element is a MoveToElement; otherwise returns \c false.
1494
1495	\sa elementCount()
1496	*/
1497
1498	bool QPainterPath::isEmpty() const
1499	{
1500	return !d_ptr || (d_ptr->elements.size() == 1 && d_ptr->elements.constFirst().type == MoveToElement);
1501	}
1502
1503	/*!
1504	Creates and returns a reversed copy of the path.
1505
1506	It is the order of the elements that is reversed: If a
1507	QPainterPath is composed by calling the moveTo(), lineTo() and
1508	cubicTo() functions in the specified order, the reversed copy is
1509	composed by calling cubicTo(), lineTo() and moveTo().
1510	*/
1511	QPainterPath QPainterPath::toReversed() const
1512	{
1513	Q_D(const QPainterPath);
1514	QPainterPath rev;
1515
1516	if (isEmpty()) {
1517	rev = *this;
1518	return rev;
1519	}
1520
1521	rev.moveTo(x: d->elements.at(i: d->elements.size()-1).x, y: d->elements.at(i: d->elements.size()-1).y);
1522
1523	for (int i=d->elements.size()-1; i>=1; --i) {
1524	const QPainterPath::Element &elm = d->elements.at(i);
1525	const QPainterPath::Element &prev = d->elements.at(i: i-1);
1526	switch (elm.type) {
1527	case LineToElement:
1528	rev.lineTo(x: prev.x, y: prev.y);
1529	break;
1530	case MoveToElement:
1531	rev.moveTo(x: prev.x, y: prev.y);
1532	break;
1533	case CurveToDataElement:
1534	{
1535	Q_ASSERT(i>=3);
1536	const QPainterPath::Element &cp1 = d->elements.at(i: i-2);
1537	const QPainterPath::Element &sp = d->elements.at(i: i-3);
1538	Q_ASSERT(prev.type == CurveToDataElement);
1539	Q_ASSERT(cp1.type == CurveToElement);
1540	rev.cubicTo(ctrlPt1x: prev.x, ctrlPt1y: prev.y, ctrlPt2x: cp1.x, ctrlPt2y: cp1.y, endPtx: sp.x, endPty: sp.y);
1541	i -= 2;
1542	break;
1543	}
1544	default:
1545	Q_ASSERT(!"qt_reversed_path");
1546	break;
1547	}
1548	}
1549	//qt_debug_path(rev);
1550	return rev;
1551	}
1552
1553	/*!
1554	Converts the path into a list of polygons using the QTransform
1555	\a matrix, and returns the list.
1556
1557	This function creates one polygon for each subpath regardless of
1558	intersecting subpaths (i.e. overlapping bounding rectangles). To
1559	make sure that such overlapping subpaths are filled correctly, use
1560	the toFillPolygons() function instead.
1561
1562	\sa toFillPolygons(), toFillPolygon(), {QPainterPath#QPainterPath
1563	Conversion}{QPainterPath Conversion}
1564	*/
1565	QList<QPolygonF> QPainterPath::toSubpathPolygons(const QTransform &matrix) const
1566	{
1567
1568	Q_D(const QPainterPath);
1569	QList<QPolygonF> flatCurves;
1570	if (isEmpty())
1571	return flatCurves;
1572
1573	QPolygonF current;
1574	for (int i=0; i<elementCount(); ++i) {
1575	const QPainterPath::Element &e = d->elements.at(i);
1576	switch (e.type) {
1577	case QPainterPath::MoveToElement:
1578	if (current.size() > 1)
1579	flatCurves += current;
1580	current.clear();
1581	current.reserve(asize: 16);
1582	current += QPointF(e.x, e.y) * matrix;
1583	break;
1584	case QPainterPath::LineToElement:
1585	current += QPointF(e.x, e.y) * matrix;
1586	break;
1587	case QPainterPath::CurveToElement: {
1588	Q_ASSERT(d->elements.at(i+1).type == QPainterPath::CurveToDataElement);
1589	Q_ASSERT(d->elements.at(i+2).type == QPainterPath::CurveToDataElement);
1590	QBezier bezier = QBezier::fromPoints(p1: QPointF(d->elements.at(i: i-1).x, d->elements.at(i: i-1).y) * matrix,
1591	p2: QPointF(e.x, e.y) * matrix,
1592	p3: QPointF(d->elements.at(i: i+1).x, d->elements.at(i: i+1).y) * matrix,
1593	p4: QPointF(d->elements.at(i: i+2).x, d->elements.at(i: i+2).y) * matrix);
1594	bezier.addToPolygon(p: &current);
1595	i+=2;
1596	break;
1597	}
1598	case QPainterPath::CurveToDataElement:
1599	Q_ASSERT(!"QPainterPath::toSubpathPolygons(), bad element type");
1600	break;
1601	}
1602	}
1603
1604	if (current.size()>1)
1605	flatCurves += current;
1606
1607	return flatCurves;
1608	}
1609
1610	/*!
1611	Converts the path into a list of polygons using the
1612	QTransform \a matrix, and returns the list.
1613
1614	The function differs from the toFillPolygon() function in that it
1615	creates several polygons. It is provided because it is usually
1616	faster to draw several small polygons than to draw one large
1617	polygon, even though the total number of points drawn is the same.
1618
1619	The toFillPolygons() function differs from the toSubpathPolygons()
1620	function in that it create only polygon for subpaths that have
1621	overlapping bounding rectangles.
1622
1623	Like the toFillPolygon() function, this function uses a rewinding
1624	technique to make sure that overlapping subpaths can be filled
1625	using the correct fill rule. Note that rewinding inserts addition
1626	lines in the polygons so the outline of the fill polygon does not
1627	match the outline of the path.
1628
1629	\sa toSubpathPolygons(), toFillPolygon(),
1630	{QPainterPath#QPainterPath Conversion}{QPainterPath Conversion}
1631	*/
1632	QList<QPolygonF> QPainterPath::toFillPolygons(const QTransform &matrix) const
1633	{
1634
1635	QList<QPolygonF> polys;
1636
1637	QList<QPolygonF> subpaths = toSubpathPolygons(matrix);
1638	int count = subpaths.size();
1639
1640	if (count == 0)
1641	return polys;
1642
1643	QList<QRectF> bounds;
1644	bounds.reserve(asize: count);
1645	for (int i=0; i<count; ++i)
1646	bounds += subpaths.at(i).boundingRect();
1647
1648	#ifdef QPP_FILLPOLYGONS_DEBUG
1649	printf("QPainterPath::toFillPolygons, subpathCount=%d\n", count);
1650	for (int i=0; i<bounds.size(); ++i)
1651	qDebug() << " bounds" << i << bounds.at(i);
1652	#endif
1653
1654	QList< QList<int> > isects;
1655	isects.resize(size: count);
1656
1657	// find all intersections
1658	for (int j=0; j<count; ++j) {
1659	if (subpaths.at(i: j).size() <= 2)
1660	continue;
1661	QRectF cbounds = bounds.at(i: j);
1662	for (int i=0; i<count; ++i) {
1663	if (cbounds.intersects(r: bounds.at(i))) {
1664	isects[j] << i;
1665	}
1666	}
1667	}
1668
1669	#ifdef QPP_FILLPOLYGONS_DEBUG
1670	printf("Intersections before flattening:\n");
1671	for (int i = 0; i < count; ++i) {
1672	printf("%d: ", i);
1673	for (int j = 0; j < isects[i].size(); ++j) {
1674	printf("%d ", isects[i][j]);
1675	}
1676	printf("\n");
1677	}
1678	#endif
1679
1680	// flatten the sets of intersections
1681	for (int i=0; i<count; ++i) {
1682	const QList<int> &current_isects = isects.at(i);
1683	for (int j=0; j<current_isects.size(); ++j) {
1684	int isect_j = current_isects.at(i: j);
1685	if (isect_j == i)
1686	continue;
1687	const QList<int> &isects_j = isects.at(i: isect_j);
1688	for (int k = 0, size = isects_j.size(); k < size; ++k) {
1689	int isect_k = isects_j.at(i: k);
1690	if (isect_k != i && !isects.at(i).contains(t: isect_k)) {
1691	isects[i] += isect_k;
1692	}
1693	}
1694	isects[isect_j].clear();
1695	}
1696	}
1697
1698	#ifdef QPP_FILLPOLYGONS_DEBUG
1699	printf("Intersections after flattening:\n");
1700	for (int i = 0; i < count; ++i) {
1701	printf("%d: ", i);
1702	for (int j = 0; j < isects[i].size(); ++j) {
1703	printf("%d ", isects[i][j]);
1704	}
1705	printf("\n");
1706	}
1707	#endif
1708
1709	// Join the intersected subpaths as rewinded polygons
1710	for (int i=0; i<count; ++i) {
1711	const QList<int> &subpath_list = isects.at(i);
1712	if (!subpath_list.isEmpty()) {
1713	QPolygonF buildUp;
1714	for (int j=0; j<subpath_list.size(); ++j) {
1715	const QPolygonF &subpath = subpaths.at(i: subpath_list.at(i: j));
1716	buildUp += subpath;
1717	if (!subpath.isClosed())
1718	buildUp += subpath.first();
1719	if (!buildUp.isClosed())
1720	buildUp += buildUp.constFirst();
1721	}
1722	polys += buildUp;
1723	}
1724	}
1725
1726	return polys;
1727	}
1728
1729	//same as qt_polygon_isect_line in qpolygon.cpp
1730	static void qt_painterpath_isect_line(const QPointF &p1,
1731	const QPointF &p2,
1732	const QPointF &pos,
1733	int *winding)
1734	{
1735	qreal x1 = p1.x();
1736	qreal y1 = p1.y();
1737	qreal x2 = p2.x();
1738	qreal y2 = p2.y();
1739	qreal y = pos.y();
1740
1741	int dir = 1;
1742
1743	if (qFuzzyCompare(p1: y1, p2: y2)) {
1744	// ignore horizontal lines according to scan conversion rule
1745	return;
1746	} else if (y2 < y1) {
1747	qreal x_tmp = x2; x2 = x1; x1 = x_tmp;
1748	qreal y_tmp = y2; y2 = y1; y1 = y_tmp;
1749	dir = -1;
1750	}
1751
1752	if (y >= y1 && y < y2) {
1753	qreal x = x1 + ((x2 - x1) / (y2 - y1)) * (y - y1);
1754
1755	// count up the winding number if we're
1756	if (x<=pos.x()) {
1757	(*winding) += dir;
1758	}
1759	}
1760	}
1761
1762	static void qt_painterpath_isect_curve(const QBezier &bezier, const QPointF &pt,
1763	int *winding, int depth = 0)
1764	{
1765	qreal y = pt.y();
1766	qreal x = pt.x();
1767	QRectF bounds = bezier.bounds();
1768
1769	// potential intersection, divide and try again...
1770	// Please note that a sideeffect of the bottom exclusion is that
1771	// horizontal lines are dropped, but this is correct according to
1772	// scan conversion rules.
1773	if (y >= bounds.y() && y < bounds.y() + bounds.height()) {
1774
1775	// hit lower limit... This is a rough threshold, but its a
1776	// tradeoff between speed and precision.
1777	const qreal lower_bound = qreal(.001);
1778	if (depth == 32 || (bounds.width() < lower_bound && bounds.height() < lower_bound)) {
1779	// We make the assumption here that the curve starts to
1780	// approximate a line after while (i.e. that it doesn't
1781	// change direction drastically during its slope)
1782	if (bezier.pt1().x() <= x) {
1783	(*winding) += (bezier.pt4().y() > bezier.pt1().y() ? 1 : -1);
1784	}
1785	return;
1786	}
1787
1788	// split curve and try again...
1789	const auto halves = bezier.split();
1790	qt_painterpath_isect_curve(bezier: halves.first, pt, winding, depth: depth + 1);
1791	qt_painterpath_isect_curve(bezier: halves.second, pt, winding, depth: depth + 1);
1792	}
1793	}
1794
1795	/*!
1796	\fn bool QPainterPath::contains(const QPointF &point) const
1797
1798	Returns \c true if the given \a point is inside the path, otherwise
1799	returns \c false.
1800
1801	\sa intersects()
1802	*/
1803	bool QPainterPath::contains(const QPointF &pt) const
1804	{
1805	if (isEmpty() || !controlPointRect().contains(p: pt))
1806	return false;
1807
1808	QPainterPathPrivate *d = d_func();
1809
1810	int winding_number = 0;
1811
1812	QPointF last_pt;
1813	QPointF last_start;
1814	for (int i=0; i<d->elements.size(); ++i) {
1815	const Element &e = d->elements.at(i);
1816
1817	switch (e.type) {
1818
1819	case MoveToElement:
1820	if (i > 0) // implicitly close all paths.
1821	qt_painterpath_isect_line(p1: last_pt, p2: last_start, pos: pt, winding: &winding_number);
1822	last_start = last_pt = e;
1823	break;
1824
1825	case LineToElement:
1826	qt_painterpath_isect_line(p1: last_pt, p2: e, pos: pt, winding: &winding_number);
1827	last_pt = e;
1828	break;
1829
1830	case CurveToElement:
1831	{
1832	const QPainterPath::Element &cp2 = d->elements.at(i: ++i);
1833	const QPainterPath::Element &ep = d->elements.at(i: ++i);
1834	qt_painterpath_isect_curve(bezier: QBezier::fromPoints(p1: last_pt, p2: e, p3: cp2, p4: ep),
1835	pt, winding: &winding_number);
1836	last_pt = ep;
1837
1838	}
1839	break;
1840
1841	default:
1842	break;
1843	}
1844	}
1845
1846	// implicitly close last subpath
1847	if (last_pt != last_start)
1848	qt_painterpath_isect_line(p1: last_pt, p2: last_start, pos: pt, winding: &winding_number);
1849
1850	return (d->hasWindingFill
1851	? (winding_number != 0)
1852	: ((winding_number % 2) != 0));
1853	}
1854
1855	enum PainterDirections { Left, Right, Top, Bottom };
1856
1857	static bool qt_painterpath_isect_line_rect(qreal x1, qreal y1, qreal x2, qreal y2,
1858	const QRectF &rect)
1859	{
1860	qreal left = rect.left();
1861	qreal right = rect.right();
1862	qreal top = rect.top();
1863	qreal bottom = rect.bottom();
1864
1865	// clip the lines, after cohen-sutherland, see e.g. http://www.nondot.org/~sabre/graphpro/line6.html
1866	int p1 = ((x1 < left) << Left)
1867	| ((x1 > right) << Right)
1868	| ((y1 < top) << Top)
1869	| ((y1 > bottom) << Bottom);
1870	int p2 = ((x2 < left) << Left)
1871	| ((x2 > right) << Right)
1872	| ((y2 < top) << Top)
1873	| ((y2 > bottom) << Bottom);
1874
1875	if (p1 & p2)
1876	// completely inside
1877	return false;
1878
1879	if (p1 | p2) {
1880	qreal dx = x2 - x1;
1881	qreal dy = y2 - y1;
1882
1883	// clip x coordinates
1884	if (x1 < left) {
1885	y1 += dy/dx * (left - x1);
1886	x1 = left;
1887	} else if (x1 > right) {
1888	y1 -= dy/dx * (x1 - right);
1889	x1 = right;
1890	}
1891	if (x2 < left) {
1892	y2 += dy/dx * (left - x2);
1893	x2 = left;
1894	} else if (x2 > right) {
1895	y2 -= dy/dx * (x2 - right);
1896	x2 = right;
1897	}
1898
1899	p1 = ((y1 < top) << Top)
1900	| ((y1 > bottom) << Bottom);
1901	p2 = ((y2 < top) << Top)
1902	| ((y2 > bottom) << Bottom);
1903
1904	if (p1 & p2)
1905	return false;
1906
1907	// clip y coordinates
1908	if (y1 < top) {
1909	x1 += dx/dy * (top - y1);
1910	y1 = top;
1911	} else if (y1 > bottom) {
1912	x1 -= dx/dy * (y1 - bottom);
1913	y1 = bottom;
1914	}
1915	if (y2 < top) {
1916	x2 += dx/dy * (top - y2);
1917	y2 = top;
1918	} else if (y2 > bottom) {
1919	x2 -= dx/dy * (y2 - bottom);
1920	y2 = bottom;
1921	}
1922
1923	p1 = ((x1 < left) << Left)
1924	| ((x1 > right) << Right);
1925	p2 = ((x2 < left) << Left)
1926	| ((x2 > right) << Right);
1927
1928	if (p1 & p2)
1929	return false;
1930
1931	return true;
1932	}
1933	return false;
1934	}
1935
1936	static bool qt_isect_curve_horizontal(const QBezier &bezier, qreal y, qreal x1, qreal x2, int depth = 0)
1937	{
1938	QRectF bounds = bezier.bounds();
1939
1940	if (y >= bounds.top() && y < bounds.bottom()
1941	&& bounds.right() >= x1 && bounds.left() < x2) {
1942	const qreal lower_bound = qreal(.01);
1943	if (depth == 32 || (bounds.width() < lower_bound && bounds.height() < lower_bound))
1944	return true;
1945
1946	const auto halves = bezier.split();
1947	if (qt_isect_curve_horizontal(bezier: halves.first, y, x1, x2, depth: depth + 1)
1948	|| qt_isect_curve_horizontal(bezier: halves.second, y, x1, x2, depth: depth + 1))
1949	return true;
1950	}
1951	return false;
1952	}
1953
1954	static bool qt_isect_curve_vertical(const QBezier &bezier, qreal x, qreal y1, qreal y2, int depth = 0)
1955	{
1956	QRectF bounds = bezier.bounds();
1957
1958	if (x >= bounds.left() && x < bounds.right()
1959	&& bounds.bottom() >= y1 && bounds.top() < y2) {
1960	const qreal lower_bound = qreal(.01);
1961	if (depth == 32 || (bounds.width() < lower_bound && bounds.height() < lower_bound))
1962	return true;
1963
1964	const auto halves = bezier.split();
1965	if (qt_isect_curve_vertical(bezier: halves.first, x, y1, y2, depth: depth + 1)
1966	|| qt_isect_curve_vertical(bezier: halves.second, x, y1, y2, depth: depth + 1))
1967	return true;
1968	}
1969	return false;
1970	}
1971
1972	static bool pointOnEdge(const QRectF &rect, const QPointF &point)
1973	{
1974	if ((point.x() == rect.left() || point.x() == rect.right()) &&
1975	(point.y() >= rect.top() && point.y() <= rect.bottom()))
1976	return true;
1977	if ((point.y() == rect.top() || point.y() == rect.bottom()) &&
1978	(point.x() >= rect.left() && point.x() <= rect.right()))
1979	return true;
1980	return false;
1981	}
1982
1983	/*
1984	Returns \c true if any lines or curves cross the four edges in of rect
1985	*/
1986	static bool qt_painterpath_check_crossing(const QPainterPath *path, const QRectF &rect)
1987	{
1988	QPointF last_pt;
1989	QPointF last_start;
1990	enum { OnRect, InsideRect, OutsideRect} edgeStatus = OnRect;
1991	for (int i=0; i<path->elementCount(); ++i) {
1992	const QPainterPath::Element &e = path->elementAt(i);
1993
1994	switch (e.type) {
1995
1996	case QPainterPath::MoveToElement:
1997	if (i > 0
1998	&& qFuzzyCompare(p1: last_pt.x(), p2: last_start.x())
1999	&& qFuzzyCompare(p1: last_pt.y(), p2: last_start.y())
2000	&& qt_painterpath_isect_line_rect(x1: last_pt.x(), y1: last_pt.y(),
2001	x2: last_start.x(), y2: last_start.y(), rect))
2002	return true;
2003	last_start = last_pt = e;
2004	break;
2005
2006	case QPainterPath::LineToElement:
2007	if (qt_painterpath_isect_line_rect(x1: last_pt.x(), y1: last_pt.y(), x2: e.x, y2: e.y, rect))
2008	return true;
2009	last_pt = e;
2010	break;
2011
2012	case QPainterPath::CurveToElement:
2013	{
2014	QPointF cp2 = path->elementAt(i: ++i);
2015	QPointF ep = path->elementAt(i: ++i);
2016	QBezier bezier = QBezier::fromPoints(p1: last_pt, p2: e, p3: cp2, p4: ep);
2017	if (qt_isect_curve_horizontal(bezier, y: rect.top(), x1: rect.left(), x2: rect.right())
2018	|| qt_isect_curve_horizontal(bezier, y: rect.bottom(), x1: rect.left(), x2: rect.right())
2019	|| qt_isect_curve_vertical(bezier, x: rect.left(), y1: rect.top(), y2: rect.bottom())
2020	|| qt_isect_curve_vertical(bezier, x: rect.right(), y1: rect.top(), y2: rect.bottom()))
2021	return true;
2022	last_pt = ep;
2023	}
2024	break;
2025
2026	default:
2027	break;
2028	}
2029	// Handle crossing the edges of the rect at the end-points of individual sub-paths.
2030	// A point on on the edge itself is considered neither inside nor outside for this purpose.
2031	if (!pointOnEdge(rect, point: last_pt)) {
2032	bool contained = rect.contains(p: last_pt);
2033	switch (edgeStatus) {
2034	case OutsideRect:
2035	if (contained)
2036	return true;
2037	break;
2038	case InsideRect:
2039	if (!contained)
2040	return true;
2041	break;
2042	case OnRect:
2043	edgeStatus = contained ? InsideRect : OutsideRect;
2044	break;
2045	}
2046	} else {
2047	if (last_pt == last_start)
2048	edgeStatus = OnRect;
2049	}
2050	}
2051
2052	// implicitly close last subpath
2053	if (last_pt != last_start
2054	&& qt_painterpath_isect_line_rect(x1: last_pt.x(), y1: last_pt.y(),
2055	x2: last_start.x(), y2: last_start.y(), rect))
2056	return true;
2057
2058	return false;
2059	}
2060
2061	/*!
2062	\fn bool QPainterPath::intersects(const QRectF &rectangle) const
2063
2064	Returns \c true if any point in the given \a rectangle intersects the
2065	path; otherwise returns \c false.
2066
2067	There is an intersection if any of the lines making up the
2068	rectangle crosses a part of the path or if any part of the
2069	rectangle overlaps with any area enclosed by the path. This
2070	function respects the current fillRule to determine what is
2071	considered inside the path.
2072
2073	\sa contains()
2074	*/
2075	bool QPainterPath::intersects(const QRectF &rect) const
2076	{
2077	if (elementCount() == 1 && rect.contains(p: elementAt(i: 0)))
2078	return true;
2079
2080	if (isEmpty())
2081	return false;
2082
2083	QRectF cp = controlPointRect();
2084	QRectF rn = rect.normalized();
2085
2086	// QRectF::intersects returns false if one of the rects is a null rect
2087	// which would happen for a painter path consisting of a vertical or
2088	// horizontal line
2089	if (qMax(a: rn.left(), b: cp.left()) > qMin(a: rn.right(), b: cp.right())
2090	|| qMax(a: rn.top(), b: cp.top()) > qMin(a: rn.bottom(), b: cp.bottom()))
2091	return false;
2092
2093	// If any path element cross the rect its bound to be an intersection
2094	if (qt_painterpath_check_crossing(path: this, rect))
2095	return true;
2096
2097	if (contains(pt: rect.center()))
2098	return true;
2099
2100	Q_D(QPainterPath);
2101
2102	// Check if the rectangle surrounds any subpath...
2103	for (int i=0; i<d->elements.size(); ++i) {
2104	const Element &e = d->elements.at(i);
2105	if (e.type == QPainterPath::MoveToElement && rect.contains(p: e))
2106	return true;
2107	}
2108
2109	return false;
2110	}
2111
2112	/*!
2113	Translates all elements in the path by (\a{dx}, \a{dy}).
2114
2115	\since 4.6
2116	\sa translated()
2117	*/
2118	void QPainterPath::translate(qreal dx, qreal dy)
2119	{
2120	if (!d_ptr || (dx == 0 && dy == 0))
2121	return;
2122
2123	int elementsLeft = d_ptr->elements.size();
2124	if (elementsLeft <= 0)
2125	return;
2126
2127	setDirty(true);
2128	QPainterPath::Element *element = d_func()->elements.data();
2129	Q_ASSERT(element);
2130	while (elementsLeft--) {
2131	element->x += dx;
2132	element->y += dy;
2133	++element;
2134	}
2135	}
2136
2137	/*!
2138	\fn void QPainterPath::translate(const QPointF &offset)
2139	\overload
2140	\since 4.6
2141
2142	Translates all elements in the path by the given \a offset.
2143
2144	\sa translated()
2145	*/
2146
2147	/*!
2148	Returns a copy of the path that is translated by (\a{dx}, \a{dy}).
2149
2150	\since 4.6
2151	\sa translate()
2152	*/
2153	QPainterPath QPainterPath::translated(qreal dx, qreal dy) const
2154	{
2155	QPainterPath copy(*this);
2156	copy.translate(dx, dy);
2157	return copy;
2158	}
2159
2160	/*!
2161	\fn QPainterPath QPainterPath::translated(const QPointF &offset) const;
2162	\overload
2163	\since 4.6
2164
2165	Returns a copy of the path that is translated by the given \a offset.
2166
2167	\sa translate()
2168	*/
2169
2170	/*!
2171	\fn bool QPainterPath::contains(const QRectF &rectangle) const
2172
2173	Returns \c true if the given \a rectangle is inside the path,
2174	otherwise returns \c false.
2175	*/
2176	bool QPainterPath::contains(const QRectF &rect) const
2177	{
2178	Q_D(QPainterPath);
2179
2180	// the path is empty or the control point rect doesn't completely
2181	// cover the rectangle we abort stratight away.
2182	if (isEmpty() || !controlPointRect().contains(r: rect))
2183	return false;
2184
2185	// if there are intersections, chances are that the rect is not
2186	// contained, except if we have winding rule, in which case it
2187	// still might.
2188	if (qt_painterpath_check_crossing(path: this, rect)) {
2189	if (fillRule() == Qt::OddEvenFill) {
2190	return false;
2191	} else {
2192	// Do some wague sampling in the winding case. This is not
2193	// precise but it should mostly be good enough.
2194	if (!contains(pt: rect.topLeft()) ||
2195	!contains(pt: rect.topRight()) ||
2196	!contains(pt: rect.bottomRight()) ||
2197	!contains(pt: rect.bottomLeft()))
2198	return false;
2199	}
2200	}
2201
2202	// If there exists a point inside that is not part of the path its
2203	// because: rectangle lies completely outside path or a subpath
2204	// excludes parts of the rectangle. Both cases mean that the rect
2205	// is not contained
2206	if (!contains(pt: rect.center()))
2207	return false;
2208
2209	// If there are any subpaths inside this rectangle we need to
2210	// check if they are still contained as a result of the fill
2211	// rule. This can only be the case for WindingFill though. For
2212	// OddEvenFill the rect will never be contained if it surrounds a
2213	// subpath. (the case where two subpaths are completely identical
2214	// can be argued but we choose to neglect it).
2215	for (int i=0; i<d->elements.size(); ++i) {
2216	const Element &e = d->elements.at(i);
2217	if (e.type == QPainterPath::MoveToElement && rect.contains(p: e)) {
2218	if (fillRule() == Qt::OddEvenFill)
2219	return false;
2220
2221	bool stop = false;
2222	for (; !stop && i<d->elements.size(); ++i) {
2223	const Element &el = d->elements.at(i);
2224	switch (el.type) {
2225	case MoveToElement:
2226	stop = true;
2227	break;
2228	case LineToElement:
2229	if (!contains(pt: el))
2230	return false;
2231	break;
2232	case CurveToElement:
2233	if (!contains(pt: d->elements.at(i: i+2)))
2234	return false;
2235	i += 2;
2236	break;
2237	default:
2238	break;
2239	}
2240	}
2241
2242	// compensate for the last ++i in the inner for
2243	--i;
2244	}
2245	}
2246
2247	return true;
2248	}
2249
2250	static inline bool epsilonCompare(const QPointF &a, const QPointF &b, const QSizeF &epsilon)
2251	{
2252	return qAbs(t: a.x() - b.x()) <= epsilon.width()
2253	&& qAbs(t: a.y() - b.y()) <= epsilon.height();
2254	}
2255
2256	/*!
2257	Returns \c true if this painterpath is equal to the given \a path.
2258
2259	Note that comparing paths may involve a per element comparison
2260	which can be slow for complex paths.
2261
2262	\sa operator!=()
2263	*/
2264
2265	bool QPainterPath::operator==(const QPainterPath &path) const
2266	{
2267	QPainterPathPrivate *d = d_func();
2268	QPainterPathPrivate *other_d = path.d_func();
2269	if (other_d == d) {
2270	return true;
2271	} else if (!d || !other_d) {
2272	if (!other_d && isEmpty() && elementAt(i: 0) == QPointF() && !d->hasWindingFill)
2273	return true;
2274	if (!d && path.isEmpty() && path.elementAt(i: 0) == QPointF() && !other_d->hasWindingFill)
2275	return true;
2276	return false;
2277	}
2278	else if (d->hasWindingFill != other_d->hasWindingFill)
2279	return false;
2280	else if (d->elements.size() != other_d->elements.size())
2281	return false;
2282
2283	const qreal qt_epsilon = sizeof(qreal) == sizeof(double) ? 1e-12 : qreal(1e-5);
2284
2285	QSizeF epsilon = boundingRect().size();
2286	epsilon.rwidth() *= qt_epsilon;
2287	epsilon.rheight() *= qt_epsilon;
2288
2289	for (int i = 0; i < d->elements.size(); ++i)
2290	if (d->elements.at(i).type != other_d->elements.at(i).type
2291	|| !epsilonCompare(a: d->elements.at(i), b: other_d->elements.at(i), epsilon))
2292	return false;
2293
2294	return true;
2295	}
2296
2297	/*!
2298	Returns \c true if this painter path differs from the given \a path.
2299
2300	Note that comparing paths may involve a per element comparison
2301	which can be slow for complex paths.
2302
2303	\sa operator==()
2304	*/
2305
2306	bool QPainterPath::operator!=(const QPainterPath &path) const
2307	{
2308	return !(*this==path);
2309	}
2310
2311	/*!
2312	\since 4.5
2313
2314	Returns the intersection of this path and the \a other path.
2315
2316	\sa intersected(), operator&=(), united(), operator|()
2317	*/
2318	QPainterPath QPainterPath::operator&(const QPainterPath &other) const
2319	{
2320	return intersected(r: other);
2321	}
2322
2323	/*!
2324	\since 4.5
2325
2326	Returns the union of this path and the \a other path.
2327
2328	\sa united(), operator|=(), intersected(), operator&()
2329	*/
2330	QPainterPath QPainterPath::operator|(const QPainterPath &other) const
2331	{
2332	return united(r: other);
2333	}
2334
2335	/*!
2336	\since 4.5
2337
2338	Returns the union of this path and the \a other path. This function is equivalent
2339	to operator|().
2340
2341	\sa united(), operator+=(), operator-()
2342	*/
2343	QPainterPath QPainterPath::operator+(const QPainterPath &other) const
2344	{
2345	return united(r: other);
2346	}
2347
2348	/*!
2349	\since 4.5
2350
2351	Subtracts the \a other path from a copy of this path, and returns the copy.
2352
2353	\sa subtracted(), operator-=(), operator+()
2354	*/
2355	QPainterPath QPainterPath::operator-(const QPainterPath &other) const
2356	{
2357	return subtracted(r: other);
2358	}
2359
2360	/*!
2361	\since 4.5
2362
2363	Intersects this path with \a other and returns a reference to this path.
2364
2365	\sa intersected(), operator&(), operator|=()
2366	*/
2367	QPainterPath &QPainterPath::operator&=(const QPainterPath &other)
2368	{
2369	return *this = (*this & other);
2370	}
2371
2372	/*!
2373	\since 4.5
2374
2375	Unites this path with \a other and returns a reference to this path.
2376
2377	\sa united(), operator|(), operator&=()
2378	*/
2379	QPainterPath &QPainterPath::operator|=(const QPainterPath &other)
2380	{
2381	return *this = (*this | other);
2382	}
2383
2384	/*!
2385	\since 4.5
2386
2387	Unites this path with \a other, and returns a reference to this path. This
2388	is equivalent to operator|=().
2389
2390	\sa united(), operator+(), operator-=()
2391	*/
2392	QPainterPath &QPainterPath::operator+=(const QPainterPath &other)
2393	{
2394	return *this = (*this + other);
2395	}
2396
2397	/*!
2398	\since 4.5
2399
2400	Subtracts \a other from this path, and returns a reference to this
2401	path.
2402
2403	\sa subtracted(), operator-(), operator+=()
2404	*/
2405	QPainterPath &QPainterPath::operator-=(const QPainterPath &other)
2406	{
2407	return *this = (*this - other);
2408	}
2409
2410	#ifndef QT_NO_DATASTREAM
2411	/*!
2412	\fn QDataStream &operator<<(QDataStream &stream, const QPainterPath &path)
2413	\relates QPainterPath
2414
2415	Writes the given painter \a path to the given \a stream, and
2416	returns a reference to the \a stream.
2417
2418	\sa {Serializing Qt Data Types}
2419	*/
2420	QDataStream &operator<<(QDataStream &s, const QPainterPath &p)
2421	{
2422	if (p.isEmpty()) {
2423	s << 0;
2424	return s;
2425	}
2426
2427	s << p.elementCount();
2428	for (int i=0; i < p.d_func()->elements.size(); ++i) {
2429	const QPainterPath::Element &e = p.d_func()->elements.at(i);
2430	s << int(e.type);
2431	s << double(e.x) << double(e.y);
2432	}
2433	s << p.d_func()->cStart;
2434	s << int(p.fillRule());
2435	return s;
2436	}
2437
2438	/*!
2439	\fn QDataStream &operator>>(QDataStream &stream, QPainterPath &path)
2440	\relates QPainterPath
2441
2442	Reads a painter path from the given \a stream into the specified \a path,
2443	and returns a reference to the \a stream.
2444
2445	\sa {Serializing Qt Data Types}
2446	*/
2447	QDataStream &operator>>(QDataStream &s, QPainterPath &p)
2448	{
2449	bool errorDetected = false;
2450	int size;
2451	s >> size;
2452
2453	if (size == 0) {
2454	p = {};
2455	return s;
2456	}
2457
2458	p.ensureData(); // in case if p.d_func() == 0
2459	p.setDirty(true);
2460	p.d_func()->elements.clear();
2461	for (int i=0; i<size; ++i) {
2462	int type;
2463	double x, y;
2464	s >> type;
2465	s >> x;
2466	s >> y;
2467	Q_ASSERT(type >= 0 && type <= 3);
2468	if (!isValidCoord(c: qreal(x)) || !isValidCoord(c: qreal(y))) {
2469	#ifndef QT_NO_DEBUG
2470	qWarning(msg: "QDataStream::operator>>: Invalid QPainterPath coordinates read, skipping it");
2471	#endif
2472	errorDetected = true;
2473	continue;
2474	}
2475	QPainterPath::Element elm = { .x: qreal(x), .y: qreal(y), .type: QPainterPath::ElementType(type) };
2476	p.d_func()->elements.append(t: elm);
2477	}
2478	s >> p.d_func()->cStart;
2479	int fillRule;
2480	s >> fillRule;
2481	Q_ASSERT(fillRule == Qt::OddEvenFill || fillRule == Qt::WindingFill);
2482	p.d_func()->hasWindingFill = (Qt::FillRule(fillRule) == Qt::WindingFill);
2483	if (errorDetected || p.d_func()->elements.isEmpty())
2484	p = QPainterPath(); // Better than to return path with possibly corrupt datastructure, which would likely cause crash
2485	return s;
2486	}
2487	#endif // QT_NO_DATASTREAM
2488
2489
2490	/*******************************************************************************
2491	* class QPainterPathStroker
2492	*/
2493
2494	void qt_path_stroke_move_to(qfixed x, qfixed y, void *data)
2495	{
2496	((QPainterPath *) data)->moveTo(qt_fixed_to_real(x), qt_fixed_to_real(y));
2497	}
2498
2499	void qt_path_stroke_line_to(qfixed x, qfixed y, void *data)
2500	{
2501	((QPainterPath *) data)->lineTo(qt_fixed_to_real(x), qt_fixed_to_real(y));
2502	}
2503
2504	void qt_path_stroke_cubic_to(qfixed c1x, qfixed c1y,
2505	qfixed c2x, qfixed c2y,
2506	qfixed ex, qfixed ey,
2507	void *data)
2508	{
2509	((QPainterPath *) data)->cubicTo(qt_fixed_to_real(c1x), qt_fixed_to_real(c1y),
2510	qt_fixed_to_real(c2x), qt_fixed_to_real(c2y),
2511	qt_fixed_to_real(ex), qt_fixed_to_real(ey));
2512	}
2513
2514	/*!
2515	\since 4.1
2516	\class QPainterPathStroker
2517	\ingroup painting
2518	\inmodule QtGui
2519
2520	\brief The QPainterPathStroker class is used to generate fillable
2521	outlines for a given painter path.
2522
2523	By calling the createStroke() function, passing a given
2524	QPainterPath as argument, a new painter path representing the
2525	outline of the given path is created. The newly created painter
2526	path can then be filled to draw the original painter path's
2527	outline.
2528
2529	You can control the various design aspects (width, cap styles,
2530	join styles and dash pattern) of the outlining using the following
2531	functions:
2532
2533	\list
2534	\li setWidth()
2535	\li setCapStyle()
2536	\li setJoinStyle()
2537	\li setDashPattern()
2538	\endlist
2539
2540	The setDashPattern() function accepts both a Qt::PenStyle object
2541	and a list representation of the pattern as argument.
2542
2543	In addition you can specify a curve's threshold, controlling the
2544	granularity with which a curve is drawn, using the
2545	setCurveThreshold() function. The default threshold is a well
2546	adjusted value (0.25), and normally you should not need to modify
2547	it. However, you can make the curve's appearance smoother by
2548	decreasing its value.
2549
2550	You can also control the miter limit for the generated outline
2551	using the setMiterLimit() function. The miter limit describes how
2552	far from each join the miter join can extend. The limit is
2553	specified in the units of width so the pixelwise miter limit will
2554	be \c {miterlimit * width}. This value is only used if the join
2555	style is Qt::MiterJoin.
2556
2557	The painter path generated by the createStroke() function should
2558	only be used for outlining the given painter path. Otherwise it
2559	may cause unexpected behavior. Generated outlines also require the
2560	Qt::WindingFill rule which is set by default.
2561
2562	\sa QPen, QBrush
2563	*/
2564
2565	QPainterPathStrokerPrivate::QPainterPathStrokerPrivate()
2566	: dashOffset(0)
2567	{
2568	stroker.setMoveToHook(qt_path_stroke_move_to);
2569	stroker.setLineToHook(qt_path_stroke_line_to);
2570	stroker.setCubicToHook(qt_path_stroke_cubic_to);
2571	}
2572
2573	/*!
2574	Creates a new stroker.
2575	*/
2576	QPainterPathStroker::QPainterPathStroker()
2577	: d_ptr(new QPainterPathStrokerPrivate)
2578	{
2579	}
2580
2581	/*!
2582	Creates a new stroker based on \a pen.
2583
2584	\since 5.3
2585	*/
2586	QPainterPathStroker::QPainterPathStroker(const QPen &pen)
2587	: d_ptr(new QPainterPathStrokerPrivate)
2588	{
2589	setWidth(pen.widthF());
2590	setCapStyle(pen.capStyle());
2591	setJoinStyle(pen.joinStyle());
2592	setMiterLimit(pen.miterLimit());
2593	setDashOffset(pen.dashOffset());
2594
2595	if (pen.style() == Qt::CustomDashLine)
2596	setDashPattern(pen.dashPattern());
2597	else
2598	setDashPattern(pen.style());
2599	}
2600
2601	/*!
2602	Destroys the stroker.
2603	*/
2604	QPainterPathStroker::~QPainterPathStroker()
2605	{
2606	}
2607
2608
2609	/*!
2610	Generates a new path that is a fillable area representing the
2611	outline of the given \a path.
2612
2613	The various design aspects of the outline are based on the
2614	stroker's properties: width(), capStyle(), joinStyle(),
2615	dashPattern(), curveThreshold() and miterLimit().
2616
2617	The generated path should only be used for outlining the given
2618	painter path. Otherwise it may cause unexpected
2619	behavior. Generated outlines also require the Qt::WindingFill rule
2620	which is set by default.
2621	*/
2622	QPainterPath QPainterPathStroker::createStroke(const QPainterPath &path) const
2623	{
2624	QPainterPathStrokerPrivate *d = const_cast<QPainterPathStrokerPrivate *>(d_func());
2625	QPainterPath stroke;
2626	if (path.isEmpty())
2627	return path;
2628	if (d->dashPattern.isEmpty()) {
2629	d->stroker.strokePath(path, data: &stroke, matrix: QTransform());
2630	} else {
2631	QDashStroker dashStroker(&d->stroker);
2632	dashStroker.setDashPattern(d->dashPattern);
2633	dashStroker.setDashOffset(d->dashOffset);
2634	dashStroker.setClipRect(d->stroker.clipRect());
2635	dashStroker.strokePath(path, data: &stroke, matrix: QTransform());
2636	}
2637	stroke.setFillRule(Qt::WindingFill);
2638	return stroke;
2639	}
2640
2641	/*!
2642	Sets the width of the generated outline painter path to \a width.
2643
2644	The generated outlines will extend approximately 50% of \a width
2645	to each side of the given input path's original outline.
2646	*/
2647	void QPainterPathStroker::setWidth(qreal width)
2648	{
2649	Q_D(QPainterPathStroker);
2650	if (width <= 0)
2651	width = 1;
2652	d->stroker.setStrokeWidth(qt_real_to_fixed(width));
2653	}
2654
2655	/*!
2656	Returns the width of the generated outlines.
2657	*/
2658	qreal QPainterPathStroker::width() const
2659	{
2660	return qt_fixed_to_real(d_func()->stroker.strokeWidth());
2661	}
2662
2663
2664	/*!
2665	Sets the cap style of the generated outlines to \a style. If a
2666	dash pattern is set, each segment of the pattern is subject to the
2667	cap \a style.
2668	*/
2669	void QPainterPathStroker::setCapStyle(Qt::PenCapStyle style)
2670	{
2671	d_func()->stroker.setCapStyle(style);
2672	}
2673
2674
2675	/*!
2676	Returns the cap style of the generated outlines.
2677	*/
2678	Qt::PenCapStyle QPainterPathStroker::capStyle() const
2679	{
2680	return d_func()->stroker.capStyle();
2681	}
2682
2683	/*!
2684	Sets the join style of the generated outlines to \a style.
2685	*/
2686	void QPainterPathStroker::setJoinStyle(Qt::PenJoinStyle style)
2687	{
2688	d_func()->stroker.setJoinStyle(style);
2689	}
2690
2691	/*!
2692	Returns the join style of the generated outlines.
2693	*/
2694	Qt::PenJoinStyle QPainterPathStroker::joinStyle() const
2695	{
2696	return d_func()->stroker.joinStyle();
2697	}
2698
2699	/*!
2700	Sets the miter limit of the generated outlines to \a limit.
2701
2702	The miter limit describes how far from each join the miter join
2703	can extend. The limit is specified in units of the currently set
2704	width. So the pixelwise miter limit will be \c { miterlimit *
2705	width}.
2706
2707	This value is only used if the join style is Qt::MiterJoin.
2708	*/
2709	void QPainterPathStroker::setMiterLimit(qreal limit)
2710	{
2711	d_func()->stroker.setMiterLimit(qt_real_to_fixed(limit));
2712	}
2713
2714	/*!
2715	Returns the miter limit for the generated outlines.
2716	*/
2717	qreal QPainterPathStroker::miterLimit() const
2718	{
2719	return qt_fixed_to_real(d_func()->stroker.miterLimit());
2720	}
2721
2722
2723	/*!
2724	Specifies the curve flattening \a threshold, controlling the
2725	granularity with which the generated outlines' curve is drawn.
2726
2727	The default threshold is a well adjusted value (0.25), and
2728	normally you should not need to modify it. However, you can make
2729	the curve's appearance smoother by decreasing its value.
2730	*/
2731	void QPainterPathStroker::setCurveThreshold(qreal threshold)
2732	{
2733	d_func()->stroker.setCurveThreshold(qt_real_to_fixed(threshold));
2734	}
2735
2736	/*!
2737	Returns the curve flattening threshold for the generated
2738	outlines.
2739	*/
2740	qreal QPainterPathStroker::curveThreshold() const
2741	{
2742	return qt_fixed_to_real(d_func()->stroker.curveThreshold());
2743	}
2744
2745	/*!
2746	Sets the dash pattern for the generated outlines to \a style.
2747	*/
2748	void QPainterPathStroker::setDashPattern(Qt::PenStyle style)
2749	{
2750	d_func()->dashPattern = QDashStroker::patternForStyle(style);
2751	}
2752
2753	/*!
2754	\overload
2755
2756	Sets the dash pattern for the generated outlines to \a
2757	dashPattern. This function makes it possible to specify custom
2758	dash patterns.
2759
2760	Each element in the list contains the lengths of the dashes and spaces
2761	in the stroke, beginning with the first dash in the first element, the
2762	first space in the second element, and alternating between dashes and
2763	spaces for each following pair of elements.
2764
2765	The list can contain an odd number of elements, in which case the last
2766	element will be extended by the length of the first element when the
2767	pattern repeats.
2768	*/
2769	void QPainterPathStroker::setDashPattern(const QList<qreal> &dashPattern)
2770	{
2771	d_func()->dashPattern.clear();
2772	for (int i=0; i<dashPattern.size(); ++i)
2773	d_func()->dashPattern << qt_real_to_fixed(dashPattern.at(i));
2774	}
2775
2776	/*!
2777	Returns the dash pattern for the generated outlines.
2778	*/
2779	QList<qreal> QPainterPathStroker::dashPattern() const
2780	{
2781	return d_func()->dashPattern;
2782	}
2783
2784	/*!
2785	Returns the dash offset for the generated outlines.
2786	*/
2787	qreal QPainterPathStroker::dashOffset() const
2788	{
2789	return d_func()->dashOffset;
2790	}
2791
2792	/*!
2793	Sets the dash offset for the generated outlines to \a offset.
2794
2795	See the documentation for QPen::setDashOffset() for a description of the
2796	dash offset.
2797	*/
2798	void QPainterPathStroker::setDashOffset(qreal offset)
2799	{
2800	d_func()->dashOffset = offset;
2801	}
2802
2803	/*!
2804	Converts the path into a polygon using the QTransform
2805	\a matrix, and returns the polygon.
2806
2807	The polygon is created by first converting all subpaths to
2808	polygons, then using a rewinding technique to make sure that
2809	overlapping subpaths can be filled using the correct fill rule.
2810
2811	Note that rewinding inserts addition lines in the polygon so
2812	the outline of the fill polygon does not match the outline of
2813	the path.
2814
2815	\sa toSubpathPolygons(), toFillPolygons(),
2816	{QPainterPath#QPainterPath Conversion}{QPainterPath Conversion}
2817	*/
2818	QPolygonF QPainterPath::toFillPolygon(const QTransform &matrix) const
2819	{
2820	const QList<QPolygonF> flats = toSubpathPolygons(matrix);
2821	QPolygonF polygon;
2822	if (flats.isEmpty())
2823	return polygon;
2824	QPointF first = flats.first().first();
2825	for (int i=0; i<flats.size(); ++i) {
2826	polygon += flats.at(i);
2827	if (!flats.at(i).isClosed())
2828	polygon += flats.at(i).first();
2829	if (i > 0)
2830	polygon += first;
2831	}
2832	return polygon;
2833	}
2834
2835	/*!
2836	Returns true if caching is enabled; otherwise returns false.
2837
2838	\since 6.10
2839	\sa setCachingEnabled()
2840	*/
2841	bool QPainterPath::isCachingEnabled() const
2842	{
2843	Q_D(QPainterPath);
2844	return d && d->cacheEnabled;
2845	}
2846
2847	/*!
2848	Enables or disables length caching according to the value of \a enabled.
2849
2850	Enabling caching speeds up repeated calls to the member functions involving path length
2851	and percentage values, such as length(), percentAtLength(), pointAtPercent() etc., at the cost
2852	of some extra memory usage for storage of intermediate calculations. By default it is disabled.
2853
2854	Disabling caching will release any allocated cache memory.
2855
2856	\since 6.10
2857	\sa isCachingEnabled(), length(), percentAtLength(), pointAtPercent(), trimmed()
2858	*/
2859	void QPainterPath::setCachingEnabled(bool enabled)
2860	{
2861	ensureData();
2862	if (d_func()->cacheEnabled == enabled)
2863	return;
2864	setDirty(true);
2865	QPainterPathPrivate *d = d_func();
2866	d->cacheEnabled = enabled;
2867	if (!enabled) {
2868	d->m_runLengths.clear();
2869	d->m_runLengths.squeeze();
2870	}
2871	}
2872
2873	//derivative of the equation
2874	static inline qreal slopeAt(qreal t, qreal a, qreal b, qreal c, qreal d)
2875	{
2876	return 3*t*t*(d - 3*c + 3*b - a) + 6*t*(c - 2*b + a) + 3*(b - a);
2877	}
2878
2879	/*!
2880	Returns the length of the current path.
2881	*/
2882	qreal QPainterPath::length() const
2883	{
2884	Q_D(QPainterPath);
2885	if (isEmpty())
2886	return 0;
2887	if (d->cacheEnabled) {
2888	if (d->dirtyRunLengths)
2889	d->computeRunLengths();
2890	return d->m_runLengths.last();
2891	}
2892
2893	qreal len = 0;
2894	for (int i=1; i<d->elements.size(); ++i) {
2895	const Element &e = d->elements.at(i);
2896
2897	switch (e.type) {
2898	case MoveToElement:
2899	break;
2900	case LineToElement:
2901	{
2902	len += QLineF(d->elements.at(i: i-1), e).length();
2903	break;
2904	}
2905	case CurveToElement:
2906	{
2907	QBezier b = QBezier::fromPoints(p1: d->elements.at(i: i-1),
2908	p2: e,
2909	p3: d->elements.at(i: i+1),
2910	p4: d->elements.at(i: i+2));
2911	len += b.length();
2912	i += 2;
2913	break;
2914	}
2915	default:
2916	break;
2917	}
2918	}
2919	return len;
2920	}
2921
2922	/*!
2923	Returns percentage of the whole path at the specified length \a len.
2924
2925	Note that similarly to other percent methods, the percentage measurement
2926	is not linear with regards to the length, if curves are present
2927	in the path. When curves are present the percentage argument is mapped
2928	to the t parameter of the Bezier equations.
2929	*/
2930	qreal QPainterPath::percentAtLength(qreal len) const
2931	{
2932	Q_D(QPainterPath);
2933	if (isEmpty() || len <= 0)
2934	return 0;
2935
2936	qreal totalLength = length();
2937	if (len > totalLength)
2938	return 1;
2939
2940	if (d->cacheEnabled) {
2941	const int ei = qMax(a: d->elementAtT(t: len / totalLength), b: 1); // Skip initial MoveTo
2942	qreal res = 0;
2943	const QPainterPath::Element &e = d->elements[ei];
2944	switch (e.type) {
2945	case QPainterPath::LineToElement:
2946	res = len / totalLength;
2947	break;
2948	case CurveToElement:
2949	{
2950	QBezier b = QBezier::fromPoints(p1: d->elements.at(i: ei-1),
2951	p2: e,
2952	p3: d->elements.at(i: ei+1),
2953	p4: d->elements.at(i: ei+2));
2954	qreal prevLen = d->m_runLengths[ei - 1];
2955	qreal blen = d->m_runLengths[ei] - prevLen;
2956	qreal elemRes = b.tAtLength(len: len - prevLen);
2957	res = (elemRes * blen + prevLen) / totalLength;
2958	break;
2959	}
2960	default:
2961	Q_UNREACHABLE();
2962	}
2963	return res;
2964	}
2965
2966	qreal curLen = 0;
2967	for (int i=1; i<d->elements.size(); ++i) {
2968	const Element &e = d->elements.at(i);
2969
2970	switch (e.type) {
2971	case MoveToElement:
2972	break;
2973	case LineToElement:
2974	{
2975	QLineF line(d->elements.at(i: i-1), e);
2976	qreal llen = line.length();
2977	curLen += llen;
2978	if (curLen >= len) {
2979	return len/totalLength ;
2980	}
2981
2982	break;
2983	}
2984	case CurveToElement:
2985	{
2986	QBezier b = QBezier::fromPoints(p1: d->elements.at(i: i-1),
2987	p2: e,
2988	p3: d->elements.at(i: i+1),
2989	p4: d->elements.at(i: i+2));
2990	qreal blen = b.length();
2991	qreal prevLen = curLen;
2992	curLen += blen;
2993
2994	if (curLen >= len) {
2995	qreal res = b.tAtLength(len: len - prevLen);
2996	return (res * blen + prevLen)/totalLength;
2997	}
2998
2999	i += 2;
3000	break;
3001	}
3002	default:
3003	break;
3004	}
3005	}
3006
3007	return 0;
3008	}
3009
3010	static inline QBezier uncached_bezierAtT(const QPainterPath &path, qreal t, qreal *startingLength,
3011	qreal *bezierLength)
3012	{
3013	*startingLength = 0;
3014	if (t > 1)
3015	return QBezier();
3016
3017	qreal curLen = 0;
3018	qreal totalLength = path.length();
3019
3020	const int lastElement = path.elementCount() - 1;
3021	for (int i=0; i <= lastElement; ++i) {
3022	const QPainterPath::Element &e = path.elementAt(i);
3023
3024	switch (e.type) {
3025	case QPainterPath::MoveToElement:
3026	break;
3027	case QPainterPath::LineToElement:
3028	{
3029	QLineF line(path.elementAt(i: i-1), e);
3030	qreal llen = line.length();
3031	curLen += llen;
3032	if (i == lastElement || curLen/totalLength >= t) {
3033	*bezierLength = llen;
3034	QPointF a = path.elementAt(i: i-1);
3035	QPointF delta = e - a;
3036	return QBezier::fromPoints(p1: a, p2: a + delta / 3, p3: a + 2 * delta / 3, p4: e);
3037	}
3038	break;
3039	}
3040	case QPainterPath::CurveToElement:
3041	{
3042	QBezier b = QBezier::fromPoints(p1: path.elementAt(i: i-1),
3043	p2: e,
3044	p3: path.elementAt(i: i+1),
3045	p4: path.elementAt(i: i+2));
3046	qreal blen = b.length();
3047	curLen += blen;
3048
3049	if (i + 2 == lastElement || curLen/totalLength >= t) {
3050	*bezierLength = blen;
3051	return b;
3052	}
3053
3054	i += 2;
3055	break;
3056	}
3057	default:
3058	break;
3059	}
3060	*startingLength = curLen;
3061	}
3062	return QBezier();
3063	}
3064
3065	QBezier QPainterPathPrivate::bezierAtT(const QPainterPath &path, qreal t, qreal *startingLength,
3066	qreal *bezierLength) const
3067	{
3068	Q_ASSERT(t >= 0 && t <= 1);
3069	QPainterPathPrivate *d = path.d_func();
3070	if (!path.isEmpty() && d->cacheEnabled) {
3071	const int ei = qMax(a: d->elementAtT(t), b: 1); // Avoid the initial MoveTo element
3072	const qreal prevRunLength = d->m_runLengths[ei - 1];
3073	*startingLength = prevRunLength;
3074	*bezierLength = d->m_runLengths[ei] - prevRunLength;
3075	const QPointF prev = d->elements[ei - 1];
3076	const QPainterPath::Element &e = d->elements[ei];
3077	switch (e.type) {
3078	case QPainterPath::LineToElement:
3079	{
3080	QPointF delta = (e - prev) / 3;
3081	return QBezier::fromPoints(p1: prev, p2: prev + delta, p3: prev + 2 * delta, p4: e);
3082	}
3083	case QPainterPath::CurveToElement:
3084	return QBezier::fromPoints(p1: prev, p2: e, p3: elements[ei + 1], p4: elements[ei + 2]);
3085	break;
3086	default:
3087	Q_UNREACHABLE();
3088	}
3089	}
3090
3091	return uncached_bezierAtT(path, t, startingLength, bezierLength);
3092	}
3093
3094	/*!
3095	Returns the point at at the percentage \a t of the current path.
3096	The argument \a t has to be between 0 and 1.
3097
3098	Note that similarly to other percent methods, the percentage measurement
3099	is not linear with regards to the length, if curves are present
3100	in the path. When curves are present the percentage argument is mapped
3101	to the t parameter of the Bezier equations.
3102	*/
3103	QPointF QPainterPath::pointAtPercent(qreal t) const
3104	{
3105	if (t < 0 || t > 1) {
3106	qWarning(msg: "QPainterPath::pointAtPercent accepts only values between 0 and 1");
3107	return QPointF();
3108	}
3109
3110	if (!d_ptr || d_ptr->elements.size() == 0)
3111	return QPointF();
3112
3113	if (d_ptr->elements.size() == 1)
3114	return d_ptr->elements.at(i: 0);
3115
3116	qreal totalLength = length();
3117	qreal curLen = 0;
3118	qreal bezierLen = 0;
3119	QBezier b = d_ptr->bezierAtT(path: *this, t, startingLength: &curLen, bezierLength: &bezierLen);
3120	qreal realT = (totalLength * t - curLen) / bezierLen;
3121
3122	return b.pointAt(t: qBound(min: qreal(0), val: realT, max: qreal(1)));
3123	}
3124
3125	/*!
3126	Returns the angle of the path tangent at the percentage \a t.
3127	The argument \a t has to be between 0 and 1.
3128
3129	Positive values for the angles mean counter-clockwise while negative values
3130	mean the clockwise direction. Zero degrees is at the 3 o'clock position.
3131
3132	Note that similarly to the other percent methods, the percentage measurement
3133	is not linear with regards to the length if curves are present
3134	in the path. When curves are present the percentage argument is mapped
3135	to the t parameter of the Bezier equations.
3136	*/
3137	qreal QPainterPath::angleAtPercent(qreal t) const
3138	{
3139	if (t < 0 || t > 1) {
3140	qWarning(msg: "QPainterPath::angleAtPercent accepts only values between 0 and 1");
3141	return 0;
3142	}
3143
3144	qreal totalLength = length();
3145	qreal curLen = 0;
3146	qreal bezierLen = 0;
3147	QBezier bez = d_ptr->bezierAtT(path: *this, t, startingLength: &curLen, bezierLength: &bezierLen);
3148	qreal realT = (totalLength * t - curLen) / bezierLen;
3149
3150	qreal m1 = slopeAt(t: realT, a: bez.x1, b: bez.x2, c: bez.x3, d: bez.x4);
3151	qreal m2 = slopeAt(t: realT, a: bez.y1, b: bez.y2, c: bez.y3, d: bez.y4);
3152
3153	return QLineF(0, 0, m1, m2).angle();
3154	}
3155
3156
3157	/*!
3158	Returns the slope of the path at the percentage \a t. The
3159	argument \a t has to be between 0 and 1.
3160
3161	Note that similarly to other percent methods, the percentage measurement
3162	is not linear with regards to the length, if curves are present
3163	in the path. When curves are present the percentage argument is mapped
3164	to the t parameter of the Bezier equations.
3165	*/
3166	qreal QPainterPath::slopeAtPercent(qreal t) const
3167	{
3168	if (t < 0 || t > 1) {
3169	qWarning(msg: "QPainterPath::slopeAtPercent accepts only values between 0 and 1");
3170	return 0;
3171	}
3172
3173	qreal totalLength = length();
3174	qreal curLen = 0;
3175	qreal bezierLen = 0;
3176	QBezier bez = d_ptr->bezierAtT(path: *this, t, startingLength: &curLen, bezierLength: &bezierLen);
3177	qreal realT = (totalLength * t - curLen) / bezierLen;
3178
3179	qreal m1 = slopeAt(t: realT, a: bez.x1, b: bez.x2, c: bez.x3, d: bez.x4);
3180	qreal m2 = slopeAt(t: realT, a: bez.y1, b: bez.y2, c: bez.y3, d: bez.y4);
3181	//tangent line
3182	qreal slope = 0;
3183
3184	if (m1)
3185	slope = m2/m1;
3186	else {
3187	if (std::numeric_limits<qreal>::has_infinity) {
3188	slope = (m2 < 0) ? -std::numeric_limits<qreal>::infinity()
3189	: std::numeric_limits<qreal>::infinity();
3190	} else {
3191	if (sizeof(qreal) == sizeof(double)) {
3192	return 1.79769313486231570e+308;
3193	} else {
3194	return ((qreal)3.40282346638528860e+38);
3195	}
3196	}
3197	}
3198
3199	return slope;
3200	}
3201
3202	/*!
3203	\since 6.10
3204
3205	Returns the section of the path between the length fractions \a fromFraction and \a toFraction.
3206	The effective range of the fractions are from 0, denoting the start point of the path, to 1,
3207	denoting its end point. The fractions are linear with respect to path length, in contrast to the
3208	percentage \e t values.
3209
3210	The value of \a offset will be added to the fraction values. If that causes an over- or underflow
3211	of the [0, 1] range, the values will be wrapped around, as will the resulting path. The effective
3212	range of the offset is between -1 and 1.
3213
3214	Repeated calls to this function can be optimized by {enabling caching}{setCachingEnabled()}.
3215
3216	\sa length(), percentAtLength(), setCachingEnabled()
3217	*/
3218
3219	QPainterPath QPainterPath::trimmed(qreal fromFraction, qreal toFraction, qreal offset) const
3220	{
3221	if (isEmpty())
3222	return *this;
3223
3224	// We need length caching enabled for the calculations.
3225	if (!isCachingEnabled()) {
3226	QPainterPath copy(*this);
3227	copy.setCachingEnabled(true);
3228	return copy.trimmed(fromFraction, toFraction, offset);
3229	}
3230
3231	qreal f1 = qBound(min: qreal(0), val: fromFraction, max: qreal(1));
3232	qreal f2 = qBound(min: qreal(0), val: toFraction, max: qreal(1));
3233	if (f1 > f2)
3234	qSwap(value1&: f1, value2&: f2);
3235	if (qFuzzyCompare(p1: f2 - f1, p2: qreal(1))) // Shortcut for no trimming
3236	return *this;
3237
3238	QPainterPath res;
3239	if (qFuzzyCompare(p1: f1, p2: f2))
3240	return res;
3241	res.setFillRule(fillRule());
3242
3243	if (offset) {
3244	qreal dummy;
3245	offset = std::modf(x: offset, iptr: &dummy); // Use only the fractional part of offset, range <-1, 1>
3246
3247	qreal of1 = f1 + offset;
3248	qreal of2 = f2 + offset;
3249	if (offset < 0) {
3250	f1 = of1 < 0 ? of1 + 1 : of1;
3251	f2 = of2 + 1 > 1 ? of2 : of2 + 1;
3252	} else if (offset > 0) {
3253	f1 = of1 - 1 < 0 ? of1 : of1 - 1;
3254	f2 = of2 > 1 ? of2 - 1 : of2;
3255	}
3256	}
3257	const bool wrapping = (f1 > f2);
3258	//qDebug() << "ADJ:" << f1 << f2 << wrapping << "(" << of1 << of2 << ")";
3259
3260	QPainterPathPrivate *d = d_func();
3261	if (d->dirtyRunLengths)
3262	d->computeRunLengths();
3263	const qreal totalLength = d->m_runLengths.last();
3264	if (qFuzzyIsNull(d: totalLength))
3265	return res;
3266
3267	const qreal l1 = f1 * totalLength;
3268	const qreal l2 = f2 * totalLength;
3269	const int e1 = d->elementAtLength(len: l1);
3270	const bool mustTrimE1 = !qFuzzyCompare(p1: d->m_runLengths.at(i: e1), p2: l1);
3271	const int e2 = d->elementAtLength(len: l2);
3272	const bool mustTrimE2 = !qFuzzyCompare(p1: d->m_runLengths.at(i: e2), p2: l2);
3273
3274	//qDebug() << "Trim [" << f1 << f2 << "] e1:" << e1 << mustTrimE1 << "e2:" << e2 << mustTrimE2 << "wrapping:" << wrapping;
3275	if (e1 == e2 && !wrapping && mustTrimE1 && mustTrimE2) {
3276	// Entire result is one element, clipped in both ends
3277	d->appendSliceOfElement(to: &res, elemIdx: e1, fromLen: l1, toLen: l2);
3278	} else {
3279	// Add partial start element (or just its end point, being the start of the next)
3280	if (mustTrimE1)
3281	d->appendEndOfElement(to: &res, elemIdx: e1, len: l1);
3282	else
3283	res.moveTo(p: d->endPointOfElement(elemIdx: e1));
3284
3285	// Add whole elements between start and end
3286	int firstWholeElement = e1 + 1;
3287	int lastWholeElement = (mustTrimE2 ? e2 - 1 : e2);
3288	if (!wrapping) {
3289	d->appendElementRange(to: &res, first: firstWholeElement, last: lastWholeElement);
3290	} else {
3291	int lastIndex = d->elements.size() - 1;
3292	d->appendElementRange(to: &res, first: firstWholeElement, last: lastIndex);
3293	bool isClosed = (QPointF(d->elements.at(i: 0)) == QPointF(d->elements.at(i: lastIndex)));
3294	// If closed we can skip the initial moveto
3295	d->appendElementRange(to: &res, first: (isClosed ? 1 : 0), last: lastWholeElement);
3296	}
3297
3298	// Partial end element
3299	if (mustTrimE2)
3300	d->appendStartOfElement(to: &res, elemIdx: e2, len: l2);
3301	}
3302
3303	return res;
3304	}
3305
3306	void QPainterPathPrivate::appendTrimmedElement(QPainterPath *to, int elemIdx, int trimFlags,
3307	qreal startLen, qreal endLen)
3308	{
3309	Q_ASSERT(cacheEnabled);
3310	Q_ASSERT(!dirtyRunLengths);
3311
3312	if (elemIdx <= 0 || elemIdx >= elements.size())
3313	return;
3314
3315	const qreal prevLen = m_runLengths.at(i: elemIdx - 1);
3316	const qreal elemLen = m_runLengths.at(i: elemIdx) - prevLen;
3317	const qreal len1 = startLen - prevLen;
3318	const qreal len2 = endLen - prevLen;
3319	if (qFuzzyIsNull(d: elemLen))
3320	return;
3321
3322	const QPointF pp = elements.at(i: elemIdx - 1);
3323	const QPainterPath::Element e = elements.at(i: elemIdx);
3324	if (e.isLineTo()) {
3325	QLineF l(pp, e);
3326	QPointF p1 = (trimFlags & TrimStart) ? l.pointAt(t: len1 / elemLen) : pp;
3327	QPointF p2 = (trimFlags & TrimEnd) ? l.pointAt(t: len2 / elemLen) : e;
3328	if (to->isEmpty())
3329	to->moveTo(p: p1);
3330	to->lineTo(p: p2);
3331	} else if (e.isCurveTo()) {
3332	Q_ASSERT(elemIdx < elements.size() - 2);
3333	QBezier b = QBezier::fromPoints(p1: pp, p2: e, p3: elements.at(i: elemIdx + 1), p4: elements.at(i: elemIdx + 2));
3334	qreal t1 = (trimFlags & TrimStart) ? b.tAtLength(len: len1) : 0.0; // or simply len1/elemLen to trim by t instead of len
3335	qreal t2 = (trimFlags & TrimEnd) ? b.tAtLength(len: len2) : 1.0;
3336	QBezier c = b.getSubRange(t0: t1, t1: t2);
3337	if (to->isEmpty())
3338	to->moveTo(p: c.pt1());
3339	to->cubicTo(c1: c.pt2(), c2: c.pt3(), e: c.pt4());
3340	} else {
3341	Q_UNREACHABLE();
3342	}
3343	}
3344
3345	void QPainterPathPrivate::appendElementRange(QPainterPath *to, int first, int last)
3346	{
3347	if (first < 0 || first >= elements.size() || last < 0 || last >= elements.size())
3348	return;
3349
3350	// (Could optimize by direct copy of elements, but must ensure correct state flags)
3351	for (int i = first; i <= last; i++) {
3352	const QPainterPath::Element &e = elements.at(i);
3353	switch (e.type) {
3354	case QPainterPath::MoveToElement:
3355	to->moveTo(p: e);
3356	break;
3357	case QPainterPath::LineToElement:
3358	to->lineTo(p: e);
3359	break;
3360	case QPainterPath::CurveToElement:
3361	Q_ASSERT(i < elements.size() - 2);
3362	to->cubicTo(c1: e, c2: elements.at(i: i + 1), e: elements.at(i: i + 2));
3363	i += 2;
3364	break;
3365	default:
3366	// 'first' may point to CurveToData element, just skip it
3367	break;
3368	}
3369	}
3370	}
3371
3372
3373	/*!
3374	\since 4.4
3375
3376	Adds the given rectangle \a rect with rounded corners to the path.
3377
3378	The \a xRadius and \a yRadius arguments specify the radii of
3379	the ellipses defining the corners of the rounded rectangle.
3380	When \a mode is Qt::RelativeSize, \a xRadius and
3381	\a yRadius are specified in percentage of half the rectangle's
3382	width and height respectively, and should be in the range 0.0 to 100.0.
3383
3384	\sa addRect()
3385	*/
3386	void QPainterPath::addRoundedRect(const QRectF &rect, qreal xRadius, qreal yRadius,
3387	Qt::SizeMode mode)
3388	{
3389	QRectF r = rect.normalized();
3390
3391	if (r.isNull())
3392	return;
3393
3394	if (mode == Qt::AbsoluteSize) {
3395	qreal w = r.width() / 2;
3396	qreal h = r.height() / 2;
3397
3398	if (w == 0) {
3399	xRadius = 0;
3400	} else {
3401	xRadius = 100 * qMin(a: xRadius, b: w) / w;
3402	}
3403	if (h == 0) {
3404	yRadius = 0;
3405	} else {
3406	yRadius = 100 * qMin(a: yRadius, b: h) / h;
3407	}
3408	} else {
3409	if (xRadius > 100) // fix ranges
3410	xRadius = 100;
3411
3412	if (yRadius > 100)
3413	yRadius = 100;
3414	}
3415
3416	if (xRadius <= 0 || yRadius <= 0) { // add normal rectangle
3417	addRect(r);
3418	return;
3419	}
3420
3421	qreal x = r.x();
3422	qreal y = r.y();
3423	qreal w = r.width();
3424	qreal h = r.height();
3425	qreal rxx2 = w*xRadius/100;
3426	qreal ryy2 = h*yRadius/100;
3427
3428	ensureData();
3429	setDirty(true);
3430
3431	bool first = d_func()->elements.size() < 2;
3432
3433	arcMoveTo(x, y, w: rxx2, h: ryy2, angle: 180);
3434	arcTo(x, y, w: rxx2, h: ryy2, startAngle: 180, arcLength: -90);
3435	arcTo(x: x+w-rxx2, y, w: rxx2, h: ryy2, startAngle: 90, arcLength: -90);
3436	arcTo(x: x+w-rxx2, y: y+h-ryy2, w: rxx2, h: ryy2, startAngle: 0, arcLength: -90);
3437	arcTo(x, y: y+h-ryy2, w: rxx2, h: ryy2, startAngle: 270, arcLength: -90);
3438	closeSubpath();
3439
3440	d_func()->require_moveTo = true;
3441	d_func()->convex = first;
3442	}
3443
3444	/*!
3445	\fn void QPainterPath::addRoundedRect(qreal x, qreal y, qreal w, qreal h, qreal xRadius, qreal yRadius, Qt::SizeMode mode = Qt::AbsoluteSize);
3446	\since 4.4
3447	\overload
3448
3449	Adds the given rectangle \a x, \a y, \a w, \a h with rounded corners to the path.
3450	*/
3451
3452	/*!
3453	\since 4.3
3454
3455	Returns a path which is the union of this path's fill area and \a p's fill area.
3456
3457	Set operations on paths will treat the paths as areas. Non-closed
3458	paths will be treated as implicitly closed.
3459	Bezier curves may be flattened to line segments due to numerical instability of
3460	doing bezier curve intersections.
3461
3462	\sa intersected(), subtracted()
3463	*/
3464	QPainterPath QPainterPath::united(const QPainterPath &p) const
3465	{
3466	if (isEmpty() || p.isEmpty())
3467	return isEmpty() ? p : *this;
3468	QPathClipper clipper(*this, p);
3469	return clipper.clip(op: QPathClipper::BoolOr);
3470	}
3471
3472	/*!
3473	\since 4.3
3474
3475	Returns a path which is the intersection of this path's fill area and \a p's fill area.
3476	Bezier curves may be flattened to line segments due to numerical instability of
3477	doing bezier curve intersections.
3478	*/
3479	QPainterPath QPainterPath::intersected(const QPainterPath &p) const
3480	{
3481	if (isEmpty() || p.isEmpty())
3482	return QPainterPath();
3483	QPathClipper clipper(*this, p);
3484	return clipper.clip(op: QPathClipper::BoolAnd);
3485	}
3486
3487	/*!
3488	\since 4.3
3489
3490	Returns a path which is \a p's fill area subtracted from this path's fill area.
3491
3492	Set operations on paths will treat the paths as areas. Non-closed
3493	paths will be treated as implicitly closed.
3494	Bezier curves may be flattened to line segments due to numerical instability of
3495	doing bezier curve intersections.
3496	*/
3497	QPainterPath QPainterPath::subtracted(const QPainterPath &p) const
3498	{
3499	if (isEmpty() || p.isEmpty())
3500	return *this;
3501	QPathClipper clipper(*this, p);
3502	return clipper.clip(op: QPathClipper::BoolSub);
3503	}
3504
3505	/*!
3506	\since 4.4
3507
3508	Returns a simplified version of this path. This implies merging all subpaths that intersect,
3509	and returning a path containing no intersecting edges. Consecutive parallel lines will also
3510	be merged. The simplified path will always use the default fill rule, Qt::OddEvenFill.
3511	Bezier curves may be flattened to line segments due to numerical instability of
3512	doing bezier curve intersections.
3513	*/
3514	QPainterPath QPainterPath::simplified() const
3515	{
3516	if (isEmpty())
3517	return *this;
3518	QPathClipper clipper(*this, QPainterPath());
3519	return clipper.clip(op: QPathClipper::Simplify);
3520	}
3521
3522	/*!
3523	\since 4.3
3524
3525	Returns \c true if the current path intersects at any point the given path \a p.
3526	Also returns \c true if the current path contains or is contained by any part of \a p.
3527
3528	Set operations on paths will treat the paths as areas. Non-closed
3529	paths will be treated as implicitly closed.
3530
3531	\sa contains()
3532	*/
3533	bool QPainterPath::intersects(const QPainterPath &p) const
3534	{
3535	if (p.elementCount() == 1)
3536	return contains(pt: p.elementAt(i: 0));
3537	if (isEmpty() || p.isEmpty())
3538	return false;
3539	QPathClipper clipper(*this, p);
3540	return clipper.intersect();
3541	}
3542
3543	/*!
3544	\since 4.3
3545
3546	Returns \c true if the given path \a p is contained within
3547	the current path. Returns \c false if any edges of the current path and
3548	\a p intersect.
3549
3550	Set operations on paths will treat the paths as areas. Non-closed
3551	paths will be treated as implicitly closed.
3552
3553	\sa intersects()
3554	*/
3555	bool QPainterPath::contains(const QPainterPath &p) const
3556	{
3557	if (p.elementCount() == 1)
3558	return contains(pt: p.elementAt(i: 0));
3559	if (isEmpty() || p.isEmpty())
3560	return false;
3561	QPathClipper clipper(*this, p);
3562	return clipper.contains();
3563	}
3564
3565	void QPainterPath::setDirty(bool dirty)
3566	{
3567	d_func()->pathConverter.reset();
3568	d_func()->dirtyBounds = dirty;
3569	d_func()->dirtyControlBounds = dirty;
3570	d_func()->dirtyRunLengths = dirty;
3571	d_func()->convex = false;
3572	}
3573
3574	void QPainterPath::computeBoundingRect() const
3575	{
3576	QPainterPathPrivate *d = d_func();
3577	d->dirtyBounds = false;
3578	if (!d_ptr) {
3579	d->bounds = QRect();
3580	return;
3581	}
3582
3583	qreal minx, maxx, miny, maxy;
3584	minx = maxx = d->elements.at(i: 0).x;
3585	miny = maxy = d->elements.at(i: 0).y;
3586	for (int i=1; i<d->elements.size(); ++i) {
3587	const Element &e = d->elements.at(i);
3588
3589	switch (e.type) {
3590	case MoveToElement:
3591	case LineToElement:
3592	if (e.x > maxx) maxx = e.x;
3593	else if (e.x < minx) minx = e.x;
3594	if (e.y > maxy) maxy = e.y;
3595	else if (e.y < miny) miny = e.y;
3596	break;
3597	case CurveToElement:
3598	{
3599	QBezier b = QBezier::fromPoints(p1: d->elements.at(i: i-1),
3600	p2: e,
3601	p3: d->elements.at(i: i+1),
3602	p4: d->elements.at(i: i+2));
3603	QRectF r = qt_painterpath_bezier_extrema(b);
3604	qreal right = r.right();
3605	qreal bottom = r.bottom();
3606	if (r.x() < minx) minx = r.x();
3607	if (right > maxx) maxx = right;
3608	if (r.y() < miny) miny = r.y();
3609	if (bottom > maxy) maxy = bottom;
3610	i += 2;
3611	}
3612	break;
3613	default:
3614	break;
3615	}
3616	}
3617	d->bounds = QRectF(minx, miny, maxx - minx, maxy - miny);
3618	}
3619
3620
3621	void QPainterPath::computeControlPointRect() const
3622	{
3623	QPainterPathPrivate *d = d_func();
3624	d->dirtyControlBounds = false;
3625	if (!d_ptr) {
3626	d->controlBounds = QRect();
3627	return;
3628	}
3629
3630	qreal minx, maxx, miny, maxy;
3631	minx = maxx = d->elements.at(i: 0).x;
3632	miny = maxy = d->elements.at(i: 0).y;
3633	for (int i=1; i<d->elements.size(); ++i) {
3634	const Element &e = d->elements.at(i);
3635	if (e.x > maxx) maxx = e.x;
3636	else if (e.x < minx) minx = e.x;
3637	if (e.y > maxy) maxy = e.y;
3638	else if (e.y < miny) miny = e.y;
3639	}
3640	d->controlBounds = QRectF(minx, miny, maxx - minx, maxy - miny);
3641	}
3642
3643	void QPainterPathPrivate::computeRunLengths()
3644	{
3645	Q_ASSERT(!elements.isEmpty());
3646
3647	m_runLengths.clear();
3648	const int numElems = elements.size();
3649	m_runLengths.reserve(asize: numElems);
3650
3651	QPointF runPt = elements[0];
3652	qreal runLen = 0.0;
3653	for (int i = 0; i < numElems; i++) {
3654	QPainterPath::Element e = elements[i];
3655	switch (e.type) {
3656	case QPainterPath::LineToElement:
3657	runLen += QLineF(runPt, e).length();
3658	runPt = e;
3659	break;
3660	case QPainterPath::CurveToElement: {
3661	Q_ASSERT(i < numElems - 2);
3662	QPainterPath::Element ee = elements[i + 2];
3663	runLen += QBezier::fromPoints(p1: runPt, p2: e, p3: elements[i + 1], p4: ee).length();
3664	runPt = ee;
3665	break;
3666	}
3667	case QPainterPath::MoveToElement:
3668	runPt = e;
3669	break;
3670	case QPainterPath::CurveToDataElement:
3671	break;
3672	}
3673	m_runLengths.append(t: runLen);
3674	}
3675	Q_ASSERT(m_runLengths.size() == elements.size());
3676
3677	dirtyRunLengths = false;
3678	}
3679
3680	#ifndef QT_NO_DEBUG_STREAM
3681	QDebug operator<<(QDebug s, const QPainterPath &p)
3682	{
3683	QDebugStateSaver saver(s);
3684	s.nospace() << "QPainterPath: Element count=" << p.elementCount() << Qt::endl;
3685	const char *types[] = {"MoveTo", "LineTo", "CurveTo", "CurveToData"};
3686	for (int i=0; i<p.elementCount(); ++i) {
3687	s.nospace() << " -> " << types[p.elementAt(i).type] << "(x=" << p.elementAt(i).x << ", y=" << p.elementAt(i).y << ')' << Qt::endl;
3688	}
3689	return s;
3690	}
3691	#endif
3692
3693	QT_END_NAMESPACE
3694