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