qpainterpath.cpp source code [Qt/src/gui/painting/qpainterpath.cpp]

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

Browse the source code of Qt/src/gui/painting/qpainterpath.cpp