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