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