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