qpathclipper.cpp

Absolute File Name:/home/qt/qt5_coco/qt5/qtbase/src/gui/painting/qpathclipper.cpp
Source codeSwitch to Preprocessed file
LineSourceCount
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 "qpathclipper_p.h"-
41-
42#include <private/qbezier_p.h>-
43#include <private/qdatabuffer_p.h>-
44#include <private/qnumeric_p.h>-
45#include <qmath.h>-
46#include <algorithm>-
47-
48/**-
49 The algorithm is as follows:-
50-
51 1. Find all intersections between the two paths (including self-intersections),-
52 and build a winged edge structure of non-intersecting parts.-
53 2. While there are more unhandled edges:-
54 3. Pick a y-coordinate from an unhandled edge.-
55 4. Intersect the horizontal line at y-coordinate with all edges.-
56 5. Traverse intersections left to right deciding whether each subpath should be added or not.-
57 6. If the subpath should be added, traverse the winged-edge structure and add the edges to-
58 a separate winged edge structure.-
59 7. Mark all edges in subpaths crossing the horizontal line as handled.-
60 8. (Optional) Simplify the resulting winged edge structure by merging shared edges.-
61 9. Convert the resulting winged edge structure to a painter path.-
62 */-
63-
64#include <qdebug.h>-
65-
66QT_BEGIN_NAMESPACE-
67-
68static inline bool fuzzyIsNull(qreal d)-
69{-
70 if (sizeof(qreal) == sizeof(double))
sizeof(qreal) ...sizeof(double)Description
TRUEnever evaluated
FALSEnever evaluated
0
71 return qAbs(d) <= 1e-12;
never executed: return qAbs(d) <= 1e-12;
0
72 else-
73 return qAbs(d) <= 1e-5f;
never executed: return qAbs(d) <= 1e-5f;
0
74}-
75-
76static inline bool comparePoints(const QPointF &a, const QPointF &b)-
77{-
78 return fuzzyIsNull(a.x() - b.x())
never executed: return fuzzyIsNull(a.x() - b.x()) && fuzzyIsNull(a.y() - b.y());
0
79 && fuzzyIsNull(a.y() - b.y());
never executed: return fuzzyIsNull(a.x() - b.x()) && fuzzyIsNull(a.y() - b.y());
0
80}-
81-
82//#define QDEBUG_CLIPPER-
83static qreal dot(const QPointF &a, const QPointF &b)-
84{-
85 return a.x() * b.x() + a.y() * b.y();
never executed: return a.x() * b.x() + a.y() * b.y();
0
86}-
87-
88static void normalize(double &x, double &y)-
89{-
90 double reciprocal = 1 / qSqrt(x * x + y * y);-
91 x *= reciprocal;-
92 y *= reciprocal;-
93}
never executed: end of block
0
94-
95struct QIntersection-
96{-
97 qreal alphaA;-
98 qreal alphaB;-
99-
100 QPointF pos;-
101};-
102-
103class QIntersectionFinder-
104{-
105public:-
106 void produceIntersections(QPathSegments &segments);-
107 bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const;-
108-
109private:-
110 bool linesIntersect(const QLineF &a, const QLineF &b) const;-
111};-
112-
113bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const-
114{-
115 const QPointF p1 = a.p1();-
116 const QPointF p2 = a.p2();-
117-
118 const QPointF q1 = b.p1();-
119 const QPointF q2 = b.p2();-
120-
121 if (comparePoints(p1, p2) || comparePoints(q1, q2))
comparePoints(p1, p2)Description
TRUEnever evaluated
FALSEnever evaluated
comparePoints(q1, q2)Description
TRUEnever evaluated
FALSEnever evaluated
0
122 return false;
never executed: return false;
0
123-
124 const bool p1_equals_q1 = comparePoints(p1, q1);-
125 const bool p2_equals_q2 = comparePoints(p2, q2);-
126-
127 if (p1_equals_q1 && p2_equals_q2)
p1_equals_q1Description
TRUEnever evaluated
FALSEnever evaluated
p2_equals_q2Description
TRUEnever evaluated
FALSEnever evaluated
0
128 return true;
never executed: return true;
0
129-
130 const bool p1_equals_q2 = comparePoints(p1, q2);-
131 const bool p2_equals_q1 = comparePoints(p2, q1);-
132-
133 if (p1_equals_q2 && p2_equals_q1)
p1_equals_q2Description
TRUEnever evaluated
FALSEnever evaluated
p2_equals_q1Description
TRUEnever evaluated
FALSEnever evaluated
0
134 return true;
never executed: return true;
0
135-
136 const QPointF pDelta = p2 - p1;-
137 const QPointF qDelta = q2 - q1;-
138-
139 const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x();-
140-
141 if (qFuzzyIsNull(par)) {
qFuzzyIsNull(par)Description
TRUEnever evaluated
FALSEnever evaluated
0
142 const QPointF normal(-pDelta.y(), pDelta.x());-
143-
144 // coinciding?-
145 if (qFuzzyIsNull(dot(normal, q1 - p1))) {
qFuzzyIsNull(d...mal, q1 - p1))Description
TRUEnever evaluated
FALSEnever evaluated
0
146 const qreal dp = dot(pDelta, pDelta);-
147-
148 const qreal tq1 = dot(pDelta, q1 - p1);-
149 const qreal tq2 = dot(pDelta, q2 - p1);-
150-
151 if ((tq1 > 0 && tq1 < dp) || (tq2 > 0 && tq2 < dp))
tq1 > 0Description
TRUEnever evaluated
FALSEnever evaluated
tq1 < dpDescription
TRUEnever evaluated
FALSEnever evaluated
tq2 > 0Description
TRUEnever evaluated
FALSEnever evaluated
tq2 < dpDescription
TRUEnever evaluated
FALSEnever evaluated
0
152 return true;
never executed: return true;
0
153-
154 const qreal dq = dot(qDelta, qDelta);-
155-
156 const qreal tp1 = dot(qDelta, p1 - q1);-
157 const qreal tp2 = dot(qDelta, p2 - q1);-
158-
159 if ((tp1 > 0 && tp1 < dq) || (tp2 > 0 && tp2 < dq))
tp1 > 0Description
TRUEnever evaluated
FALSEnever evaluated
tp1 < dqDescription
TRUEnever evaluated
FALSEnever evaluated
tp2 > 0Description
TRUEnever evaluated
FALSEnever evaluated
tp2 < dqDescription
TRUEnever evaluated
FALSEnever evaluated
0
160 return true;
never executed: return true;
0
161 }
never executed: end of block
0
162-
163 return false;
never executed: return false;
0
164 }-
165-
166 const qreal invPar = 1 / par;-
167-
168 const qreal tp = (qDelta.y() * (q1.x() - p1.x()) --
169 qDelta.x() * (q1.y() - p1.y())) * invPar;-
170-
171 if (tp < 0 || tp > 1)
tp < 0Description
TRUEnever evaluated
FALSEnever evaluated
tp > 1Description
TRUEnever evaluated
FALSEnever evaluated
0
172 return false;
never executed: return false;
0
173-
174 const qreal tq = (pDelta.y() * (q1.x() - p1.x()) --
175 pDelta.x() * (q1.y() - p1.y())) * invPar;-
176-
177 return tq >= 0 && tq <= 1;
never executed: return tq >= 0 && tq <= 1;
0
178}-
179-
180bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const-
181{-
182 if (a.segments() == 0 || b.segments() == 0)
a.segments() == 0Description
TRUEnever evaluated
FALSEnever evaluated
b.segments() == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
183 return false;
never executed: return false;
0
184-
185 const QRectF &rb0 = b.elementBounds(0);-
186-
187 qreal minX = rb0.left();-
188 qreal minY = rb0.top();-
189 qreal maxX = rb0.right();-
190 qreal maxY = rb0.bottom();-
191-
192 for (int i = 1; i < b.segments(); ++i) {
i < b.segments()Description
TRUEnever evaluated
FALSEnever evaluated
0
193 const QRectF &r = b.elementBounds(i);-
194 minX = qMin(minX, r.left());-
195 minY = qMin(minY, r.top());-
196 maxX = qMax(maxX, r.right());-
197 maxY = qMax(maxY, r.bottom());-
198 }
never executed: end of block
0
199-
200 QRectF rb(minX, minY, maxX - minX, maxY - minY);-
201-
202 for (int i = 0; i < a.segments(); ++i) {
i < a.segments()Description
TRUEnever evaluated
FALSEnever evaluated
0
203 const QRectF &r1 = a.elementBounds(i);-
204-
205 if (r1.left() > rb.right() || rb.left() > r1.right())
r1.left() > rb.right()Description
TRUEnever evaluated
FALSEnever evaluated
rb.left() > r1.right()Description
TRUEnever evaluated
FALSEnever evaluated
0
206 continue;
never executed: continue;
0
207 if (r1.top() > rb.bottom() || rb.top() > r1.bottom())
r1.top() > rb.bottom()Description
TRUEnever evaluated
FALSEnever evaluated
rb.top() > r1.bottom()Description
TRUEnever evaluated
FALSEnever evaluated
0
208 continue;
never executed: continue;
0
209-
210 for (int j = 0; j < b.segments(); ++j) {
j < b.segments()Description
TRUEnever evaluated
FALSEnever evaluated
0
211 const QRectF &r2 = b.elementBounds(j);-
212-
213 if (r1.left() > r2.right() || r2.left() > r1.right())
r1.left() > r2.right()Description
TRUEnever evaluated
FALSEnever evaluated
r2.left() > r1.right()Description
TRUEnever evaluated
FALSEnever evaluated
0
214 continue;
never executed: continue;
0
215 if (r1.top() > r2.bottom() || r2.top() > r1.bottom())
r1.top() > r2.bottom()Description
TRUEnever evaluated
FALSEnever evaluated
r2.top() > r1.bottom()Description
TRUEnever evaluated
FALSEnever evaluated
0
216 continue;
never executed: continue;
0
217-
218 if (linesIntersect(a.lineAt(i), b.lineAt(j)))
linesIntersect..., b.lineAt(j))Description
TRUEnever evaluated
FALSEnever evaluated
0
219 return true;
never executed: return true;
0
220 }
never executed: end of block
0
221 }
never executed: end of block
0
222-
223 return false;
never executed: return false;
0
224}-
225-
226namespace {-
227struct TreeNode-
228{-
229 qreal splitLeft;-
230 qreal splitRight;-
231 bool leaf;-
232-
233 int lowestLeftIndex;-
234 int lowestRightIndex;-
235-
236 union {-
237 struct {-
238 int first;-
239 int last;-
240 } interval;-
241 struct {-
242 int left;-
243 int right;-
244 } children;-
245 } index;-
246};-
247-
248struct RectF-
249{-
250 qreal x1;-
251 qreal y1;-
252 qreal x2;-
253 qreal y2;-
254};-
255-
256class SegmentTree-
257{-
258public:-
259 SegmentTree(QPathSegments &segments);-
260-
261 void produceIntersections(int segment);-
262-
263private:-
264 TreeNode buildTree(int first, int last, int depth, const RectF &bounds);-
265-
266 void produceIntersectionsLeaf(const TreeNode &node, int segment);-
267 void produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis);-
268 void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections);-
269-
270 QPathSegments &m_segments;-
271 QVector<int> m_index;-
272-
273 RectF m_bounds;-
274-
275 QVector<TreeNode> m_tree;-
276 QDataBuffer<QIntersection> m_intersections;-
277};-
278-
279SegmentTree::SegmentTree(QPathSegments &segments)-
280 : m_segments(segments),-
281 m_intersections(0)-
282{-
283 m_bounds.x1 = qt_inf();-
284 m_bounds.y1 = qt_inf();-
285 m_bounds.x2 = -qt_inf();-
286 m_bounds.y2 = -qt_inf();-
287-
288 m_index.resize(m_segments.segments());-
289-
290 for (int i = 0; i < m_index.size(); ++i) {
i < m_index.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
291 m_index[i] = i;-
292-
293 const QRectF &segmentBounds = m_segments.elementBounds(i);-
294-
295 if (segmentBounds.left() < m_bounds.x1)
segmentBounds.... < m_bounds.x1Description
TRUEnever evaluated
FALSEnever evaluated
0
296 m_bounds.x1 = segmentBounds.left();
never executed: m_bounds.x1 = segmentBounds.left();
0
297 if (segmentBounds.top() < m_bounds.y1)
segmentBounds.... < m_bounds.y1Description
TRUEnever evaluated
FALSEnever evaluated
0
298 m_bounds.y1 = segmentBounds.top();
never executed: m_bounds.y1 = segmentBounds.top();
0
299 if (segmentBounds.right() > m_bounds.x2)
segmentBounds.... > m_bounds.x2Description
TRUEnever evaluated
FALSEnever evaluated
0
300 m_bounds.x2 = segmentBounds.right();
never executed: m_bounds.x2 = segmentBounds.right();
0
301 if (segmentBounds.bottom() > m_bounds.y2)
segmentBounds.... > m_bounds.y2Description
TRUEnever evaluated
FALSEnever evaluated
0
302 m_bounds.y2 = segmentBounds.bottom();
never executed: m_bounds.y2 = segmentBounds.bottom();
0
303 }
never executed: end of block
0
304-
305 m_tree.resize(1);-
306-
307 TreeNode root = buildTree(0, m_index.size(), 0, m_bounds);-
308 m_tree[0] = root;-
309}
never executed: end of block
0
310-
311static inline qreal coordinate(const QPointF &pos, int axis)-
312{-
313 return axis == 0 ? pos.x() : pos.y();
never executed: return axis == 0 ? pos.x() : pos.y();
0
314}-
315-
316TreeNode SegmentTree::buildTree(int first, int last, int depth, const RectF &bounds)-
317{-
318 if (depth >= 24 || (last - first) <= 10) {
depth >= 24Description
TRUEnever evaluated
FALSEnever evaluated
(last - first) <= 10Description
TRUEnever evaluated
FALSEnever evaluated
0
319 TreeNode node;-
320 node.leaf = true;-
321 node.index.interval.first = first;-
322 node.index.interval.last = last;-
323-
324 return node;
never executed: return node;
0
325 }-
326-
327 int splitAxis = (depth & 1);-
328-
329 TreeNode node;-
330 node.leaf = false;-
331-
332 qreal split = 0.5f * ((&bounds.x1)[splitAxis] + (&bounds.x2)[splitAxis]);-
333-
334 node.splitLeft = (&bounds.x1)[splitAxis];-
335 node.splitRight = (&bounds.x2)[splitAxis];-
336-
337 node.lowestLeftIndex = INT_MAX;-
338 node.lowestRightIndex = INT_MAX;-
339-
340 const int treeSize = m_tree.size();-
341-
342 node.index.children.left = treeSize;-
343 node.index.children.right = treeSize + 1;-
344-
345 m_tree.resize(treeSize + 2);-
346-
347 int l = first;-
348 int r = last - 1;-
349-
350 // partition into left and right sets-
351 while (l <= r) {
l <= rDescription
TRUEnever evaluated
FALSEnever evaluated
0
352 const int index = m_index.at(l);-
353 const QRectF &segmentBounds = m_segments.elementBounds(index);-
354-
355 qreal lowCoordinate = coordinate(segmentBounds.topLeft(), splitAxis);-
356-
357 if (coordinate(segmentBounds.center(), splitAxis) < split) {
coordinate(seg...tAxis) < splitDescription
TRUEnever evaluated
FALSEnever evaluated
0
358 qreal highCoordinate = coordinate(segmentBounds.bottomRight(), splitAxis);-
359 if (highCoordinate > node.splitLeft)
highCoordinate...node.splitLeftDescription
TRUEnever evaluated
FALSEnever evaluated
0
360 node.splitLeft = highCoordinate;
never executed: node.splitLeft = highCoordinate;
0
361 if (index < node.lowestLeftIndex)
index < node.lowestLeftIndexDescription
TRUEnever evaluated
FALSEnever evaluated
0
362 node.lowestLeftIndex = index;
never executed: node.lowestLeftIndex = index;
0
363 ++l;-
364 } else {
never executed: end of block
0
365 if (lowCoordinate < node.splitRight)
lowCoordinate ...ode.splitRightDescription
TRUEnever evaluated
FALSEnever evaluated
0
366 node.splitRight = lowCoordinate;
never executed: node.splitRight = lowCoordinate;
0
367 if (index < node.lowestRightIndex)
index < node.lowestRightIndexDescription
TRUEnever evaluated
FALSEnever evaluated
0
368 node.lowestRightIndex = index;
never executed: node.lowestRightIndex = index;
0
369 qSwap(m_index[l], m_index[r]);-
370 --r;-
371 }
never executed: end of block
0
372 }-
373-
374 RectF lbounds = bounds;-
375 (&lbounds.x2)[splitAxis] = node.splitLeft;-
376-
377 RectF rbounds = bounds;-
378 (&rbounds.x1)[splitAxis] = node.splitRight;-
379-
380 TreeNode left = buildTree(first, l, depth + 1, lbounds);-
381 m_tree[node.index.children.left] = left;-
382-
383 TreeNode right = buildTree(l, last, depth + 1, rbounds);-
384 m_tree[node.index.children.right] = right;-
385-
386 return node;
never executed: return node;
0
387}-
388-
389void SegmentTree::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections)-
390{-
391 const QPointF p1 = a.p1();-
392 const QPointF p2 = a.p2();-
393-
394 const QPointF q1 = b.p1();-
395 const QPointF q2 = b.p2();-
396-
397 if (comparePoints(p1, p2) || comparePoints(q1, q2))
comparePoints(p1, p2)Description
TRUEnever evaluated
FALSEnever evaluated
comparePoints(q1, q2)Description
TRUEnever evaluated
FALSEnever evaluated
0
398 return;
never executed: return;
0
399-
400 const bool p1_equals_q1 = comparePoints(p1, q1);-
401 const bool p2_equals_q2 = comparePoints(p2, q2);-
402-
403 if (p1_equals_q1 && p2_equals_q2)
p1_equals_q1Description
TRUEnever evaluated
FALSEnever evaluated
p2_equals_q2Description
TRUEnever evaluated
FALSEnever evaluated
0
404 return;
never executed: return;
0
405-
406 const bool p1_equals_q2 = comparePoints(p1, q2);-
407 const bool p2_equals_q1 = comparePoints(p2, q1);-
408-
409 if (p1_equals_q2 && p2_equals_q1)
p1_equals_q2Description
TRUEnever evaluated
FALSEnever evaluated
p2_equals_q1Description
TRUEnever evaluated
FALSEnever evaluated
0
410 return;
never executed: return;
0
411-
412 const QPointF pDelta = p2 - p1;-
413 const QPointF qDelta = q2 - q1;-
414-
415 const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x();-
416-
417 if (qFuzzyIsNull(par)) {
qFuzzyIsNull(par)Description
TRUEnever evaluated
FALSEnever evaluated
0
418 const QPointF normal(-pDelta.y(), pDelta.x());-
419-
420 // coinciding?-
421 if (qFuzzyIsNull(dot(normal, q1 - p1))) {
qFuzzyIsNull(d...mal, q1 - p1))Description
TRUEnever evaluated
FALSEnever evaluated
0
422 const qreal invDp = 1 / dot(pDelta, pDelta);-
423-
424 const qreal tq1 = dot(pDelta, q1 - p1) * invDp;-
425 const qreal tq2 = dot(pDelta, q2 - p1) * invDp;-
426-
427 if (tq1 > 0 && tq1 < 1) {
tq1 > 0Description
TRUEnever evaluated
FALSEnever evaluated
tq1 < 1Description
TRUEnever evaluated
FALSEnever evaluated
0
428 QIntersection intersection;-
429 intersection.alphaA = tq1;-
430 intersection.alphaB = 0;-
431 intersection.pos = q1;-
432 intersections.add(intersection);-
433 }
never executed: end of block
0
434-
435 if (tq2 > 0 && tq2 < 1) {
tq2 > 0Description
TRUEnever evaluated
FALSEnever evaluated
tq2 < 1Description
TRUEnever evaluated
FALSEnever evaluated
0
436 QIntersection intersection;-
437 intersection.alphaA = tq2;-
438 intersection.alphaB = 1;-
439 intersection.pos = q2;-
440 intersections.add(intersection);-
441 }
never executed: end of block
0
442-
443 const qreal invDq = 1 / dot(qDelta, qDelta);-
444-
445 const qreal tp1 = dot(qDelta, p1 - q1) * invDq;-
446 const qreal tp2 = dot(qDelta, p2 - q1) * invDq;-
447-
448 if (tp1 > 0 && tp1 < 1) {
tp1 > 0Description
TRUEnever evaluated
FALSEnever evaluated
tp1 < 1Description
TRUEnever evaluated
FALSEnever evaluated
0
449 QIntersection intersection;-
450 intersection.alphaA = 0;-
451 intersection.alphaB = tp1;-
452 intersection.pos = p1;-
453 intersections.add(intersection);-
454 }
never executed: end of block
0
455-
456 if (tp2 > 0 && tp2 < 1) {
tp2 > 0Description
TRUEnever evaluated
FALSEnever evaluated
tp2 < 1Description
TRUEnever evaluated
FALSEnever evaluated
0
457 QIntersection intersection;-
458 intersection.alphaA = 1;-
459 intersection.alphaB = tp2;-
460 intersection.pos = p2;-
461 intersections.add(intersection);-
462 }
never executed: end of block
0
463 }
never executed: end of block
0
464-
465 return;
never executed: return;
0
466 }-
467-
468 // if the lines are not parallel and share a common end point, then they-
469 // don't intersect-
470 if (p1_equals_q1 || p1_equals_q2 || p2_equals_q1 || p2_equals_q2)
p1_equals_q1Description
TRUEnever evaluated
FALSEnever evaluated
p1_equals_q2Description
TRUEnever evaluated
FALSEnever evaluated
p2_equals_q1Description
TRUEnever evaluated
FALSEnever evaluated
p2_equals_q2Description
TRUEnever evaluated
FALSEnever evaluated
0
471 return;
never executed: return;
0
472-
473-
474 const qreal tp = (qDelta.y() * (q1.x() - p1.x()) --
475 qDelta.x() * (q1.y() - p1.y())) / par;-
476 const qreal tq = (pDelta.y() * (q1.x() - p1.x()) --
477 pDelta.x() * (q1.y() - p1.y())) / par;-
478-
479 if (tp<0 || tp>1 || tq<0 || tq>1)
tp<0Description
TRUEnever evaluated
FALSEnever evaluated
tp>1Description
TRUEnever evaluated
FALSEnever evaluated
tq<0Description
TRUEnever evaluated
FALSEnever evaluated
tq>1Description
TRUEnever evaluated
FALSEnever evaluated
0
480 return;
never executed: return;
0
481-
482 const bool p_zero = qFuzzyIsNull(tp);-
483 const bool p_one = qFuzzyIsNull(tp - 1);-
484-
485 const bool q_zero = qFuzzyIsNull(tq);-
486 const bool q_one = qFuzzyIsNull(tq - 1);-
487-
488 if ((q_zero || q_one) && (p_zero || p_one))
q_zeroDescription
TRUEnever evaluated
FALSEnever evaluated
q_oneDescription
TRUEnever evaluated
FALSEnever evaluated
p_zeroDescription
TRUEnever evaluated
FALSEnever evaluated
p_oneDescription
TRUEnever evaluated
FALSEnever evaluated
0
489 return;
never executed: return;
0
490-
491 QPointF pt;-
492 if (p_zero) {
p_zeroDescription
TRUEnever evaluated
FALSEnever evaluated
0
493 pt = p1;-
494 } else if (p_one) {
never executed: end of block
p_oneDescription
TRUEnever evaluated
FALSEnever evaluated
0
495 pt = p2;-
496 } else if (q_zero) {
never executed: end of block
q_zeroDescription
TRUEnever evaluated
FALSEnever evaluated
0
497 pt = q1;-
498 } else if (q_one) {
never executed: end of block
q_oneDescription
TRUEnever evaluated
FALSEnever evaluated
0
499 pt = q2;-
500 } else {
never executed: end of block
0
501 pt = q1 + (q2 - q1) * tq;-
502 }
never executed: end of block
0
503-
504 QIntersection intersection;-
505 intersection.alphaA = tp;-
506 intersection.alphaB = tq;-
507 intersection.pos = pt;-
508 intersections.add(intersection);-
509}
never executed: end of block
0
510-
511void SegmentTree::produceIntersections(int segment)-
512{-
513 const QRectF &segmentBounds = m_segments.elementBounds(segment);-
514-
515 RectF sbounds;-
516 sbounds.x1 = segmentBounds.left();-
517 sbounds.y1 = segmentBounds.top();-
518 sbounds.x2 = segmentBounds.right();-
519 sbounds.y2 = segmentBounds.bottom();-
520-
521 produceIntersections(m_tree.at(0), segment, sbounds, m_bounds, 0);-
522}
never executed: end of block
0
523-
524void SegmentTree::produceIntersectionsLeaf(const TreeNode &node, int segment)-
525{-
526 const QRectF &r1 = m_segments.elementBounds(segment);-
527 const QLineF lineA = m_segments.lineAt(segment);-
528-
529 for (int i = node.index.interval.first; i < node.index.interval.last; ++i) {
i < node.index.interval.lastDescription
TRUEnever evaluated
FALSEnever evaluated
0
530 const int other = m_index.at(i);-
531 if (other >= segment)
other >= segmentDescription
TRUEnever evaluated
FALSEnever evaluated
0
532 continue;
never executed: continue;
0
533-
534 const QRectF &r2 = m_segments.elementBounds(other);-
535-
536 if (r1.left() > r2.right() || r2.left() > r1.right())
r1.left() > r2.right()Description
TRUEnever evaluated
FALSEnever evaluated
r2.left() > r1.right()Description
TRUEnever evaluated
FALSEnever evaluated
0
537 continue;
never executed: continue;
0
538 if (r1.top() > r2.bottom() || r2.top() > r1.bottom())
r1.top() > r2.bottom()Description
TRUEnever evaluated
FALSEnever evaluated
r2.top() > r1.bottom()Description
TRUEnever evaluated
FALSEnever evaluated
0
539 continue;
never executed: continue;
0
540-
541 m_intersections.reset();-
542-
543 const QLineF lineB = m_segments.lineAt(other);-
544-
545 intersectLines(lineA, lineB, m_intersections);-
546-
547 for (int k = 0; k < m_intersections.size(); ++k) {
k < m_intersections.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
548 QPathSegments::Intersection i_isect, j_isect;-
549 i_isect.t = m_intersections.at(k).alphaA;-
550 j_isect.t = m_intersections.at(k).alphaB;-
551-
552 i_isect.vertex = j_isect.vertex = m_segments.addPoint(m_intersections.at(k).pos);-
553-
554 i_isect.next = 0;-
555 j_isect.next = 0;-
556-
557 m_segments.addIntersection(segment, i_isect);-
558 m_segments.addIntersection(other, j_isect);-
559 }
never executed: end of block
0
560 }
never executed: end of block
0
561}
never executed: end of block
0
562-
563void SegmentTree::produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis)-
564{-
565 if (node.leaf) {
node.leafDescription
TRUEnever evaluated
FALSEnever evaluated
0
566 produceIntersectionsLeaf(node, segment);-
567 return;
never executed: return;
0
568 }-
569-
570 RectF lbounds = nodeBounds;-
571 (&lbounds.x2)[axis] = node.splitLeft;-
572-
573 RectF rbounds = nodeBounds;-
574 (&rbounds.x1)[axis] = node.splitRight;-
575-
576 if (segment > node.lowestLeftIndex && (&segmentBounds.x1)[axis] <= node.splitLeft)
segment > node.lowestLeftIndexDescription
TRUEnever evaluated
FALSEnever evaluated
(&segmentBound...node.splitLeftDescription
TRUEnever evaluated
FALSEnever evaluated
0
577 produceIntersections(m_tree.at(node.index.children.left), segment, segmentBounds, lbounds, !axis);
never executed: produceIntersections(m_tree.at(node.index.children.left), segment, segmentBounds, lbounds, !axis);
0
578-
579 if (segment > node.lowestRightIndex && (&segmentBounds.x2)[axis] >= node.splitRight)
segment > node...westRightIndexDescription
TRUEnever evaluated
FALSEnever evaluated
(&segmentBound...ode.splitRightDescription
TRUEnever evaluated
FALSEnever evaluated
0
580 produceIntersections(m_tree.at(node.index.children.right), segment, segmentBounds, rbounds, !axis);
never executed: produceIntersections(m_tree.at(node.index.children.right), segment, segmentBounds, rbounds, !axis);
0
581}
never executed: end of block
0
582-
583}-
584-
585void QIntersectionFinder::produceIntersections(QPathSegments &segments)-
586{-
587 SegmentTree tree(segments);-
588-
589 for (int i = 0; i < segments.segments(); ++i)
i < segments.segments()Description
TRUEnever evaluated
FALSEnever evaluated
0
590 tree.produceIntersections(i);
never executed: tree.produceIntersections(i);
0
591}
never executed: end of block
0
592-
593class QKdPointTree-
594{-
595public:-
596 enum Traversal {-
597 TraverseBoth,-
598 TraverseLeft,-
599 TraverseRight,-
600 TraverseNone-
601 };-
602-
603 struct Node {-
604 int point;-
605 int id;-
606-
607 Node *left;-
608 Node *right;-
609 };-
610-
611 QKdPointTree(const QPathSegments &segments)-
612 : m_segments(&segments)-
613 , m_nodes(m_segments->points())-
614 , m_id(0)-
615 {-
616 m_nodes.resize(m_segments->points());-
617-
618 for (int i = 0; i < m_nodes.size(); ++i) {
i < m_nodes.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
619 m_nodes.at(i).point = i;-
620 m_nodes.at(i).id = -1;-
621 }
never executed: end of block
0
622-
623 m_rootNode = build(0, m_nodes.size());-
624 }
never executed: end of block
0
625-
626 int build(int begin, int end, int depth = 0);-
627-
628 Node *rootNode()-
629 {-
630 return &m_nodes.at(m_rootNode);
never executed: return &m_nodes.at(m_rootNode);
0
631 }-
632-
633 inline int nextId()-
634 {-
635 return m_id++;
never executed: return m_id++;
0
636 }-
637-
638private:-
639 const QPathSegments *m_segments;-
640 QDataBuffer<Node> m_nodes;-
641-
642 int m_rootNode;-
643 int m_id;-
644};-
645-
646template <typename T>-
647void qTraverseKdPointTree(QKdPointTree::Node &node, T &t, int depth = 0)-
648{-
649 QKdPointTree::Traversal status = t(node, depth);-
650-
651 const bool traverseRight = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseRight);-
652 const bool traverseLeft = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseLeft);-
653-
654 if (traverseLeft && node.left)
traverseLeftDescription
TRUEnever evaluated
FALSEnever evaluated
node.leftDescription
TRUEnever evaluated
FALSEnever evaluated
0
655 QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.left, t, depth + 1);
never executed: ::qTraverseKdPointTree<T>(*node.left, t, depth + 1);
0
656-
657 if (traverseRight && node.right)
traverseRightDescription
TRUEnever evaluated
FALSEnever evaluated
node.rightDescription
TRUEnever evaluated
FALSEnever evaluated
0
658 QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.right, t, depth + 1);
never executed: ::qTraverseKdPointTree<T>(*node.right, t, depth + 1);
0
659}
never executed: end of block
0
660-
661static inline qreal component(const QPointF &point, unsigned int i)-
662{-
663 Q_ASSERT(i < 2);-
664 const qreal components[] = { point.x(), point.y() };-
665 return components[i];
never executed: return components[i];
0
666}-
667-
668int QKdPointTree::build(int begin, int end, int depth)-
669{-
670 Q_ASSERT(end > begin);-
671-
672 const qreal pivot = component(m_segments->pointAt(m_nodes.at(begin).point), depth & 1);-
673-
674 int first = begin + 1;-
675 int last = end - 1;-
676-
677 while (first <= last) {
first <= lastDescription
TRUEnever evaluated
FALSEnever evaluated
0
678 const qreal value = component(m_segments->pointAt(m_nodes.at(first).point), depth & 1);-
679-
680 if (value < pivot)
value < pivotDescription
TRUEnever evaluated
FALSEnever evaluated
0
681 ++first;
never executed: ++first;
0
682 else {-
683 qSwap(m_nodes.at(first), m_nodes.at(last));-
684 --last;-
685 }
never executed: end of block
0
686 }-
687-
688 qSwap(m_nodes.at(last), m_nodes.at(begin));-
689-
690 if (last > begin)
last > beginDescription
TRUEnever evaluated
FALSEnever evaluated
0
691 m_nodes.at(last).left = &m_nodes.at(build(begin, last, depth + 1));
never executed: m_nodes.at(last).left = &m_nodes.at(build(begin, last, depth + 1));
0
692 else-
693 m_nodes.at(last).left = 0;
never executed: m_nodes.at(last).left = 0;
0
694-
695 if (last + 1 < end)
last + 1 < endDescription
TRUEnever evaluated
FALSEnever evaluated
0
696 m_nodes.at(last).right = &m_nodes.at(build(last + 1, end, depth + 1));
never executed: m_nodes.at(last).right = &m_nodes.at(build(last + 1, end, depth + 1));
0
697 else-
698 m_nodes.at(last).right = 0;
never executed: m_nodes.at(last).right = 0;
0
699-
700 return last;
never executed: return last;
0
701}-
702-
703class QKdPointFinder-
704{-
705public:-
706 QKdPointFinder(int point, const QPathSegments &segments, QKdPointTree &tree)-
707 : m_result(-1)-
708 , m_segments(&segments)-
709 , m_tree(&tree)-
710 {-
711 pointComponents[0] = segments.pointAt(point).x();-
712 pointComponents[1] = segments.pointAt(point).y();-
713 }
never executed: end of block
0
714-
715 inline QKdPointTree::Traversal operator()(QKdPointTree::Node &node, int depth)-
716 {-
717 if (m_result != -1)
m_result != -1Description
TRUEnever evaluated
FALSEnever evaluated
0
718 return QKdPointTree::TraverseNone;
never executed: return QKdPointTree::TraverseNone;
0
719-
720 const QPointF &nodePoint = m_segments->pointAt(node.point);-
721-
722 const qreal pivotComponents[] = { nodePoint.x(), nodePoint.y() };-
723-
724 const qreal pivot = pivotComponents[depth & 1];-
725 const qreal value = pointComponents[depth & 1];-
726-
727 if (fuzzyIsNull(pivot - value)) {
fuzzyIsNull(pivot - value)Description
TRUEnever evaluated
FALSEnever evaluated
0
728 const qreal pivot2 = pivotComponents[(depth + 1) & 1];-
729 const qreal value2 = pointComponents[(depth + 1) & 1];-
730-
731 if (fuzzyIsNull(pivot2 - value2)) {
fuzzyIsNull(pivot2 - value2)Description
TRUEnever evaluated
FALSEnever evaluated
0
732 if (node.id < 0)
node.id < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
733 node.id = m_tree->nextId();
never executed: node.id = m_tree->nextId();
0
734-
735 m_result = node.id;-
736 return QKdPointTree::TraverseNone;
never executed: return QKdPointTree::TraverseNone;
0
737 } else-
738 return QKdPointTree::TraverseBoth;
never executed: return QKdPointTree::TraverseBoth;
0
739 } else if (value < pivot) {
value < pivotDescription
TRUEnever evaluated
FALSEnever evaluated
0
740 return QKdPointTree::TraverseLeft;
never executed: return QKdPointTree::TraverseLeft;
0
741 } else {-
742 return QKdPointTree::TraverseRight;
never executed: return QKdPointTree::TraverseRight;
0
743 }-
744 }-
745-
746 int result() const-
747 {-
748 return m_result;
never executed: return m_result;
0
749 }-
750-
751private:-
752 qreal pointComponents[2];-
753 int m_result;-
754 const QPathSegments *m_segments;-
755 QKdPointTree *m_tree;-
756};-
757-
758// merge all points that are within qFuzzyCompare range of each other-
759void QPathSegments::mergePoints()-
760{-
761 QKdPointTree tree(*this);-
762-
763 if (tree.rootNode()) {
tree.rootNode()Description
TRUEnever evaluated
FALSEnever evaluated
0
764 QDataBuffer<QPointF> mergedPoints(points());-
765 QDataBuffer<int> pointIndices(points());-
766-
767 for (int i = 0; i < points(); ++i) {
i < points()Description
TRUEnever evaluated
FALSEnever evaluated
0
768 QKdPointFinder finder(i, *this, tree);-
769 QT_PREPEND_NAMESPACE(qTraverseKdPointTree<QKdPointFinder>)(*tree.rootNode(), finder);-
770-
771 Q_ASSERT(finder.result() != -1);-
772-
773 if (finder.result() >= mergedPoints.size())
finder.result(...dPoints.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
774 mergedPoints << m_points.at(i);
never executed: mergedPoints << m_points.at(i);
0
775-
776 pointIndices << finder.result();-
777 }
never executed: end of block
0
778-
779 for (int i = 0; i < m_segments.size(); ++i) {
i < m_segments.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
780 m_segments.at(i).va = pointIndices.at(m_segments.at(i).va);-
781 m_segments.at(i).vb = pointIndices.at(m_segments.at(i).vb);-
782 }
never executed: end of block
0
783-
784 for (int i = 0; i < m_intersections.size(); ++i)
i < m_intersections.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
785 m_intersections.at(i).vertex = pointIndices.at(m_intersections.at(i).vertex);
never executed: m_intersections.at(i).vertex = pointIndices.at(m_intersections.at(i).vertex);
0
786-
787 m_points.swap(mergedPoints);-
788 }
never executed: end of block
0
789}
never executed: end of block
0
790-
791void QWingedEdge::intersectAndAdd()-
792{-
793 QIntersectionFinder finder;-
794 finder.produceIntersections(m_segments);-
795-
796 m_segments.mergePoints();-
797-
798 for (int i = 0; i < m_segments.points(); ++i)
i < m_segments.points()Description
TRUEnever evaluated
FALSEnever evaluated
0
799 addVertex(m_segments.pointAt(i));
never executed: addVertex(m_segments.pointAt(i));
0
800-
801 QDataBuffer<QPathSegments::Intersection> intersections(m_segments.segments());-
802 for (int i = 0; i < m_segments.segments(); ++i) {
i < m_segments.segments()Description
TRUEnever evaluated
FALSEnever evaluated
0
803 intersections.reset();-
804-
805 int pathId = m_segments.pathId(i);-
806-
807 const QPathSegments::Intersection *isect = m_segments.intersectionAt(i);-
808 while (isect) {
isectDescription
TRUEnever evaluated
FALSEnever evaluated
0
809 intersections << *isect;-
810-
811 if (isect->next) {
isect->nextDescription
TRUEnever evaluated
FALSEnever evaluated
0
812 isect += isect->next;-
813 } else {
never executed: end of block
0
814 isect = 0;-
815 }
never executed: end of block
0
816 }-
817-
818 std::sort(intersections.data(), intersections.data() + intersections.size());-
819-
820 int first = m_segments.segmentAt(i).va;-
821 int second = m_segments.segmentAt(i).vb;-
822-
823 int last = first;-
824 for (int j = 0; j < intersections.size(); ++j) {
j < intersections.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
825 const QPathSegments::Intersection &isect = intersections.at(j);-
826-
827 QPathEdge *ep = edge(addEdge(last, isect.vertex));-
828-
829 if (ep) {
epDescription
TRUEnever evaluated
FALSEnever evaluated
0
830 const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(isect.vertex).y() ? 1 : -1;
m_segments.poi...ct.vertex).y()Description
TRUEnever evaluated
FALSEnever evaluated
0
831 if (pathId == 0)
pathId == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
832 ep->windingA += dir;
never executed: ep->windingA += dir;
0
833 else-
834 ep->windingB += dir;
never executed: ep->windingB += dir;
0
835 }-
836-
837 last = isect.vertex;-
838 }
never executed: end of block
0
839-
840 QPathEdge *ep = edge(addEdge(last, second));-
841-
842 if (ep) {
epDescription
TRUEnever evaluated
FALSEnever evaluated
0
843 const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(second).y() ? 1 : -1;
m_segments.poi...At(second).y()Description
TRUEnever evaluated
FALSEnever evaluated
0
844 if (pathId == 0)
pathId == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
845 ep->windingA += dir;
never executed: ep->windingA += dir;
0
846 else-
847 ep->windingB += dir;
never executed: ep->windingB += dir;
0
848 }-
849 }
never executed: end of block
0
850}
never executed: end of block
0
851-
852QWingedEdge::QWingedEdge() :-
853 m_edges(0),-
854 m_vertices(0),-
855 m_segments(0)-
856{-
857}
never executed: end of block
0
858-
859QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip) :-
860 m_edges(subject.elementCount()),-
861 m_vertices(subject.elementCount()),-
862 m_segments(subject.elementCount())-
863{-
864 m_segments.setPath(subject);-
865 m_segments.addPath(clip);-
866-
867 intersectAndAdd();-
868}
never executed: end of block
0
869-
870QWingedEdge::TraversalStatus QWingedEdge::next(const QWingedEdge::TraversalStatus &status) const-
871{-
872 const QPathEdge *sp = edge(status.edge);-
873 Q_ASSERT(sp);-
874-
875 TraversalStatus result;-
876 result.edge = sp->next(status.traversal, status.direction);-
877 result.traversal = status.traversal;-
878 result.direction = status.direction;-
879-
880 const QPathEdge *rp = edge(result.edge);-
881 Q_ASSERT(rp);-
882-
883 if (sp->vertex(status.direction) == rp->vertex(status.direction))
sp->vertex(sta...tus.direction)Description
TRUEnever evaluated
FALSEnever evaluated
0
884 result.flip();
never executed: result.flip();
0
885-
886 return result;
never executed: return result;
0
887}-
888-
889static bool isLine(const QBezier &bezier)-
890{-
891 const bool equal_1_2 = comparePoints(bezier.pt1(), bezier.pt2());-
892 const bool equal_2_3 = comparePoints(bezier.pt2(), bezier.pt3());-
893 const bool equal_3_4 = comparePoints(bezier.pt3(), bezier.pt4());-
894-
895 // point?-
896 if (equal_1_2 && equal_2_3 && equal_3_4)
equal_1_2Description
TRUEnever evaluated
FALSEnever evaluated
equal_2_3Description
TRUEnever evaluated
FALSEnever evaluated
equal_3_4Description
TRUEnever evaluated
FALSEnever evaluated
0
897 return true;
never executed: return true;
0
898-
899 if (comparePoints(bezier.pt1(), bezier.pt4()))
comparePoints(... bezier.pt4())Description
TRUEnever evaluated
FALSEnever evaluated
0
900 return equal_1_2 || equal_3_4;
never executed: return equal_1_2 || equal_3_4;
0
901-
902 return (equal_1_2 && equal_3_4) || (equal_1_2 && equal_2_3) || (equal_2_3 && equal_3_4);
never executed: return (equal_1_2 && equal_3_4) || (equal_1_2 && equal_2_3) || (equal_2_3 && equal_3_4);
0
903}-
904-
905void QPathSegments::setPath(const QPainterPath &path)-
906{-
907 m_points.reset();-
908 m_intersections.reset();-
909 m_segments.reset();-
910-
911 m_pathId = 0;-
912-
913 addPath(path);-
914}
never executed: end of block
0
915-
916void QPathSegments::addPath(const QPainterPath &path)-
917{-
918 int firstSegment = m_segments.size();-
919-
920 bool hasMoveTo = false;-
921 int lastMoveTo = 0;-
922 int last = 0;-
923 for (int i = 0; i < path.elementCount(); ++i) {
i < path.elementCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
924 int current = m_points.size();-
925-
926 QPointF currentPoint;-
927 if (path.elementAt(i).type == QPainterPath::CurveToElement)
path.elementAt...CurveToElementDescription
TRUEnever evaluated
FALSEnever evaluated
0
928 currentPoint = path.elementAt(i+2);
never executed: currentPoint = path.elementAt(i+2);
0
929 else-
930 currentPoint = path.elementAt(i);
never executed: currentPoint = path.elementAt(i);
0
931-
932 if (i > 0 && comparePoints(m_points.at(lastMoveTo), currentPoint))
i > 0Description
TRUEnever evaluated
FALSEnever evaluated
comparePoints(... currentPoint)Description
TRUEnever evaluated
FALSEnever evaluated
0
933 current = lastMoveTo;
never executed: current = lastMoveTo;
0
934 else-
935 m_points << currentPoint;
never executed: m_points << currentPoint;
0
936-
937 switch (path.elementAt(i).type) {-
938 case QPainterPath::MoveToElement:
never executed: case QPainterPath::MoveToElement:
0
939 if (hasMoveTo && last != lastMoveTo && !comparePoints(m_points.at(last), m_points.at(lastMoveTo)))
hasMoveToDescription
TRUEnever evaluated
FALSEnever evaluated
last != lastMoveToDescription
TRUEnever evaluated
FALSEnever evaluated
!comparePoints...t(lastMoveTo))Description
TRUEnever evaluated
FALSEnever evaluated
0
940 m_segments << Segment(m_pathId, last, lastMoveTo);
never executed: m_segments << Segment(m_pathId, last, lastMoveTo);
0
941 hasMoveTo = true;-
942 last = lastMoveTo = current;-
943 break;
never executed: break;
0
944 case QPainterPath::LineToElement:
never executed: case QPainterPath::LineToElement:
0
945 m_segments << Segment(m_pathId, last, current);-
946 last = current;-
947 break;
never executed: break;
0
948 case QPainterPath::CurveToElement:
never executed: case QPainterPath::CurveToElement:
0
949 {-
950 QBezier bezier = QBezier::fromPoints(m_points.at(last), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2));-
951 if (isLine(bezier)) {
isLine(bezier)Description
TRUEnever evaluated
FALSEnever evaluated
0
952 m_segments << Segment(m_pathId, last, current);-
953 } else {
never executed: end of block
0
954 QRectF bounds = bezier.bounds();-
955-
956 // threshold based on similar algorithm as in qtriangulatingstroker.cpp-
957 int threshold = qMin<float>(64, qMax(bounds.width(), bounds.height()) * (2 * qreal(3.14) / 6));-
958-
959 if (threshold < 3) threshold = 3;
never executed: threshold = 3;
threshold < 3Description
TRUEnever evaluated
FALSEnever evaluated
0
960 qreal one_over_threshold_minus_1 = qreal(1) / (threshold - 1);-
961-
962 for (int t = 1; t < threshold - 1; ++t) {
t < threshold - 1Description
TRUEnever evaluated
FALSEnever evaluated
0
963 currentPoint = bezier.pointAt(t * one_over_threshold_minus_1);-
964-
965 int index = m_points.size();-
966 m_segments << Segment(m_pathId, last, index);-
967 last = index;-
968-
969 m_points << currentPoint;-
970 }
never executed: end of block
0
971-
972 m_segments << Segment(m_pathId, last, current);-
973 }
never executed: end of block
0
974 }-
975 last = current;-
976 i += 2;-
977 break;
never executed: break;
0
978 default:
never executed: default:
0
979 Q_ASSERT(false);-
980 break;
never executed: break;
0
981 }-
982 }-
983-
984 if (hasMoveTo && last != lastMoveTo && !comparePoints(m_points.at(last), m_points.at(lastMoveTo)))
hasMoveToDescription
TRUEnever evaluated
FALSEnever evaluated
last != lastMoveToDescription
TRUEnever evaluated
FALSEnever evaluated
!comparePoints...t(lastMoveTo))Description
TRUEnever evaluated
FALSEnever evaluated
0
985 m_segments << Segment(m_pathId, last, lastMoveTo);
never executed: m_segments << Segment(m_pathId, last, lastMoveTo);
0
986-
987 for (int i = firstSegment; i < m_segments.size(); ++i) {
i < m_segments.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
988 const QLineF line = lineAt(i);-
989-
990 qreal x1 = line.p1().x();-
991 qreal y1 = line.p1().y();-
992 qreal x2 = line.p2().x();-
993 qreal y2 = line.p2().y();-
994-
995 if (x2 < x1)
x2 < x1Description
TRUEnever evaluated
FALSEnever evaluated
0
996 qSwap(x1, x2);
never executed: qSwap(x1, x2);
0
997 if (y2 < y1)
y2 < y1Description
TRUEnever evaluated
FALSEnever evaluated
0
998 qSwap(y1, y2);
never executed: qSwap(y1, y2);
0
999-
1000 m_segments.at(i).bounds = QRectF(x1, y1, x2 - x1, y2 - y1);-
1001 }
never executed: end of block
0
1002-
1003 ++m_pathId;-
1004}
never executed: end of block
0
1005-
1006qreal QWingedEdge::delta(int vertex, int a, int b) const-
1007{-
1008 const QPathEdge *ap = edge(a);-
1009 const QPathEdge *bp = edge(b);-
1010-
1011 double a_angle = ap->angle;-
1012 double b_angle = bp->angle;-
1013-
1014 if (vertex == ap->second)
vertex == ap->secondDescription
TRUEnever evaluated
FALSEnever evaluated
0
1015 a_angle = ap->invAngle;
never executed: a_angle = ap->invAngle;
0
1016-
1017 if (vertex == bp->second)
vertex == bp->secondDescription
TRUEnever evaluated
FALSEnever evaluated
0
1018 b_angle = bp->invAngle;
never executed: b_angle = bp->invAngle;
0
1019-
1020 double result = b_angle - a_angle;-
1021-
1022 if (result >= 128.)
result >= 128.Description
TRUEnever evaluated
FALSEnever evaluated
0
1023 return result - 128.;
never executed: return result - 128.;
0
1024 else if (result < 0)
result < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
1025 return result + 128.;
never executed: return result + 128.;
0
1026 else-
1027 return result;
never executed: return result;
0
1028}-
1029-
1030QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const-
1031{-
1032 const QPathVertex *vp = vertex(vi);-
1033-
1034 Q_ASSERT(vp);-
1035 Q_ASSERT(ei >= 0);-
1036 Q_ASSERT(vp->edge >= 0);-
1037-
1038 int position = vp->edge;-
1039 qreal d = 128.;-
1040-
1041 TraversalStatus status;-
1042 status.direction = edge(vp->edge)->directionTo(vi);-
1043 status.traversal = QPathEdge::RightTraversal;-
1044 status.edge = vp->edge;-
1045-
1046#ifdef QDEBUG_CLIPPER-
1047 const QPathEdge *ep = edge(ei);-
1048 qDebug() << "Finding insert status for edge" << ei << "at vertex" << QPointF(*vp) << ", angles: " << ep->angle << ep->invAngle;-
1049#endif-
1050-
1051 do {-
1052 status = next(status);-
1053 status.flip();-
1054-
1055 Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi);-
1056 qreal d2 = delta(vi, ei, status.edge);-
1057-
1058#ifdef QDEBUG_CLIPPER-
1059 const QPathEdge *op = edge(status.edge);-
1060 qDebug() << "Delta to edge" << status.edge << d2 << ", angles: " << op->angle << op->invAngle;-
1061#endif-
1062-
1063 if (d2 < d) {
d2 < dDescription
TRUEnever evaluated
FALSEnever evaluated
0
1064 position = status.edge;-
1065 d = d2;-
1066 }
never executed: end of block
0
1067 } while (status.edge != vp->edge);
never executed: end of block
status.edge != vp->edgeDescription
TRUEnever evaluated
FALSEnever evaluated
0
1068-
1069 status.traversal = QPathEdge::LeftTraversal;-
1070 status.direction = QPathEdge::Forward;-
1071 status.edge = position;-
1072-
1073 if (edge(status.edge)->vertex(status.direction) != vi)
edge(status.ed...rection) != viDescription
TRUEnever evaluated
FALSEnever evaluated
0
1074 status.flip();
never executed: status.flip();
0
1075-
1076#ifdef QDEBUG_CLIPPER-
1077 qDebug() << "Inserting edge" << ei << "to" << (status.traversal == QPathEdge::LeftTraversal ? "left" : "right") << "of edge" << status.edge;-
1078#endif-
1079-
1080 Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi);-
1081-
1082 return status;
never executed: return status;
0
1083}-
1084-
1085void QWingedEdge::removeEdge(int ei)-
1086{-
1087 QPathEdge *ep = edge(ei);-
1088-
1089 TraversalStatus status;-
1090 status.direction = QPathEdge::Forward;-
1091 status.traversal = QPathEdge::RightTraversal;-
1092 status.edge = ei;-
1093-
1094 TraversalStatus forwardRight = next(status);-
1095 forwardRight.flipDirection();-
1096-
1097 status.traversal = QPathEdge::LeftTraversal;-
1098 TraversalStatus forwardLeft = next(status);-
1099 forwardLeft.flipDirection();-
1100-
1101 status.direction = QPathEdge::Backward;-
1102 TraversalStatus backwardLeft = next(status);-
1103 backwardLeft.flipDirection();-
1104-
1105 status.traversal = QPathEdge::RightTraversal;-
1106 TraversalStatus backwardRight = next(status);-
1107 backwardRight.flipDirection();-
1108-
1109 edge(forwardRight.edge)->setNext(forwardRight.traversal, forwardRight.direction, forwardLeft.edge);-
1110 edge(forwardLeft.edge)->setNext(forwardLeft.traversal, forwardLeft.direction, forwardRight.edge);-
1111-
1112 edge(backwardRight.edge)->setNext(backwardRight.traversal, backwardRight.direction, backwardLeft.edge);-
1113 edge(backwardLeft.edge)->setNext(backwardLeft.traversal, backwardLeft.direction, backwardRight.edge);-
1114-
1115 ep->setNext(QPathEdge::Forward, ei);-
1116 ep->setNext(QPathEdge::Backward, ei);-
1117-
1118 QPathVertex *a = vertex(ep->first);-
1119 QPathVertex *b = vertex(ep->second);-
1120-
1121 a->edge = backwardRight.edge;-
1122 b->edge = forwardRight.edge;-
1123}
never executed: end of block
0
1124-
1125static int commonEdge(const QWingedEdge &list, int a, int b)-
1126{-
1127 const QPathVertex *ap = list.vertex(a);-
1128 Q_ASSERT(ap);-
1129-
1130 const QPathVertex *bp = list.vertex(b);-
1131 Q_ASSERT(bp);-
1132-
1133 if (ap->edge < 0 || bp->edge < 0)
ap->edge < 0Description
TRUEnever evaluated
FALSEnever evaluated
bp->edge < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
1134 return -1;
never executed: return -1;
0
1135-
1136 QWingedEdge::TraversalStatus status;-
1137 status.edge = ap->edge;-
1138 status.direction = list.edge(status.edge)->directionTo(a);-
1139 status.traversal = QPathEdge::RightTraversal;-
1140-
1141 do {-
1142 const QPathEdge *ep = list.edge(status.edge);-
1143-
1144 if ((ep->first == a && ep->second == b)
ep->first == aDescription
TRUEnever evaluated
FALSEnever evaluated
ep->second == bDescription
TRUEnever evaluated
FALSEnever evaluated
0
1145 || (ep->first == b && ep->second == a))
ep->first == bDescription
TRUEnever evaluated
FALSEnever evaluated
ep->second == aDescription
TRUEnever evaluated
FALSEnever evaluated
0
1146 return status.edge;
never executed: return status.edge;
0
1147-
1148 status = list.next(status);-
1149 status.flip();-
1150 } while (status.edge != ap->edge);
never executed: end of block
status.edge != ap->edgeDescription
TRUEnever evaluated
FALSEnever evaluated
0
1151-
1152 return -1;
never executed: return -1;
0
1153}-
1154-
1155static double computeAngle(const QPointF &v)-
1156{-
1157#if 1-
1158 if (v.x() == 0) {
v.x() == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
1159 return v.y() <= 0 ? 0 : 64.;
never executed: return v.y() <= 0 ? 0 : 64.;
0
1160 } else if (v.y() == 0) {
v.y() == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
1161 return v.x() <= 0 ? 32. : 96.;
never executed: return v.x() <= 0 ? 32. : 96.;
0
1162 }-
1163-
1164 double vx = v.x();-
1165 double vy = v.y();-
1166 normalize(vx, vy);-
1167 if (vy < 0) {
vy < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
1168 if (vx < 0) { // 0 - 32
vx < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
1169 return -32. * vx;
never executed: return -32. * vx;
0
1170 } else { // 96 - 128-
1171 return 128. - 32. * vx;
never executed: return 128. - 32. * vx;
0
1172 }-
1173 } else { // 32 - 96-
1174 return 64. + 32. * vx;
never executed: return 64. + 32. * vx;
0
1175 }-
1176#else-
1177 // doesn't seem to be robust enough-
1178 return qAtan2(v.x(), v.y()) + Q_PI;-
1179#endif-
1180}-
1181-
1182int QWingedEdge::addEdge(const QPointF &a, const QPointF &b)-
1183{-
1184 int fi = insert(a);-
1185 int si = insert(b);-
1186-
1187 return addEdge(fi, si);
never executed: return addEdge(fi, si);
0
1188}-
1189-
1190int QWingedEdge::addEdge(int fi, int si)-
1191{-
1192 if (fi == si)
fi == siDescription
TRUEnever evaluated
FALSEnever evaluated
0
1193 return -1;
never executed: return -1;
0
1194-
1195 int common = commonEdge(*this, fi, si);-
1196 if (common >= 0)
common >= 0Description
TRUEnever evaluated
FALSEnever evaluated
0
1197 return common;
never executed: return common;
0
1198-
1199 m_edges << QPathEdge(fi, si);-
1200-
1201 int ei = m_edges.size() - 1;-
1202-
1203 QPathVertex *fp = vertex(fi);-
1204 QPathVertex *sp = vertex(si);-
1205-
1206 QPathEdge *ep = edge(ei);-
1207-
1208 const QPointF tangent = QPointF(*sp) - QPointF(*fp);-
1209 ep->angle = computeAngle(tangent);-
1210 ep->invAngle = ep->angle + 64;-
1211 if (ep->invAngle >= 128)
ep->invAngle >= 128Description
TRUEnever evaluated
FALSEnever evaluated
0
1212 ep->invAngle -= 128;
never executed: ep->invAngle -= 128;
0
1213-
1214 QPathVertex *vertices[2] = { fp, sp };-
1215 QPathEdge::Direction dirs[2] = { QPathEdge::Backward, QPathEdge::Forward };-
1216-
1217#ifdef QDEBUG_CLIPPER-
1218 printf("** Adding edge %d / vertices: %.07f %.07f, %.07f %.07f\n", ei, fp->x, fp->y, sp->x, sp->y);-
1219#endif-
1220-
1221 for (int i = 0; i < 2; ++i) {
i < 2Description
TRUEnever evaluated
FALSEnever evaluated
0
1222 QPathVertex *vp = vertices[i];-
1223 if (vp->edge < 0) {
vp->edge < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
1224 vp->edge = ei;-
1225 ep->setNext(dirs[i], ei);-
1226 } else {
never executed: end of block
0
1227 int vi = ep->vertex(dirs[i]);-
1228 Q_ASSERT(vertex(vi) == vertices[i]);-
1229-
1230 TraversalStatus os = findInsertStatus(vi, ei);-
1231 QPathEdge *op = edge(os.edge);-
1232-
1233 Q_ASSERT(vertex(op->vertex(os.direction)) == vertices[i]);-
1234-
1235 TraversalStatus ns = next(os);-
1236 ns.flipDirection();-
1237 QPathEdge *np = edge(ns.edge);-
1238-
1239 op->setNext(os.traversal, os.direction, ei);-
1240 np->setNext(ns.traversal, ns.direction, ei);-
1241-
1242 int oe = os.edge;-
1243 int ne = ns.edge;-
1244-
1245 os = next(os);-
1246 ns = next(ns);-
1247-
1248 os.flipDirection();-
1249 ns.flipDirection();-
1250-
1251 Q_ASSERT(os.edge == ei);-
1252 Q_ASSERT(ns.edge == ei);-
1253-
1254 ep->setNext(os.traversal, os.direction, oe);-
1255 ep->setNext(ns.traversal, ns.direction, ne);-
1256 }
never executed: end of block
0
1257 }-
1258-
1259 Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Forward) >= 0);-
1260 Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Backward) >= 0);-
1261 Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Forward) >= 0);-
1262 Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Backward) >= 0);-
1263-
1264 return ei;
never executed: return ei;
0
1265}-
1266-
1267int QWingedEdge::insert(const QPathVertex &vertex)-
1268{-
1269 if (!m_vertices.isEmpty()) {
!m_vertices.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
1270 const QPathVertex &last = m_vertices.last();-
1271 if (vertex.x == last.x && vertex.y == last.y)
vertex.x == last.xDescription
TRUEnever evaluated
FALSEnever evaluated
vertex.y == last.yDescription
TRUEnever evaluated
FALSEnever evaluated
0
1272 return m_vertices.size() - 1;
never executed: return m_vertices.size() - 1;
0
1273-
1274 for (int i = 0; i < m_vertices.size(); ++i) {
i < m_vertices.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
1275 const QPathVertex &v = m_vertices.at(i);-
1276 if (qFuzzyCompare(v.x, vertex.x) && qFuzzyCompare(v.y, vertex.y)) {
qFuzzyCompare(v.x, vertex.x)Description
TRUEnever evaluated
FALSEnever evaluated
qFuzzyCompare(v.y, vertex.y)Description
TRUEnever evaluated
FALSEnever evaluated
0
1277 return i;
never executed: return i;
0
1278 }-
1279 }
never executed: end of block
0
1280 }
never executed: end of block
0
1281-
1282 m_vertices << vertex;-
1283 return m_vertices.size() - 1;
never executed: return m_vertices.size() - 1;
0
1284}-
1285-
1286static void addLineTo(QPainterPath &path, const QPointF &point)-
1287{-
1288 const int elementCount = path.elementCount();-
1289 if (elementCount >= 2) {
elementCount >= 2Description
TRUEnever evaluated
FALSEnever evaluated
0
1290 const QPainterPath::Element &middle = path.elementAt(elementCount - 1);-
1291 if (middle.type == QPainterPath::LineToElement) {
middle.type ==...:LineToElementDescription
TRUEnever evaluated
FALSEnever evaluated
0
1292 const QPointF first = path.elementAt(elementCount - 2);-
1293 const QPointF d1 = point - first;-
1294 const QPointF d2 = middle - first;-
1295-
1296 const QPointF p(-d1.y(), d1.x());-
1297-
1298 if (qFuzzyIsNull(dot(p, d2))) {
qFuzzyIsNull(dot(p, d2))Description
TRUEnever evaluated
FALSEnever evaluated
0
1299 path.setElementPositionAt(elementCount - 1, point.x(), point.y());-
1300 return;
never executed: return;
0
1301 }-
1302 }
never executed: end of block
0
1303 }
never executed: end of block
0
1304-
1305 path.lineTo(point);-
1306}
never executed: end of block
0
1307-
1308static void add(QPainterPath &path, const QWingedEdge &list, int edge, QPathEdge::Traversal traversal)-
1309{-
1310 QWingedEdge::TraversalStatus status;-
1311 status.edge = edge;-
1312 status.traversal = traversal;-
1313 status.direction = QPathEdge::Forward;-
1314-
1315 path.moveTo(*list.vertex(list.edge(edge)->first));-
1316-
1317 do {-
1318 const QPathEdge *ep = list.edge(status.edge);-
1319-
1320 addLineTo(path, *list.vertex(ep->vertex(status.direction)));-
1321-
1322 if (status.traversal == QPathEdge::LeftTraversal)
status.travers...:LeftTraversalDescription
TRUEnever evaluated
FALSEnever evaluated
0
1323 ep->flag &= ~16;
never executed: ep->flag &= ~16;
0
1324 else-
1325 ep->flag &= ~32;
never executed: ep->flag &= ~32;
0
1326-
1327 status = list.next(status);-
1328 } while (status.edge != edge);
never executed: end of block
status.edge != edgeDescription
TRUEnever evaluated
FALSEnever evaluated
0
1329}
never executed: end of block
0
1330-
1331void QWingedEdge::simplify()-
1332{-
1333 for (int i = 0; i < edgeCount(); ++i) {
i < edgeCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
1334 const QPathEdge *ep = edge(i);-
1335-
1336 // if both sides are part of the inside then we can collapse the edge-
1337 int flag = 0x3 << 4;-
1338 if ((ep->flag & flag) == flag) {
(ep->flag & flag) == flagDescription
TRUEnever evaluated
FALSEnever evaluated
0
1339 removeEdge(i);-
1340-
1341 ep->flag &= ~flag;-
1342 }
never executed: end of block
0
1343 }
never executed: end of block
0
1344}
never executed: end of block
0
1345-
1346QPainterPath QWingedEdge::toPath() const-
1347{-
1348 QPainterPath path;-
1349-
1350 for (int i = 0; i < edgeCount(); ++i) {
i < edgeCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
1351 const QPathEdge *ep = edge(i);-
1352-
1353 if (ep->flag & 16) {
ep->flag & 16Description
TRUEnever evaluated
FALSEnever evaluated
0
1354 add(path, *this, i, QPathEdge::LeftTraversal);-
1355 }
never executed: end of block
0
1356-
1357 if (ep->flag & 32)
ep->flag & 32Description
TRUEnever evaluated
FALSEnever evaluated
0
1358 add(path, *this, i, QPathEdge::RightTraversal);
never executed: add(path, *this, i, QPathEdge::RightTraversal);
0
1359 }
never executed: end of block
0
1360-
1361 return path;
never executed: return path;
0
1362}-
1363-
1364bool QPathClipper::intersect()-
1365{-
1366 if (subjectPath == clipPath)
subjectPath == clipPathDescription
TRUEnever evaluated
FALSEnever evaluated
0
1367 return true;
never executed: return true;
0
1368-
1369 QRectF r1 = subjectPath.controlPointRect();-
1370 QRectF r2 = clipPath.controlPointRect();-
1371 if (qMax(r1.x(), r2.x()) > qMin(r1.x() + r1.width(), r2.x() + r2.width()) ||
qMax(r1.x(), r... + r2.width())Description
TRUEnever evaluated
FALSEnever evaluated
0
1372 qMax(r1.y(), r2.y()) > qMin(r1.y() + r1.height(), r2.y() + r2.height())) {
qMax(r1.y(), r...+ r2.height())Description
TRUEnever evaluated
FALSEnever evaluated
0
1373 // no way we could intersect-
1374 return false;
never executed: return false;
0
1375 }-
1376-
1377 bool subjectIsRect = pathToRect(subjectPath);-
1378 bool clipIsRect = pathToRect(clipPath);-
1379-
1380 if (subjectIsRect && clipIsRect)
subjectIsRectDescription
TRUEnever evaluated
FALSEnever evaluated
clipIsRectDescription
TRUEnever evaluated
FALSEnever evaluated
0
1381 return true;
never executed: return true;
0
1382 else if (subjectIsRect)
subjectIsRectDescription
TRUEnever evaluated
FALSEnever evaluated
0
1383 return clipPath.intersects(r1);
never executed: return clipPath.intersects(r1);
0
1384 else if (clipIsRect)
clipIsRectDescription
TRUEnever evaluated
FALSEnever evaluated
0
1385 return subjectPath.intersects(r2);
never executed: return subjectPath.intersects(r2);
0
1386-
1387 QPathSegments a(subjectPath.elementCount());-
1388 a.setPath(subjectPath);-
1389 QPathSegments b(clipPath.elementCount());-
1390 b.setPath(clipPath);-
1391-
1392 QIntersectionFinder finder;-
1393 if (finder.hasIntersections(a, b))
finder.hasIntersections(a, b)Description
TRUEnever evaluated
FALSEnever evaluated
0
1394 return true;
never executed: return true;
0
1395-
1396 for (int i = 0; i < clipPath.elementCount(); ++i) {
i < clipPath.elementCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
1397 if (clipPath.elementAt(i).type == QPainterPath::MoveToElement) {
clipPath.eleme...:MoveToElementDescription
TRUEnever evaluated
FALSEnever evaluated
0
1398 const QPointF point = clipPath.elementAt(i);-
1399 if (r1.contains(point) && subjectPath.contains(point))
r1.contains(point)Description
TRUEnever evaluated
FALSEnever evaluated
subjectPath.contains(point)Description
TRUEnever evaluated
FALSEnever evaluated
0
1400 return true;
never executed: return true;
0
1401 }
never executed: end of block
0
1402 }
never executed: end of block
0
1403-
1404 for (int i = 0; i < subjectPath.elementCount(); ++i) {
i < subjectPath.elementCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
1405 if (subjectPath.elementAt(i).type == QPainterPath::MoveToElement) {
subjectPath.el...:MoveToElementDescription
TRUEnever evaluated
FALSEnever evaluated
0
1406 const QPointF point = subjectPath.elementAt(i);-
1407 if (r2.contains(point) && clipPath.contains(point))
r2.contains(point)Description
TRUEnever evaluated
FALSEnever evaluated
clipPath.contains(point)Description
TRUEnever evaluated
FALSEnever evaluated
0
1408 return true;
never executed: return true;
0
1409 }
never executed: end of block
0
1410 }
never executed: end of block
0
1411-
1412 return false;
never executed: return false;
0
1413}-
1414-
1415bool QPathClipper::contains()-
1416{-
1417 if (subjectPath == clipPath)
subjectPath == clipPathDescription
TRUEnever evaluated
FALSEnever evaluated
0
1418 return false;
never executed: return false;
0
1419-
1420 QRectF r1 = subjectPath.controlPointRect();-
1421 QRectF r2 = clipPath.controlPointRect();-
1422 if (qMax(r1.x(), r2.x()) > qMin(r1.x() + r1.width(), r2.x() + r2.width()) ||
qMax(r1.x(), r... + r2.width())Description
TRUEnever evaluated
FALSEnever evaluated
0
1423 qMax(r1.y(), r2.y()) > qMin(r1.y() + r1.height(), r2.y() + r2.height())) {
qMax(r1.y(), r...+ r2.height())Description
TRUEnever evaluated
FALSEnever evaluated
0
1424 // no intersection -> not contained-
1425 return false;
never executed: return false;
0
1426 }-
1427-
1428 bool clipIsRect = pathToRect(clipPath);-
1429 if (clipIsRect)
clipIsRectDescription
TRUEnever evaluated
FALSEnever evaluated
0
1430 return subjectPath.contains(r2);
never executed: return subjectPath.contains(r2);
0
1431-
1432 QPathSegments a(subjectPath.elementCount());-
1433 a.setPath(subjectPath);-
1434 QPathSegments b(clipPath.elementCount());-
1435 b.setPath(clipPath);-
1436-
1437 QIntersectionFinder finder;-
1438 if (finder.hasIntersections(a, b))
finder.hasIntersections(a, b)Description
TRUEnever evaluated
FALSEnever evaluated
0
1439 return false;
never executed: return false;
0
1440-
1441 for (int i = 0; i < clipPath.elementCount(); ++i) {
i < clipPath.elementCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
1442 if (clipPath.elementAt(i).type == QPainterPath::MoveToElement) {
clipPath.eleme...:MoveToElementDescription
TRUEnever evaluated
FALSEnever evaluated
0
1443 const QPointF point = clipPath.elementAt(i);-
1444 if (!r1.contains(point) || !subjectPath.contains(point))
!r1.contains(point)Description
TRUEnever evaluated
FALSEnever evaluated
!subjectPath.contains(point)Description
TRUEnever evaluated
FALSEnever evaluated
0
1445 return false;
never executed: return false;
0
1446 }
never executed: end of block
0
1447 }
never executed: end of block
0
1448-
1449 return true;
never executed: return true;
0
1450}-
1451-
1452QPathClipper::QPathClipper(const QPainterPath &subject,-
1453 const QPainterPath &clip)-
1454 : subjectPath(subject)-
1455 , clipPath(clip)-
1456{-
1457 aMask = subjectPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1;
subjectPath.fi...t::WindingFillDescription
TRUEnever evaluated
FALSEnever evaluated
0
1458 bMask = clipPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1;
clipPath.fillR...t::WindingFillDescription
TRUEnever evaluated
FALSEnever evaluated
0
1459}
never executed: end of block
0
1460-
1461template <typename Iterator, typename Equality>-
1462Iterator qRemoveDuplicates(Iterator begin, Iterator end, Equality eq)-
1463{-
1464 if (begin == end)
begin == endDescription
TRUEnever evaluated
FALSEnever evaluated
0
1465 return end;
never executed: return end;
0
1466-
1467 Iterator last = begin;-
1468 ++begin;-
1469 Iterator insert = begin;-
1470 for (Iterator it = begin; it != end; ++it) {
it != endDescription
TRUEnever evaluated
FALSEnever evaluated
0
1471 if (!eq(*it, *last)) {
!eq(*it, *last)Description
TRUEnever evaluated
FALSEnever evaluated
0
1472 *insert++ = *it;-
1473 last = it;-
1474 }
never executed: end of block
0
1475 }
never executed: end of block
0
1476-
1477 return insert;
never executed: return insert;
0
1478}-
1479-
1480static void clear(QWingedEdge& list, int edge, QPathEdge::Traversal traversal)-
1481{-
1482 QWingedEdge::TraversalStatus status;-
1483 status.edge = edge;-
1484 status.traversal = traversal;-
1485 status.direction = QPathEdge::Forward;-
1486-
1487 do {-
1488 if (status.traversal == QPathEdge::LeftTraversal)
status.travers...:LeftTraversalDescription
TRUEnever evaluated
FALSEnever evaluated
0
1489 list.edge(status.edge)->flag |= 1;
never executed: list.edge(status.edge)->flag |= 1;
0
1490 else-
1491 list.edge(status.edge)->flag |= 2;
never executed: list.edge(status.edge)->flag |= 2;
0
1492-
1493 status = list.next(status);-
1494 } while (status.edge != edge);
never executed: end of block
status.edge != edgeDescription
TRUEnever evaluated
FALSEnever evaluated
0
1495}
never executed: end of block
0
1496-
1497template <typename InputIterator>-
1498InputIterator qFuzzyFind(InputIterator first, InputIterator last, qreal val)-
1499{-
1500 while (first != last && !QT_PREPEND_NAMESPACE(qFuzzyCompare)(qreal(*first), qreal(val)))
first != lastDescription
TRUEnever evaluated
FALSEnever evaluated
!::qFuzzyCompa...), qreal(val))Description
TRUEnever evaluated
FALSEnever evaluated
0
1501 ++first;
never executed: ++first;
0
1502 return first;
never executed: return first;
0
1503}-
1504-
1505static bool fuzzyCompare(qreal a, qreal b)-
1506{-
1507 return qFuzzyCompare(a, b);
never executed: return qFuzzyCompare(a, b);
0
1508}-
1509-
1510bool QPathClipper::pathToRect(const QPainterPath &path, QRectF *rect)-
1511{-
1512 if (path.elementCount() != 5)
path.elementCount() != 5Description
TRUEnever evaluated
FALSEnever evaluated
0
1513 return false;
never executed: return false;
0
1514-
1515 const bool mightBeRect = path.elementAt(0).isMoveTo()
path.elementAt(0).isMoveTo()Description
TRUEnever evaluated
FALSEnever evaluated
0
1516 && path.elementAt(1).isLineTo()
path.elementAt(1).isLineTo()Description
TRUEnever evaluated
FALSEnever evaluated
0
1517 && path.elementAt(2).isLineTo()
path.elementAt(2).isLineTo()Description
TRUEnever evaluated
FALSEnever evaluated
0
1518 && path.elementAt(3).isLineTo()
path.elementAt(3).isLineTo()Description
TRUEnever evaluated
FALSEnever evaluated
0
1519 && path.elementAt(4).isLineTo();
path.elementAt(4).isLineTo()Description
TRUEnever evaluated
FALSEnever evaluated
0
1520-
1521 if (!mightBeRect)
!mightBeRectDescription
TRUEnever evaluated
FALSEnever evaluated
0
1522 return false;
never executed: return false;
0
1523-
1524 const qreal x1 = path.elementAt(0).x;-
1525 const qreal y1 = path.elementAt(0).y;-
1526-
1527 const qreal x2 = path.elementAt(1).x;-
1528 const qreal y2 = path.elementAt(2).y;-
1529-
1530 if (path.elementAt(1).y != y1)
path.elementAt(1).y != y1Description
TRUEnever evaluated
FALSEnever evaluated
0
1531 return false;
never executed: return false;
0
1532-
1533 if (path.elementAt(2).x != x2)
path.elementAt(2).x != x2Description
TRUEnever evaluated
FALSEnever evaluated
0
1534 return false;
never executed: return false;
0
1535-
1536 if (path.elementAt(3).x != x1 || path.elementAt(3).y != y2)
path.elementAt(3).x != x1Description
TRUEnever evaluated
FALSEnever evaluated
path.elementAt(3).y != y2Description
TRUEnever evaluated
FALSEnever evaluated
0
1537 return false;
never executed: return false;
0
1538-
1539 if (path.elementAt(4).x != x1 || path.elementAt(4).y != y1)
path.elementAt(4).x != x1Description
TRUEnever evaluated
FALSEnever evaluated
path.elementAt(4).y != y1Description
TRUEnever evaluated
FALSEnever evaluated
0
1540 return false;
never executed: return false;
0
1541-
1542 if (rect)
rectDescription
TRUEnever evaluated
FALSEnever evaluated
0
1543 rect->setCoords(x1, y1, x2, y2);
never executed: rect->setCoords(x1, y1, x2, y2);
0
1544-
1545 return true;
never executed: return true;
0
1546}-
1547-
1548-
1549QPainterPath QPathClipper::clip(Operation operation)-
1550{-
1551 op = operation;-
1552-
1553 if (op != Simplify) {
op != SimplifyDescription
TRUEnever evaluated
FALSEnever evaluated
0
1554 if (subjectPath == clipPath)
subjectPath == clipPathDescription
TRUEnever evaluated
FALSEnever evaluated
0
1555 return op == BoolSub ? QPainterPath() : subjectPath;
never executed: return op == BoolSub ? QPainterPath() : subjectPath;
0
1556-
1557 bool subjectIsRect = pathToRect(subjectPath, 0);-
1558 bool clipIsRect = pathToRect(clipPath, 0);-
1559-
1560 const QRectF clipBounds = clipPath.boundingRect();-
1561 const QRectF subjectBounds = subjectPath.boundingRect();-
1562-
1563 if (!clipBounds.intersects(subjectBounds)) {
!clipBounds.in...subjectBounds)Description
TRUEnever evaluated
FALSEnever evaluated
0
1564 switch (op) {-
1565 case BoolSub:
never executed: case BoolSub:
0
1566 return subjectPath;
never executed: return subjectPath;
0
1567 case BoolAnd:
never executed: case BoolAnd:
0
1568 return QPainterPath();
never executed: return QPainterPath();
0
1569 case BoolOr: {
never executed: case BoolOr:
0
1570 QPainterPath result = subjectPath;-
1571 if (result.fillRule() == clipPath.fillRule()) {
result.fillRul...ath.fillRule()Description
TRUEnever evaluated
FALSEnever evaluated
0
1572 result.addPath(clipPath);-
1573 } else if (result.fillRule() == Qt::WindingFill) {
never executed: end of block
result.fillRul...t::WindingFillDescription
TRUEnever evaluated
FALSEnever evaluated
0
1574 result = result.simplified();-
1575 result.addPath(clipPath);-
1576 } else {
never executed: end of block
0
1577 result.addPath(clipPath.simplified());-
1578 }
never executed: end of block
0
1579 return result;
never executed: return result;
0
1580 }-
1581 default:
never executed: default:
0
1582 break;
never executed: break;
0
1583 }-
1584 }-
1585-
1586 if (clipBounds.contains(subjectBounds)) {
clipBounds.con...subjectBounds)Description
TRUEnever evaluated
FALSEnever evaluated
0
1587 if (clipIsRect) {
clipIsRectDescription
TRUEnever evaluated
FALSEnever evaluated
0
1588 switch (op) {-
1589 case BoolSub:
never executed: case BoolSub:
0
1590 return QPainterPath();
never executed: return QPainterPath();
0
1591 case BoolAnd:
never executed: case BoolAnd:
0
1592 return subjectPath;
never executed: return subjectPath;
0
1593 case BoolOr:
never executed: case BoolOr:
0
1594 return clipPath;
never executed: return clipPath;
0
1595 default:
never executed: default:
0
1596 break;
never executed: break;
0
1597 }-
1598 }-
1599 } else if (subjectBounds.contains(clipBounds)) {
never executed: end of block
subjectBounds....ns(clipBounds)Description
TRUEnever evaluated
FALSEnever evaluated
0
1600 if (subjectIsRect) {
subjectIsRectDescription
TRUEnever evaluated
FALSEnever evaluated
0
1601 switch (op) {-
1602 case BoolSub:
never executed: case BoolSub:
0
1603 if (clipPath.fillRule() == Qt::OddEvenFill) {
clipPath.fillR...t::OddEvenFillDescription
TRUEnever evaluated
FALSEnever evaluated
0
1604 QPainterPath result = clipPath;-
1605 result.addRect(subjectBounds);-
1606 return result;
never executed: return result;
0
1607 } else {-
1608 QPainterPath result = clipPath.simplified();-
1609 result.addRect(subjectBounds);-
1610 return result;
never executed: return result;
0
1611 }-
1612 case BoolAnd:
never executed: case BoolAnd:
0
1613 return clipPath;
never executed: return clipPath;
0
1614 case BoolOr:
never executed: case BoolOr:
0
1615 return subjectPath;
never executed: return subjectPath;
0
1616 default:
never executed: default:
0
1617 break;
never executed: break;
0
1618 }-
1619 }-
1620 }
never executed: end of block
0
1621-
1622 if (op == BoolAnd) {
op == BoolAndDescription
TRUEnever evaluated
FALSEnever evaluated
0
1623 if (subjectIsRect)
subjectIsRectDescription
TRUEnever evaluated
FALSEnever evaluated
0
1624 return intersect(clipPath, subjectBounds);
never executed: return intersect(clipPath, subjectBounds);
0
1625 else if (clipIsRect)
clipIsRectDescription
TRUEnever evaluated
FALSEnever evaluated
0
1626 return intersect(subjectPath, clipBounds);
never executed: return intersect(subjectPath, clipBounds);
0
1627 }
never executed: end of block
0
1628 }
never executed: end of block
0
1629-
1630 QWingedEdge list(subjectPath, clipPath);-
1631-
1632 doClip(list, ClipMode);-
1633-
1634 QPainterPath path = list.toPath();-
1635 return path;
never executed: return path;
0
1636}-
1637-
1638bool QPathClipper::doClip(QWingedEdge &list, ClipperMode mode)-
1639{-
1640 QVector<qreal> y_coords;-
1641 y_coords.reserve(list.vertexCount());-
1642 for (int i = 0; i < list.vertexCount(); ++i)
i < list.vertexCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
1643 y_coords << list.vertex(i)->y;
never executed: y_coords << list.vertex(i)->y;
0
1644-
1645 std::sort(y_coords.begin(), y_coords.end());-
1646 y_coords.resize(qRemoveDuplicates(y_coords.begin(), y_coords.end(), fuzzyCompare) - y_coords.begin());-
1647-
1648#ifdef QDEBUG_CLIPPER-
1649 printf("sorted y coords:\n");-
1650 for (int i = 0; i < y_coords.size(); ++i) {-
1651 printf("%.9f\n", y_coords.at(i));-
1652 }-
1653#endif-
1654-
1655 bool found;-
1656 do {-
1657 found = false;-
1658 int index = 0;-
1659 qreal maxHeight = 0;-
1660 for (int i = 0; i < list.edgeCount(); ++i) {
i < list.edgeCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
1661 QPathEdge *edge = list.edge(i);-
1662-
1663 // have both sides of this edge already been handled?-
1664 if ((edge->flag & 0x3) == 0x3)
(edge->flag & 0x3) == 0x3Description
TRUEnever evaluated
FALSEnever evaluated
0
1665 continue;
never executed: continue;
0
1666-
1667 QPathVertex *a = list.vertex(edge->first);-
1668 QPathVertex *b = list.vertex(edge->second);-
1669-
1670 if (qFuzzyCompare(a->y, b->y))
qFuzzyCompare(a->y, b->y)Description
TRUEnever evaluated
FALSEnever evaluated
0
1671 continue;
never executed: continue;
0
1672-
1673 found = true;-
1674-
1675 qreal height = qAbs(a->y - b->y);-
1676 if (height > maxHeight) {
height > maxHeightDescription
TRUEnever evaluated
FALSEnever evaluated
0
1677 index = i;-
1678 maxHeight = height;-
1679 }
never executed: end of block
0
1680 }
never executed: end of block
0
1681-
1682 if (found) {
foundDescription
TRUEnever evaluated
FALSEnever evaluated
0
1683 QPathEdge *edge = list.edge(index);-
1684-
1685 QPathVertex *a = list.vertex(edge->first);-
1686 QPathVertex *b = list.vertex(edge->second);-
1687-
1688 // FIXME: this can be optimized by using binary search-
1689 const int first = qFuzzyFind(y_coords.cbegin(), y_coords.cend(), qMin(a->y, b->y)) - y_coords.cbegin();-
1690 const int last = qFuzzyFind(y_coords.cbegin() + first, y_coords.cend(), qMax(a->y, b->y)) - y_coords.cbegin();-
1691-
1692 Q_ASSERT(first < y_coords.size() - 1);-
1693 Q_ASSERT(last < y_coords.size());-
1694-
1695 qreal biggestGap = y_coords.at(first + 1) - y_coords.at(first);-
1696 int bestIdx = first;-
1697 for (int i = first + 1; i < last; ++i) {
i < lastDescription
TRUEnever evaluated
FALSEnever evaluated
0
1698 qreal gap = y_coords.at(i + 1) - y_coords.at(i);-
1699-
1700 if (gap > biggestGap) {
gap > biggestGapDescription
TRUEnever evaluated
FALSEnever evaluated
0
1701 bestIdx = i;-
1702 biggestGap = gap;-
1703 }
never executed: end of block
0
1704 }
never executed: end of block
0
1705 const qreal bestY = 0.5 * (y_coords.at(bestIdx) + y_coords.at(bestIdx + 1));-
1706-
1707#ifdef QDEBUG_CLIPPER-
1708 printf("y: %.9f, gap: %.9f\n", bestY, biggestGap);-
1709#endif-
1710-
1711 if (handleCrossingEdges(list, bestY, mode) && mode == CheckMode)
handleCrossing..., bestY, mode)Description
TRUEnever evaluated
FALSEnever evaluated
mode == CheckModeDescription
TRUEnever evaluated
FALSEnever evaluated
0
1712 return true;
never executed: return true;
0
1713-
1714 edge->flag |= 0x3;-
1715 }
never executed: end of block
0
1716 } while (found);
never executed: end of block
foundDescription
TRUEnever evaluated
FALSEnever evaluated
0
1717-
1718 if (mode == ClipMode)
mode == ClipModeDescription
TRUEnever evaluated
FALSEnever evaluated
0
1719 list.simplify();
never executed: list.simplify();
0
1720-
1721 return false;
never executed: return false;
0
1722}-
1723-
1724static void traverse(QWingedEdge &list, int edge, QPathEdge::Traversal traversal)-
1725{-
1726 QWingedEdge::TraversalStatus status;-
1727 status.edge = edge;-
1728 status.traversal = traversal;-
1729 status.direction = QPathEdge::Forward;-
1730-
1731 do {-
1732 int flag = status.traversal == QPathEdge::LeftTraversal ? 1 : 2;
status.travers...:LeftTraversalDescription
TRUEnever evaluated
FALSEnever evaluated
0
1733-
1734 QPathEdge *ep = list.edge(status.edge);-
1735-
1736 ep->flag |= (flag | (flag << 4));-
1737-
1738#ifdef QDEBUG_CLIPPER-
1739 qDebug() << "traverse: adding edge " << status.edge << ", mask:" << (flag << 4) <<ep->flag;-
1740#endif-
1741-
1742 status = list.next(status);-
1743 } while (status.edge != edge);
never executed: end of block
status.edge != edgeDescription
TRUEnever evaluated
FALSEnever evaluated
0
1744}
never executed: end of block
0
1745-
1746struct QCrossingEdge-
1747{-
1748 int edge;-
1749 qreal x;-
1750-
1751 bool operator<(const QCrossingEdge &edge) const-
1752 {-
1753 return x < edge.x;
never executed: return x < edge.x;
0
1754 }-
1755};-
1756Q_DECLARE_TYPEINFO(QCrossingEdge, Q_PRIMITIVE_TYPE);-
1757-
1758static bool bool_op(bool a, bool b, QPathClipper::Operation op)-
1759{-
1760 switch (op) {-
1761 case QPathClipper::BoolAnd:
never executed: case QPathClipper::BoolAnd:
0
1762 return a && b;
never executed: return a && b;
0
1763 case QPathClipper::BoolOr: // fall-through
never executed: case QPathClipper::BoolOr:
0
1764 case QPathClipper::Simplify:
never executed: case QPathClipper::Simplify:
0
1765 return a || b;
never executed: return a || b;
0
1766 case QPathClipper::BoolSub:
never executed: case QPathClipper::BoolSub:
0
1767 return a && !b;
never executed: return a && !b;
0
1768 default:
never executed: default:
0
1769 Q_ASSERT(false);-
1770 return false;
never executed: return false;
0
1771 }-
1772}-
1773-
1774bool QWingedEdge::isInside(qreal x, qreal y) const-
1775{-
1776 int winding = 0;-
1777 for (int i = 0; i < edgeCount(); ++i) {
i < edgeCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
1778 const QPathEdge *ep = edge(i);-
1779-
1780 // left xor right-
1781 int w = ((ep->flag >> 4) ^ (ep->flag >> 5)) & 1;-
1782-
1783 if (!w)
!wDescription
TRUEnever evaluated
FALSEnever evaluated
0
1784 continue;
never executed: continue;
0
1785-
1786 QPointF a = *vertex(ep->first);-
1787 QPointF b = *vertex(ep->second);-
1788-
1789 if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) {
a.y() < yDescription
TRUEnever evaluated
FALSEnever evaluated
b.y() > yDescription
TRUEnever evaluated
FALSEnever evaluated
a.y() > yDescription
TRUEnever evaluated
FALSEnever evaluated
b.y() < yDescription
TRUEnever evaluated
FALSEnever evaluated
0
1790 qreal intersectionX = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y());-
1791-
1792 if (intersectionX > x)
intersectionX > xDescription
TRUEnever evaluated
FALSEnever evaluated
0
1793 winding += w;
never executed: winding += w;
0
1794 }
never executed: end of block
0
1795 }
never executed: end of block
0
1796-
1797 return winding & 1;
never executed: return winding & 1;
0
1798}-
1799-
1800static QVector<QCrossingEdge> findCrossings(const QWingedEdge &list, qreal y)-
1801{-
1802 QVector<QCrossingEdge> crossings;-
1803 for (int i = 0; i < list.edgeCount(); ++i) {
i < list.edgeCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
1804 const QPathEdge *edge = list.edge(i);-
1805 QPointF a = *list.vertex(edge->first);-
1806 QPointF b = *list.vertex(edge->second);-
1807-
1808 if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) {
a.y() < yDescription
TRUEnever evaluated
FALSEnever evaluated
b.y() > yDescription
TRUEnever evaluated
FALSEnever evaluated
a.y() > yDescription
TRUEnever evaluated
FALSEnever evaluated
b.y() < yDescription
TRUEnever evaluated
FALSEnever evaluated
0
1809 const qreal intersection = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y());-
1810 const QCrossingEdge edge = { i, intersection };-
1811 crossings << edge;-
1812 }
never executed: end of block
0
1813 }
never executed: end of block
0
1814 return crossings;
never executed: return crossings;
0
1815}-
1816-
1817bool QPathClipper::handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode)-
1818{-
1819 QVector<QCrossingEdge> crossings = findCrossings(list, y);-
1820-
1821 Q_ASSERT(!crossings.isEmpty());-
1822 std::sort(crossings.begin(), crossings.end());-
1823-
1824 int windingA = 0;-
1825 int windingB = 0;-
1826-
1827 int windingD = 0;-
1828-
1829#ifdef QDEBUG_CLIPPER-
1830 qDebug() << "crossings:" << crossings.size();-
1831#endif-
1832 for (int i = 0; i < crossings.size() - 1; ++i) {
i < crossings.size() - 1Description
TRUEnever evaluated
FALSEnever evaluated
0
1833 int ei = crossings.at(i).edge;-
1834 const QPathEdge *edge = list.edge(ei);-
1835-
1836 windingA += edge->windingA;-
1837 windingB += edge->windingB;-
1838-
1839 const bool hasLeft = (edge->flag >> 4) & 1;-
1840 const bool hasRight = (edge->flag >> 4) & 2;-
1841-
1842 windingD += hasLeft ^ hasRight;-
1843-
1844 const bool inA = (windingA & aMask) != 0;-
1845 const bool inB = (windingB & bMask) != 0;-
1846 const bool inD = (windingD & 0x1) != 0;-
1847-
1848 const bool inside = bool_op(inA, inB, op);-
1849 const bool add = inD ^ inside;-
1850-
1851#ifdef QDEBUG_CLIPPER-
1852 printf("y %f, x %f, inA: %d, inB: %d, inD: %d, inside: %d, flag: %x, bezier: %p, edge: %d\n", y, crossings.at(i).x, inA, inB, inD, inside, edge->flag, edge->bezier, ei);-
1853#endif-
1854-
1855 if (add) {
addDescription
TRUEnever evaluated
FALSEnever evaluated
0
1856 if (mode == CheckMode)
mode == CheckModeDescription
TRUEnever evaluated
FALSEnever evaluated
0
1857 return true;
never executed: return true;
0
1858-
1859 qreal y0 = list.vertex(edge->first)->y;-
1860 qreal y1 = list.vertex(edge->second)->y;-
1861-
1862 if (y0 < y1) {
y0 < y1Description
TRUEnever evaluated
FALSEnever evaluated
0
1863 if (!(edge->flag & 1))
!(edge->flag & 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
1864 traverse(list, ei, QPathEdge::LeftTraversal);
never executed: traverse(list, ei, QPathEdge::LeftTraversal);
0
1865-
1866 if (!(edge->flag & 2))
!(edge->flag & 2)Description
TRUEnever evaluated
FALSEnever evaluated
0
1867 clear(list, ei, QPathEdge::RightTraversal);
never executed: clear(list, ei, QPathEdge::RightTraversal);
0
1868 } else {
never executed: end of block
0
1869 if (!(edge->flag & 1))
!(edge->flag & 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
1870 clear(list, ei, QPathEdge::LeftTraversal);
never executed: clear(list, ei, QPathEdge::LeftTraversal);
0
1871-
1872 if (!(edge->flag & 2))
!(edge->flag & 2)Description
TRUEnever evaluated
FALSEnever evaluated
0
1873 traverse(list, ei, QPathEdge::RightTraversal);
never executed: traverse(list, ei, QPathEdge::RightTraversal);
0
1874 }
never executed: end of block
0
1875-
1876 ++windingD;-
1877 } else {
never executed: end of block
0
1878 if (!(edge->flag & 1))
!(edge->flag & 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
1879 clear(list, ei, QPathEdge::LeftTraversal);
never executed: clear(list, ei, QPathEdge::LeftTraversal);
0
1880-
1881 if (!(edge->flag & 2))
!(edge->flag & 2)Description
TRUEnever evaluated
FALSEnever evaluated
0
1882 clear(list, ei, QPathEdge::RightTraversal);
never executed: clear(list, ei, QPathEdge::RightTraversal);
0
1883 }
never executed: end of block
0
1884 }-
1885-
1886 return false;
never executed: return false;
0
1887}-
1888-
1889namespace {-
1890-
1891QVector<QPainterPath> toSubpaths(const QPainterPath &path)-
1892{-
1893-
1894 QVector<QPainterPath> subpaths;-
1895 if (path.isEmpty())
path.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
1896 return subpaths;
never executed: return subpaths;
0
1897-
1898 QPainterPath current;-
1899 for (int i = 0; i < path.elementCount(); ++i) {
i < path.elementCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
1900 const QPainterPath::Element &e = path.elementAt(i);-
1901 switch (e.type) {-
1902 case QPainterPath::MoveToElement:
never executed: case QPainterPath::MoveToElement:
0
1903 if (current.elementCount() > 1)
current.elementCount() > 1Description
TRUEnever evaluated
FALSEnever evaluated
0
1904 subpaths += current;
never executed: subpaths += current;
0
1905 current = QPainterPath();-
1906 current.moveTo(e);-
1907 break;
never executed: break;
0
1908 case QPainterPath::LineToElement:
never executed: case QPainterPath::LineToElement:
0
1909 current.lineTo(e);-
1910 break;
never executed: break;
0
1911 case QPainterPath::CurveToElement: {
never executed: case QPainterPath::CurveToElement:
0
1912 current.cubicTo(e, path.elementAt(i + 1), path.elementAt(i + 2));-
1913 i+=2;-
1914 break;
never executed: break;
0
1915 }-
1916 case QPainterPath::CurveToDataElement:
never executed: case QPainterPath::CurveToDataElement:
0
1917 Q_ASSERT(!"toSubpaths(), bad element type");-
1918 break;
never executed: break;
0
1919 }-
1920 }
never executed: end of block
0
1921-
1922 if (current.elementCount() > 1)
current.elementCount() > 1Description
TRUEnever evaluated
FALSEnever evaluated
0
1923 subpaths << current;
never executed: subpaths << current;
0
1924-
1925 return subpaths;
never executed: return subpaths;
0
1926}-
1927-
1928enum Edge-
1929{-
1930 Left, Top, Right, Bottom-
1931};-
1932-
1933static bool isVertical(Edge edge)-
1934{-
1935 return edge == Left || edge == Right;
never executed: return edge == Left || edge == Right;
0
1936}-
1937-
1938template <Edge edge>-
1939bool compare(const QPointF &p, qreal t)-
1940{-
1941 switch (edge)-
1942 {-
1943 case Left:
never executed: case Left:
0
1944 return p.x() < t;
never executed: return p.x() < t;
0
1945 case Right:
never executed: case Right:
0
1946 return p.x() > t;
never executed: return p.x() > t;
0
1947 case Top:
never executed: case Top:
0
1948 return p.y() < t;
never executed: return p.y() < t;
0
1949 default:
never executed: default:
0
1950 return p.y() > t;
never executed: return p.y() > t;
0
1951 }-
1952}-
1953-
1954template <Edge edge>-
1955QPointF intersectLine(const QPointF &a, const QPointF &b, qreal t)-
1956{-
1957 QLineF line(a, b);-
1958 switch (edge) {-
1959 case Left: // fall-through
never executed: case Left:
0
1960 case Right:
never executed: case Right:
0
1961 return line.pointAt((t - a.x()) / (b.x() - a.x()));
never executed: return line.pointAt((t - a.x()) / (b.x() - a.x()));
0
1962 default:
never executed: default:
0
1963 return line.pointAt((t - a.y()) / (b.y() - a.y()));
never executed: return line.pointAt((t - a.y()) / (b.y() - a.y()));
0
1964 }-
1965}-
1966-
1967void addLine(QPainterPath &path, const QLineF &line)-
1968{-
1969 if (path.elementCount() > 0)
path.elementCount() > 0Description
TRUEnever evaluated
FALSEnever evaluated
0
1970 path.lineTo(line.p1());
never executed: path.lineTo(line.p1());
0
1971 else-
1972 path.moveTo(line.p1());
never executed: path.moveTo(line.p1());
0
1973-
1974 path.lineTo(line.p2());-
1975}
never executed: end of block
0
1976-
1977template <Edge edge>-
1978void clipLine(const QPointF &a, const QPointF &b, qreal t, QPainterPath &result)-
1979{-
1980 bool outA = compare<edge>(a, t);-
1981 bool outB = compare<edge>(b, t);-
1982 if (outA && outB)
outADescription
TRUEnever evaluated
FALSEnever evaluated
outBDescription
TRUEnever evaluated
FALSEnever evaluated
0
1983 return;
never executed: return;
0
1984-
1985 if (outA)
outADescription
TRUEnever evaluated
FALSEnever evaluated
0
1986 addLine(result, QLineF(intersectLine<edge>(a, b, t), b));
never executed: addLine(result, QLineF(intersectLine<edge>(a, b, t), b));
0
1987 else if(outB)
outBDescription
TRUEnever evaluated
FALSEnever evaluated
0
1988 addLine(result, QLineF(a, intersectLine<edge>(a, b, t)));
never executed: addLine(result, QLineF(a, intersectLine<edge>(a, b, t)));
0
1989 else-
1990 addLine(result, QLineF(a, b));
never executed: addLine(result, QLineF(a, b));
0
1991}-
1992-
1993void addBezier(QPainterPath &path, const QBezier &bezier)-
1994{-
1995 if (path.elementCount() > 0)
path.elementCount() > 0Description
TRUEnever evaluated
FALSEnever evaluated
0
1996 path.lineTo(bezier.pt1());
never executed: path.lineTo(bezier.pt1());
0
1997 else-
1998 path.moveTo(bezier.pt1());
never executed: path.moveTo(bezier.pt1());
0
1999-
2000 path.cubicTo(bezier.pt2(), bezier.pt3(), bezier.pt4());-
2001}
never executed: end of block
0
2002-
2003template <Edge edge>-
2004void clipBezier(const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, qreal t, QPainterPath &result)-
2005{-
2006 QBezier bezier = QBezier::fromPoints(a, b, c, d);-
2007-
2008 bool outA = compare<edge>(a, t);-
2009 bool outB = compare<edge>(b, t);-
2010 bool outC = compare<edge>(c, t);-
2011 bool outD = compare<edge>(d, t);-
2012-
2013 int outCount = int(outA) + int(outB) + int(outC) + int(outD);-
2014-
2015 if (outCount == 4)
outCount == 4Description
TRUEnever evaluated
FALSEnever evaluated
0
2016 return;
never executed: return;
0
2017-
2018 if (outCount == 0) {
outCount == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
2019 addBezier(result, bezier);-
2020 return;
never executed: return;
0
2021 }-
2022-
2023 QTransform flip = isVertical(edge) ? QTransform(0, 1, 1, 0, 0, 0) : QTransform();
isVertical(edge)Description
TRUEnever evaluated
FALSEnever evaluated
0
2024 QBezier unflipped = bezier;-
2025 QBezier flipped = bezier.mapBy(flip);-
2026-
2027 qreal t0 = 0, t1 = 1;-
2028 int stationary = flipped.stationaryYPoints(t0, t1);-
2029-
2030 qreal segments[4];-
2031 QPointF points[4];-
2032 points[0] = unflipped.pt1();-
2033 segments[0] = 0;-
2034-
2035 int segmentCount = 0;-
2036 if (stationary > 0) {
stationary > 0Description
TRUEnever evaluated
FALSEnever evaluated
0
2037 ++segmentCount;-
2038 segments[segmentCount] = t0;-
2039 points[segmentCount] = unflipped.pointAt(t0);-
2040 }
never executed: end of block
0
2041 if (stationary > 1) {
stationary > 1Description
TRUEnever evaluated
FALSEnever evaluated
0
2042 ++segmentCount;-
2043 segments[segmentCount] = t1;-
2044 points[segmentCount] = unflipped.pointAt(t1);-
2045 }
never executed: end of block
0
2046 ++segmentCount;-
2047 segments[segmentCount] = 1;-
2048 points[segmentCount] = unflipped.pt4();-
2049-
2050 qreal lastIntersection = 0;-
2051 for (int i = 0; i < segmentCount; ++i) {
i < segmentCountDescription
TRUEnever evaluated
FALSEnever evaluated
0
2052 outA = compare<edge>(points[i], t);-
2053 outB = compare<edge>(points[i+1], t);-
2054-
2055 if (outA != outB) {
outA != outBDescription
TRUEnever evaluated
FALSEnever evaluated
0
2056 qreal intersection = flipped.tForY(segments[i], segments[i+1], t);-
2057-
2058 if (outB)
outBDescription
TRUEnever evaluated
FALSEnever evaluated
0
2059 addBezier(result, unflipped.getSubRange(lastIntersection, intersection));
never executed: addBezier(result, unflipped.getSubRange(lastIntersection, intersection));
0
2060-
2061 lastIntersection = intersection;-
2062 }
never executed: end of block
0
2063 }
never executed: end of block
0
2064-
2065 if (!outB)
!outBDescription
TRUEnever evaluated
FALSEnever evaluated
0
2066 addBezier(result, unflipped.getSubRange(lastIntersection, 1));
never executed: addBezier(result, unflipped.getSubRange(lastIntersection, 1));
0
2067}
never executed: end of block
0
2068-
2069// clips a single subpath against a single edge-
2070template <Edge edge>-
2071QPainterPath clip(const QPainterPath &path, qreal t)-
2072{-
2073 QPainterPath result;-
2074 for (int i = 1; i < path.elementCount(); ++i) {
i < path.elementCount()Description
TRUEnever evaluated
FALSEnever evaluated
0
2075 const QPainterPath::Element &element = path.elementAt(i);-
2076 Q_ASSERT(!element.isMoveTo());-
2077 if (element.isLineTo()) {
element.isLineTo()Description
TRUEnever evaluated
FALSEnever evaluated
0
2078 clipLine<edge>(path.elementAt(i-1), path.elementAt(i), t, result);-
2079 } else {
never executed: end of block
0
2080 clipBezier<edge>(path.elementAt(i-1), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2), t, result);-
2081 i += 2;-
2082 }
never executed: end of block
0
2083 }-
2084-
2085 int last = path.elementCount() - 1;-
2086 if (QPointF(path.elementAt(last)) != QPointF(path.elementAt(0)))
QPointF(path.e....elementAt(0))Description
TRUEnever evaluated
FALSEnever evaluated
0
2087 clipLine<edge>(path.elementAt(last), path.elementAt(0), t, result);
never executed: clipLine<edge>(path.elementAt(last), path.elementAt(0), t, result);
0
2088-
2089 return result;
never executed: return result;
0
2090}-
2091-
2092QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect)-
2093{-
2094 QVector<QPainterPath> subpaths = toSubpaths(path);-
2095-
2096 QPainterPath result;-
2097 result.setFillRule(path.fillRule());-
2098 for (int i = 0; i < subpaths.size(); ++i) {
i < subpaths.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
2099 QPainterPath subPath = subpaths.at(i);-
2100 QRectF bounds = subPath.boundingRect();-
2101 if (bounds.intersects(rect)) {
bounds.intersects(rect)Description
TRUEnever evaluated
FALSEnever evaluated
0
2102 if (bounds.left() < rect.left())
bounds.left() < rect.left()Description
TRUEnever evaluated
FALSEnever evaluated
0
2103 subPath = clip<Left>(subPath, rect.left());
never executed: subPath = clip<Left>(subPath, rect.left());
0
2104 if (bounds.right() > rect.right())
bounds.right() > rect.right()Description
TRUEnever evaluated
FALSEnever evaluated
0
2105 subPath = clip<Right>(subPath, rect.right());
never executed: subPath = clip<Right>(subPath, rect.right());
0
2106-
2107 bounds = subPath.boundingRect();-
2108-
2109 if (bounds.top() < rect.top())
bounds.top() < rect.top()Description
TRUEnever evaluated
FALSEnever evaluated
0
2110 subPath = clip<Top>(subPath, rect.top());
never executed: subPath = clip<Top>(subPath, rect.top());
0
2111 if (bounds.bottom() > rect.bottom())
bounds.bottom(... rect.bottom()Description
TRUEnever evaluated
FALSEnever evaluated
0
2112 subPath = clip<Bottom>(subPath, rect.bottom());
never executed: subPath = clip<Bottom>(subPath, rect.bottom());
0
2113-
2114 if (subPath.elementCount() > 1)
subPath.elementCount() > 1Description
TRUEnever evaluated
FALSEnever evaluated
0
2115 result.addPath(subPath);
never executed: result.addPath(subPath);
0
2116 }
never executed: end of block
0
2117 }
never executed: end of block
0
2118 return result;
never executed: return result;
0
2119}-
2120-
2121}-
2122-
2123QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect)-
2124{-
2125 return intersectPath(path, rect);
never executed: return intersectPath(path, rect);
0
2126}-
2127-
2128QT_END_NAMESPACE-
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial 4.3.0-BETA-master-30-08-2018-4cb69e9