opengl/qtriangulator.cpp

Source codeSwitch to Preprocessed file
LineSource CodeCoverage
1/**************************************************************************** -
2** -
3** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). -
4** Contact: http://www.qt-project.org/legal -
5** -
6** This file is part of the QtGui module of the Qt Toolkit. -
7** -
8** $QT_BEGIN_LICENSE:LGPL$ -
9** Commercial License Usage -
10** Licensees holding valid commercial Qt licenses may use this file in -
11** accordance with the commercial license agreement provided with the -
12** Software or, alternatively, in accordance with the terms contained in -
13** a written agreement between you and Digia. For licensing terms and -
14** conditions see http://qt.digia.com/licensing. For further information -
15** use the contact form at http://qt.digia.com/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 as published by the Free Software -
20** Foundation and appearing in the file LICENSE.LGPL included in the -
21** packaging of this file. Please review the following information to -
22** ensure the GNU Lesser General Public License version 2.1 requirements -
23** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. -
24** -
25** In addition, as a special exception, Digia gives you certain additional -
26** rights. These rights are described in the Digia Qt LGPL Exception -
27** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. -
28** -
29** GNU General Public License Usage -
30** Alternatively, this file may be used under the terms of the GNU -
31** General Public License version 3.0 as published by the Free Software -
32** Foundation and appearing in the file LICENSE.GPL included in the -
33** packaging of this file. Please review the following information to -
34** ensure the GNU General Public License version 3.0 requirements will be -
35** met: http://www.gnu.org/copyleft/gpl.html. -
36** -
37** -
38** $QT_END_LICENSE$ -
39** -
40****************************************************************************/ -
41 -
42#include "qtriangulator_p.h" -
43 -
44#include <QtGui/qevent.h> -
45#include <QtGui/qpainter.h> -
46#include <QtGui/qpainterpath.h> -
47#include <QtGui/private/qbezier_p.h> -
48#include <QtGui/private/qdatabuffer_p.h> -
49#include <QtCore/qbitarray.h> -
50#include <QtCore/qvarlengtharray.h> -
51#include <QtCore/qqueue.h> -
52#include <QtCore/qglobal.h> -
53#include <QtCore/qpoint.h> -
54#include <QtCore/qalgorithms.h> -
55 -
56#include <private/qopenglcontext_p.h> -
57#include <private/qopenglextensions_p.h> -
58#include <private/qrbtree_p.h> -
59 -
60#include <math.h> -
61 -
62QT_BEGIN_NAMESPACE -
63 -
64//#define Q_TRIANGULATOR_DEBUG -
65 -
66#define Q_FIXED_POINT_SCALE 32 -
67 -
68template<typename T> -
69struct QVertexSet -
70{ -
71 inline QVertexSet() { } -
72 inline QVertexSet(const QVertexSet<T> &other) : vertices(other.vertices), indices(other.indices) { }
never executed: }
0
73 QVertexSet<T> &operator = (const QVertexSet<T> &other) {vertices = other.vertices; indices = other.indices; return *this;}
never executed: return *this;
0
74 -
75 // The vertices of a triangle are given by: (x[i[n]], y[i[n]]), (x[j[n]], y[j[n]]), (x[k[n]], y[k[n]]), n = 0, 1, ... -
76 QVector<qreal> vertices; // [x[0], y[0], x[1], y[1], x[2], ...] -
77 QVector<T> indices; // [i[0], j[0], k[0], i[1], j[1], k[1], i[2], ...] -
78}; -
79 -
80//============================================================================// -
81// QFraction // -
82//============================================================================// -
83 -
84// Fraction must be in the range [0, 1) -
85struct QFraction -
86{ -
87 // Comparison operators must not be called on invalid fractions. -
88 inline bool operator < (const QFraction &other) const; -
89 inline bool operator == (const QFraction &other) const; -
90 inline bool operator != (const QFraction &other) const {return !(*this == other);}
never executed: return !(*this == other);
0
91 inline bool operator > (const QFraction &other) const {return other < *this;}
never executed: return other < *this;
0
92 inline bool operator >= (const QFraction &other) const {return !(*this < other);}
never executed: return !(*this < other);
0
93 inline bool operator <= (const QFraction &other) const {return !(*this > other);}
never executed: return !(*this > other);
0
94 -
95 inline bool isValid() const {return denominator != 0;}
never executed: return denominator != 0;
0
96 -
97 // numerator and denominator must not have common denominators. -
98 quint64 numerator, denominator; -
99}; -
100 -
101static inline quint64 gcd(quint64 x, quint64 y) -
102{ -
103 while (y != 0) {
never evaluated: y != 0
0
104 quint64 z = y;
never executed (the execution status of this line is deduced): quint64 z = y;
-
105 y = x % y;
never executed (the execution status of this line is deduced): y = x % y;
-
106 x = z;
never executed (the execution status of this line is deduced): x = z;
-
107 }
never executed: }
0
108 return x;
never executed: return x;
0
109} -
110 -
111static inline int compare(quint64 a, quint64 b) -
112{ -
113 return (a > b) - (a < b);
never executed: return (a > b) - (a < b);
0
114} -
115 -
116// Compare a/b with c/d. -
117// Return negative if less, 0 if equal, positive if greater. -
118// a < b, c < d -
119static int qCompareFractions(quint64 a, quint64 b, quint64 c, quint64 d) -
120{ -
121 const quint64 LIMIT = Q_UINT64_C(0x100000000);
never executed (the execution status of this line is deduced): const quint64 LIMIT = static_cast<unsigned long long>(0x100000000ULL);
-
122 for (;;) {
never executed (the execution status of this line is deduced): for (;;) {
-
123 // If the products 'ad' and 'bc' fit into 64 bits, they can be directly compared. -
124 if (b < LIMIT && d < LIMIT)
never evaluated: b < LIMIT
never evaluated: d < LIMIT
0
125 return compare(a * d, b * c);
never executed: return compare(a * d, b * c);
0
126 -
127 if (a == 0 || c == 0)
never evaluated: a == 0
never evaluated: c == 0
0
128 return compare(a, c);
never executed: return compare(a, c);
0
129 -
130 // a/b < c/d <=> d/c < b/a -
131 quint64 b_div_a = b / a;
never executed (the execution status of this line is deduced): quint64 b_div_a = b / a;
-
132 quint64 d_div_c = d / c;
never executed (the execution status of this line is deduced): quint64 d_div_c = d / c;
-
133 if (b_div_a != d_div_c)
never evaluated: b_div_a != d_div_c
0
134 return compare(d_div_c, b_div_a);
never executed: return compare(d_div_c, b_div_a);
0
135 -
136 // floor(d/c) == floor(b/a) -
137 // frac(d/c) < frac(b/a) ? -
138 // frac(x/y) = (x%y)/y -
139 d -= d_div_c * c; //d %= c;
never executed (the execution status of this line is deduced): d -= d_div_c * c;
-
140 b -= b_div_a * a; //b %= a;
never executed (the execution status of this line is deduced): b -= b_div_a * a;
-
141 qSwap(a, d);
never executed (the execution status of this line is deduced): qSwap(a, d);
-
142 qSwap(b, c);
never executed (the execution status of this line is deduced): qSwap(b, c);
-
143 }
never executed: }
0
144}
never executed: }
0
145 -
146// Fraction must be in the range [0, 1) -
147// Assume input is valid. -
148static QFraction qFraction(quint64 n, quint64 d) { -
149 QFraction result;
never executed (the execution status of this line is deduced): QFraction result;
-
150 if (n == 0) {
never evaluated: n == 0
0
151 result.numerator = 0;
never executed (the execution status of this line is deduced): result.numerator = 0;
-
152 result.denominator = 1;
never executed (the execution status of this line is deduced): result.denominator = 1;
-
153 } else {
never executed: }
0
154 quint64 g = gcd(n, d);
never executed (the execution status of this line is deduced): quint64 g = gcd(n, d);
-
155 result.numerator = n / g;
never executed (the execution status of this line is deduced): result.numerator = n / g;
-
156 result.denominator = d / g;
never executed (the execution status of this line is deduced): result.denominator = d / g;
-
157 }
never executed: }
0
158 return result;
never executed: return result;
0
159} -
160 -
161inline bool QFraction::operator < (const QFraction &other) const -
162{ -
163 return qCompareFractions(numerator, denominator, other.numerator, other.denominator) < 0;
never executed: return qCompareFractions(numerator, denominator, other.numerator, other.denominator) < 0;
0
164} -
165 -
166inline bool QFraction::operator == (const QFraction &other) const -
167{ -
168 return numerator == other.numerator && denominator == other.denominator;
never executed: return numerator == other.numerator && denominator == other.denominator;
0
169} -
170 -
171//============================================================================// -
172// QPodPoint // -
173//============================================================================// -
174 -
175struct QPodPoint -
176{ -
177 inline bool operator < (const QPodPoint &other) const -
178 { -
179 if (y != other.y)
never evaluated: y != other.y
0
180 return y < other.y;
never executed: return y < other.y;
0
181 return x < other.x;
never executed: return x < other.x;
0
182 } -
183 -
184 inline bool operator > (const QPodPoint &other) const {return other < *this;}
never executed: return other < *this;
0
185 inline bool operator <= (const QPodPoint &other) const {return !(*this > other);}
never executed: return !(*this > other);
0
186 inline bool operator >= (const QPodPoint &other) const {return !(*this < other);}
never executed: return !(*this < other);
0
187 inline bool operator == (const QPodPoint &other) const {return x == other.x && y == other.y;}
never executed: return x == other.x && y == other.y;
0
188 inline bool operator != (const QPodPoint &other) const {return x != other.x || y != other.y;}
never executed: return x != other.x || y != other.y;
0
189 -
190 inline QPodPoint &operator += (const QPodPoint &other) {x += other.x; y += other.y; return *this;}
never executed: return *this;
0
191 inline QPodPoint &operator -= (const QPodPoint &other) {x -= other.x; y -= other.y; return *this;}
never executed: return *this;
0
192 inline QPodPoint operator + (const QPodPoint &other) const {QPodPoint result = {x + other.x, y + other.y}; return result;}
never executed: return result;
0
193 inline QPodPoint operator - (const QPodPoint &other) const {QPodPoint result = {x - other.x, y - other.y}; return result;}
never executed: return result;
0
194 -
195 int x; -
196 int y; -
197}; -
198 -
199static inline qint64 qCross(const QPodPoint &u, const QPodPoint &v) -
200{ -
201 return qint64(u.x) * qint64(v.y) - qint64(u.y) * qint64(v.x);
never executed: return qint64(u.x) * qint64(v.y) - qint64(u.y) * qint64(v.x);
0
202} -
203 -
204static inline qint64 qDot(const QPodPoint &u, const QPodPoint &v) -
205{ -
206 return qint64(u.x) * qint64(v.x) + qint64(u.y) * qint64(v.y);
never executed: return qint64(u.x) * qint64(v.x) + qint64(u.y) * qint64(v.y);
0
207} -
208 -
209// Return positive value if 'p' is to the right of the line 'v1'->'v2', negative if left of the -
210// line and zero if exactly on the line. -
211// The returned value is the z-component of the qCross product between 'v2-v1' and 'p-v1', -
212// which is twice the signed area of the triangle 'p'->'v1'->'v2' (positive for CW order). -
213static inline qint64 qPointDistanceFromLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2) -
214{ -
215 return qCross(v2 - v1, p - v1);
never executed: return qCross(v2 - v1, p - v1);
0
216} -
217 -
218static inline bool qPointIsLeftOfLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2) -
219{ -
220 return QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(p, v1, v2) < 0;
never executed: return ::qPointDistanceFromLine(p, v1, v2) < 0;
0
221} -
222 -
223//============================================================================// -
224// QIntersectionPoint // -
225//============================================================================// -
226 -
227struct QIntersectionPoint -
228{ -
229 inline bool isValid() const {return xOffset.isValid() && yOffset.isValid();}
never executed: return xOffset.isValid() && yOffset.isValid();
0
230 QPodPoint round() const; -
231 inline bool isAccurate() const {return xOffset.numerator == 0 && yOffset.numerator == 0;}
never executed: return xOffset.numerator == 0 && yOffset.numerator == 0;
0
232 bool operator < (const QIntersectionPoint &other) const; -
233 bool operator == (const QIntersectionPoint &other) const; -
234 inline bool operator != (const QIntersectionPoint &other) const {return !(*this == other);}
never executed: return !(*this == other);
0
235 inline bool operator > (const QIntersectionPoint &other) const {return other < *this;}
never executed: return other < *this;
0
236 inline bool operator >= (const QIntersectionPoint &other) const {return !(*this < other);}
never executed: return !(*this < other);
0
237 inline bool operator <= (const QIntersectionPoint &other) const {return !(*this > other);}
never executed: return !(*this > other);
0
238 bool isOnLine(const QPodPoint &u, const QPodPoint &v) const; -
239 -
240 QPodPoint upperLeft; -
241 QFraction xOffset; -
242 QFraction yOffset; -
243}; -
244 -
245static inline QIntersectionPoint qIntersectionPoint(const QPodPoint &point) -
246{ -
247 // upperLeft = point, xOffset = 0/1, yOffset = 0/1. -
248 QIntersectionPoint p = {{point.x, point.y}, {0, 1}, {0, 1}};
never executed (the execution status of this line is deduced): QIntersectionPoint p = {{point.x, point.y}, {0, 1}, {0, 1}};
-
249 return p;
never executed: return p;
0
250} -
251 -
252static inline QIntersectionPoint qIntersectionPoint(int x, int y) -
253{ -
254 // upperLeft = (x, y), xOffset = 0/1, yOffset = 0/1. -
255 QIntersectionPoint p = {{x, y}, {0, 1}, {0, 1}};
never executed (the execution status of this line is deduced): QIntersectionPoint p = {{x, y}, {0, 1}, {0, 1}};
-
256 return p;
never executed: return p;
0
257} -
258 -
259static QIntersectionPoint qIntersectionPoint(const QPodPoint &u1, const QPodPoint &u2, const QPodPoint &v1, const QPodPoint &v2) -
260{ -
261 QIntersectionPoint result = {{0, 0}, {0, 0}, {0, 0}};
never executed (the execution status of this line is deduced): QIntersectionPoint result = {{0, 0}, {0, 0}, {0, 0}};
-
262 -
263 QPodPoint u = u2 - u1;
never executed (the execution status of this line is deduced): QPodPoint u = u2 - u1;
-
264 QPodPoint v = v2 - v1;
never executed (the execution status of this line is deduced): QPodPoint v = v2 - v1;
-
265 qint64 d1 = qCross(u, v1 - u1);
never executed (the execution status of this line is deduced): qint64 d1 = qCross(u, v1 - u1);
-
266 qint64 d2 = qCross(u, v2 - u1);
never executed (the execution status of this line is deduced): qint64 d2 = qCross(u, v2 - u1);
-
267 qint64 det = d2 - d1;
never executed (the execution status of this line is deduced): qint64 det = d2 - d1;
-
268 qint64 d3 = qCross(v, u1 - v1);
never executed (the execution status of this line is deduced): qint64 d3 = qCross(v, u1 - v1);
-
269 qint64 d4 = d3 - det; //qCross(v, u2 - v1);
never executed (the execution status of this line is deduced): qint64 d4 = d3 - det;
-
270 -
271 // Check that the math is correct. -
272 Q_ASSERT(d4 == qCross(v, u2 - v1));
never executed (the execution status of this line is deduced): qt_noop();
-
273 -
274 // The intersection point can be expressed as: -
275 // v1 - v * d1/det -
276 // v2 - v * d2/det -
277 // u1 + u * d3/det -
278 // u2 + u * d4/det -
279 -
280 // I'm only interested in lines that are crossing, so ignore parallel lines even if they overlap. -
281 if (det == 0)
never evaluated: det == 0
0
282 return result;
never executed: return result;
0
283 -
284 if (det < 0) {
never evaluated: det < 0
0
285 det = -det;
never executed (the execution status of this line is deduced): det = -det;
-
286 d1 = -d1;
never executed (the execution status of this line is deduced): d1 = -d1;
-
287 d2 = -d2;
never executed (the execution status of this line is deduced): d2 = -d2;
-
288 d3 = -d3;
never executed (the execution status of this line is deduced): d3 = -d3;
-
289 d4 = -d4;
never executed (the execution status of this line is deduced): d4 = -d4;
-
290 }
never executed: }
0
291 -
292 // I'm only interested in lines intersecting at their interior, not at their end points. -
293 // The lines intersect at their interior if and only if 'd1 < 0', 'd2 > 0', 'd3 < 0' and 'd4 > 0'. -
294 if (d1 >= 0 || d2 <= 0 || d3 <= 0 || d4 >= 0)
never evaluated: d1 >= 0
never evaluated: d2 <= 0
never evaluated: d3 <= 0
never evaluated: d4 >= 0
0
295 return result;
never executed: return result;
0
296 -
297 // Calculate the intersection point as follows: -
298 // v1 - v * d1/det | v1 <= v2 (component-wise) -
299 // v2 - v * d2/det | v2 < v1 (component-wise) -
300 -
301 // Assuming 21 bits per vector component. -
302 // TODO: Make code path for 31 bits per vector component. -
303 if (v.x >= 0) {
never evaluated: v.x >= 0
0
304 result.upperLeft.x = v1.x + (-v.x * d1) / det;
never executed (the execution status of this line is deduced): result.upperLeft.x = v1.x + (-v.x * d1) / det;
-
305 result.xOffset = qFraction(quint64(-v.x * d1) % quint64(det), quint64(det));
never executed (the execution status of this line is deduced): result.xOffset = qFraction(quint64(-v.x * d1) % quint64(det), quint64(det));
-
306 } else {
never executed: }
0
307 result.upperLeft.x = v2.x + (-v.x * d2) / det;
never executed (the execution status of this line is deduced): result.upperLeft.x = v2.x + (-v.x * d2) / det;
-
308 result.xOffset = qFraction(quint64(-v.x * d2) % quint64(det), quint64(det));
never executed (the execution status of this line is deduced): result.xOffset = qFraction(quint64(-v.x * d2) % quint64(det), quint64(det));
-
309 }
never executed: }
0
310 -
311 if (v.y >= 0) {
never evaluated: v.y >= 0
0
312 result.upperLeft.y = v1.y + (-v.y * d1) / det;
never executed (the execution status of this line is deduced): result.upperLeft.y = v1.y + (-v.y * d1) / det;
-
313 result.yOffset = qFraction(quint64(-v.y * d1) % quint64(det), quint64(det));
never executed (the execution status of this line is deduced): result.yOffset = qFraction(quint64(-v.y * d1) % quint64(det), quint64(det));
-
314 } else {
never executed: }
0
315 result.upperLeft.y = v2.y + (-v.y * d2) / det;
never executed (the execution status of this line is deduced): result.upperLeft.y = v2.y + (-v.y * d2) / det;
-
316 result.yOffset = qFraction(quint64(-v.y * d2) % quint64(det), quint64(det));
never executed (the execution status of this line is deduced): result.yOffset = qFraction(quint64(-v.y * d2) % quint64(det), quint64(det));
-
317 }
never executed: }
0
318 -
319 Q_ASSERT(result.xOffset.isValid());
never executed (the execution status of this line is deduced): qt_noop();
-
320 Q_ASSERT(result.yOffset.isValid());
never executed (the execution status of this line is deduced): qt_noop();
-
321 return result;
never executed: return result;
0
322} -
323 -
324QPodPoint QIntersectionPoint::round() const -
325{ -
326 QPodPoint result = upperLeft;
never executed (the execution status of this line is deduced): QPodPoint result = upperLeft;
-
327 if (2 * xOffset.numerator >= xOffset.denominator)
never evaluated: 2 * xOffset.numerator >= xOffset.denominator
0
328 ++result.x;
never executed: ++result.x;
0
329 if (2 * yOffset.numerator >= yOffset.denominator)
never evaluated: 2 * yOffset.numerator >= yOffset.denominator
0
330 ++result.y;
never executed: ++result.y;
0
331 return result;
never executed: return result;
0
332} -
333 -
334bool QIntersectionPoint::operator < (const QIntersectionPoint &other) const -
335{ -
336 if (upperLeft.y != other.upperLeft.y)
never evaluated: upperLeft.y != other.upperLeft.y
0
337 return upperLeft.y < other.upperLeft.y;
never executed: return upperLeft.y < other.upperLeft.y;
0
338 if (yOffset != other.yOffset)
never evaluated: yOffset != other.yOffset
0
339 return yOffset < other.yOffset;
never executed: return yOffset < other.yOffset;
0
340 if (upperLeft.x != other.upperLeft.x)
never evaluated: upperLeft.x != other.upperLeft.x
0
341 return upperLeft.x < other.upperLeft.x;
never executed: return upperLeft.x < other.upperLeft.x;
0
342 return xOffset < other.xOffset;
never executed: return xOffset < other.xOffset;
0
343} -
344 -
345bool QIntersectionPoint::operator == (const QIntersectionPoint &other) const -
346{ -
347 return upperLeft == other.upperLeft && xOffset == other.xOffset && yOffset == other.yOffset;
never executed: return upperLeft == other.upperLeft && xOffset == other.xOffset && yOffset == other.yOffset;
0
348} -
349 -
350// Returns true if this point is on the infinite line passing through 'u' and 'v'. -
351bool QIntersectionPoint::isOnLine(const QPodPoint &u, const QPodPoint &v) const -
352{ -
353 // TODO: Make code path for coordinates with more than 21 bits. -
354 const QPodPoint p = upperLeft - u;
never executed (the execution status of this line is deduced): const QPodPoint p = upperLeft - u;
-
355 const QPodPoint q = v - u;
never executed (the execution status of this line is deduced): const QPodPoint q = v - u;
-
356 bool isHorizontal = p.y == 0 && yOffset.numerator == 0;
never evaluated: p.y == 0
never evaluated: yOffset.numerator == 0
0
357 bool isVertical = p.x == 0 && xOffset.numerator == 0;
never evaluated: p.x == 0
never evaluated: xOffset.numerator == 0
0
358 if (isHorizontal && isVertical)
never evaluated: isHorizontal
never evaluated: isVertical
0
359 return true;
never executed: return true;
0
360 if (isHorizontal)
never evaluated: isHorizontal
0
361 return q.y == 0;
never executed: return q.y == 0;
0
362 if (q.y == 0)
never evaluated: q.y == 0
0
363 return false;
never executed: return false;
0
364 if (isVertical)
never evaluated: isVertical
0
365 return q.x == 0;
never executed: return q.x == 0;
0
366 if (q.x == 0)
never evaluated: q.x == 0
0
367 return false;
never executed: return false;
0
368 -
369 // At this point, 'p+offset' and 'q' cannot lie on the x or y axis. -
370 -
371 if (((q.x < 0) == (q.y < 0)) != ((p.x < 0) == (p.y < 0)))
never evaluated: ((q.x < 0) == (q.y < 0)) != ((p.x < 0) == (p.y < 0))
0
372 return false; // 'p + offset' and 'q' pass through different quadrants.
never executed: return false;
0
373 -
374 // Move all coordinates into the first quadrant. -
375 quint64 nx, ny;
never executed (the execution status of this line is deduced): quint64 nx, ny;
-
376 if (p.x < 0)
never evaluated: p.x < 0
0
377 nx = quint64(-p.x) * xOffset.denominator - xOffset.numerator;
never executed: nx = quint64(-p.x) * xOffset.denominator - xOffset.numerator;
0
378 else -
379 nx = quint64(p.x) * xOffset.denominator + xOffset.numerator;
never executed: nx = quint64(p.x) * xOffset.denominator + xOffset.numerator;
0
380 if (p.y < 0)
never evaluated: p.y < 0
0
381 ny = quint64(-p.y) * yOffset.denominator - yOffset.numerator;
never executed: ny = quint64(-p.y) * yOffset.denominator - yOffset.numerator;
0
382 else -
383 ny = quint64(p.y) * yOffset.denominator + yOffset.numerator;
never executed: ny = quint64(p.y) * yOffset.denominator + yOffset.numerator;
0
384 -
385 return qFraction(quint64(qAbs(q.x)) * xOffset.denominator, quint64(qAbs(q.y)) * yOffset.denominator) == qFraction(nx, ny);
never executed: return qFraction(quint64(qAbs(q.x)) * xOffset.denominator, quint64(qAbs(q.y)) * yOffset.denominator) == qFraction(nx, ny);
0
386} -
387 -
388//============================================================================// -
389// QMaxHeap // -
390//============================================================================// -
391 -
392template <class T> -
393class QMaxHeap -
394{ -
395public: -
396 QMaxHeap() : m_data(0) {}
never executed: }
0
397 inline int size() const {return m_data.size();}
never executed: return m_data.size();
0
398 inline bool empty() const {return m_data.isEmpty();}
never executed: return m_data.isEmpty();
0
399 inline bool isEmpty() const {return m_data.isEmpty();}
never executed: return m_data.isEmpty();
0
400 void push(const T &x); -
401 T pop(); -
402 inline const T &top() const {return m_data.first();}
never executed: return m_data.first();
0
403private: -
404 static inline int parent(int i) {return (i - 1) / 2;}
never executed: return (i - 1) / 2;
0
405 static inline int left(int i) {return 2 * i + 1;}
never executed: return 2 * i + 1;
0
406 static inline int right(int i) {return 2 * i + 2;}
never executed: return 2 * i + 2;
0
407 -
408 QDataBuffer<T> m_data; -
409}; -
410 -
411template <class T> -
412void QMaxHeap<T>::push(const T &x) -
413{ -
414 int current = m_data.size();
never executed (the execution status of this line is deduced): int current = m_data.size();
-
415 int parent = QMaxHeap::parent(current);
never executed (the execution status of this line is deduced): int parent = QMaxHeap::parent(current);
-
416 m_data.add(x);
never executed (the execution status of this line is deduced): m_data.add(x);
-
417 while (current != 0 && m_data.at(parent) < x) {
never evaluated: current != 0
never evaluated: m_data.at(parent) < x
0
418 m_data.at(current) = m_data.at(parent);
never executed (the execution status of this line is deduced): m_data.at(current) = m_data.at(parent);
-
419 current = parent;
never executed (the execution status of this line is deduced): current = parent;
-
420 parent = QMaxHeap::parent(current);
never executed (the execution status of this line is deduced): parent = QMaxHeap::parent(current);
-
421 }
never executed: }
0
422 m_data.at(current) = x;
never executed (the execution status of this line is deduced): m_data.at(current) = x;
-
423}
never executed: }
0
424 -
425template <class T> -
426T QMaxHeap<T>::pop() -
427{ -
428 T result = m_data.first();
never executed (the execution status of this line is deduced): T result = m_data.first();
-
429 T back = m_data.last();
never executed (the execution status of this line is deduced): T back = m_data.last();
-
430 m_data.pop_back();
never executed (the execution status of this line is deduced): m_data.pop_back();
-
431 if (!m_data.isEmpty()) {
never evaluated: !m_data.isEmpty()
0
432 int current = 0;
never executed (the execution status of this line is deduced): int current = 0;
-
433 for (;;) {
never executed (the execution status of this line is deduced): for (;;) {
-
434 int left = QMaxHeap::left(current);
never executed (the execution status of this line is deduced): int left = QMaxHeap::left(current);
-
435 int right = QMaxHeap::right(current);
never executed (the execution status of this line is deduced): int right = QMaxHeap::right(current);
-
436 if (left >= m_data.size())
never evaluated: left >= m_data.size()
0
437 break;
never executed: break;
0
438 int greater = left;
never executed (the execution status of this line is deduced): int greater = left;
-
439 if (right < m_data.size() && m_data.at(left) < m_data.at(right))
never evaluated: right < m_data.size()
never evaluated: m_data.at(left) < m_data.at(right)
0
440 greater = right;
never executed: greater = right;
0
441 if (m_data.at(greater) < back)
never evaluated: m_data.at(greater) < back
0
442 break;
never executed: break;
0
443 m_data.at(current) = m_data.at(greater);
never executed (the execution status of this line is deduced): m_data.at(current) = m_data.at(greater);
-
444 current = greater;
never executed (the execution status of this line is deduced): current = greater;
-
445 }
never executed: }
0
446 m_data.at(current) = back;
never executed (the execution status of this line is deduced): m_data.at(current) = back;
-
447 }
never executed: }
0
448 return result;
never executed: return result;
0
449} -
450 -
451//============================================================================// -
452// QInt64Hash // -
453//============================================================================// -
454 -
455// Copied from qhash.cpp -
456static const uchar prime_deltas[] = { -
457 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, -
458 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 -
459}; -
460 -
461// Copied from qhash.cpp -
462static inline int primeForNumBits(int numBits) -
463{ -
464 return (1 << numBits) + prime_deltas[numBits];
never executed: return (1 << numBits) + prime_deltas[numBits];
0
465} -
466 -
467static inline int primeForCount(int count) -
468{ -
469 int low = 0;
never executed (the execution status of this line is deduced): int low = 0;
-
470 int high = 32;
never executed (the execution status of this line is deduced): int high = 32;
-
471 for (int i = 0; i < 5; ++i) {
never evaluated: i < 5
0
472 int mid = (high + low) / 2;
never executed (the execution status of this line is deduced): int mid = (high + low) / 2;
-
473 if (count >= 1 << mid)
never evaluated: count >= 1 << mid
0
474 low = mid;
never executed: low = mid;
0
475 else -
476 high = mid;
never executed: high = mid;
0
477 } -
478 return primeForNumBits(high);
never executed: return primeForNumBits(high);
0
479} -
480 -
481// Hash set of quint64s. Elements cannot be removed without clearing the -
482// entire set. A value of -1 is used to mark unused entries. -
483class QInt64Set -
484{ -
485public: -
486 inline QInt64Set(int capacity = 64); -
487 inline ~QInt64Set() {if (m_array) delete[] m_array;}
never executed: delete[] m_array;
never executed: }
never evaluated: m_array
0
488 inline bool isValid() const {return m_array;}
never executed: return m_array;
0
489 void insert(quint64 key); -
490 bool contains(quint64 key) const; -
491 inline void clear(); -
492private: -
493 bool rehash(int capacity); -
494 -
495 static const quint64 UNUSED; -
496 -
497 quint64 *m_array; -
498 int m_capacity; -
499 int m_count; -
500}; -
501 -
502const quint64 QInt64Set::UNUSED = quint64(-1); -
503 -
504inline QInt64Set::QInt64Set(int capacity) -
505{ -
506 m_capacity = primeForCount(capacity);
never executed (the execution status of this line is deduced): m_capacity = primeForCount(capacity);
-
507 m_array = new quint64[m_capacity];
never executed (the execution status of this line is deduced): m_array = new quint64[m_capacity];
-
508 if (m_array)
never evaluated: m_array
0
509 clear();
never executed: clear();
0
510 else -
511 m_capacity = 0;
never executed: m_capacity = 0;
0
512} -
513 -
514bool QInt64Set::rehash(int capacity) -
515{ -
516 quint64 *oldArray = m_array;
never executed (the execution status of this line is deduced): quint64 *oldArray = m_array;
-
517 int oldCapacity = m_capacity;
never executed (the execution status of this line is deduced): int oldCapacity = m_capacity;
-
518 -
519 m_capacity = capacity;
never executed (the execution status of this line is deduced): m_capacity = capacity;
-
520 m_array = new quint64[m_capacity];
never executed (the execution status of this line is deduced): m_array = new quint64[m_capacity];
-
521 if (m_array) {
never evaluated: m_array
0
522 clear();
never executed (the execution status of this line is deduced): clear();
-
523 if (oldArray) {
never evaluated: oldArray
0
524 for (int i = 0; i < oldCapacity; ++i) {
never evaluated: i < oldCapacity
0
525 if (oldArray[i] != UNUSED)
never evaluated: oldArray[i] != UNUSED
0
526 insert(oldArray[i]);
never executed: insert(oldArray[i]);
0
527 }
never executed: }
0
528 delete[] oldArray;
never executed (the execution status of this line is deduced): delete[] oldArray;
-
529 }
never executed: }
0
530 return true;
never executed: return true;
0
531 } else { -
532 m_capacity = oldCapacity;
never executed (the execution status of this line is deduced): m_capacity = oldCapacity;
-
533 m_array = oldArray;
never executed (the execution status of this line is deduced): m_array = oldArray;
-
534 return false;
never executed: return false;
0
535 } -
536} -
537 -
538void QInt64Set::insert(quint64 key) -
539{ -
540 if (m_count > 3 * m_capacity / 4)
never evaluated: m_count > 3 * m_capacity / 4
0
541 rehash(primeForCount(2 * m_capacity));
never executed: rehash(primeForCount(2 * m_capacity));
0
542 Q_ASSERT_X(m_array, "QInt64Hash<T>::insert", "Hash set not allocated.");
never executed (the execution status of this line is deduced): qt_noop();
-
543 int index = int(key % m_capacity);
never executed (the execution status of this line is deduced): int index = int(key % m_capacity);
-
544 for (int i = 0; i < m_capacity; ++i) {
never evaluated: i < m_capacity
0
545 index += i;
never executed (the execution status of this line is deduced): index += i;
-
546 if (index >= m_capacity)
never evaluated: index >= m_capacity
0
547 index -= m_capacity;
never executed: index -= m_capacity;
0
548 if (m_array[index] == key)
never evaluated: m_array[index] == key
0
549 return;
never executed: return;
0
550 if (m_array[index] == UNUSED) {
never evaluated: m_array[index] == UNUSED
0
551 ++m_count;
never executed (the execution status of this line is deduced): ++m_count;
-
552 m_array[index] = key;
never executed (the execution status of this line is deduced): m_array[index] = key;
-
553 return;
never executed: return;
0
554 } -
555 }
never executed: }
0
556 Q_ASSERT_X(0, "QInt64Hash<T>::insert", "Hash set full.");
never executed (the execution status of this line is deduced): qt_noop();
-
557}
never executed: }
0
558 -
559bool QInt64Set::contains(quint64 key) const -
560{ -
561 Q_ASSERT_X(m_array, "QInt64Hash<T>::contains", "Hash set not allocated.");
never executed (the execution status of this line is deduced): qt_noop();
-
562 int index = int(key % m_capacity);
never executed (the execution status of this line is deduced): int index = int(key % m_capacity);
-
563 for (int i = 0; i < m_capacity; ++i) {
never evaluated: i < m_capacity
0
564 index += i;
never executed (the execution status of this line is deduced): index += i;
-
565 if (index >= m_capacity)
never evaluated: index >= m_capacity
0
566 index -= m_capacity;
never executed: index -= m_capacity;
0
567 if (m_array[index] == key)
never evaluated: m_array[index] == key
0
568 return true;
never executed: return true;
0
569 if (m_array[index] == UNUSED)
never evaluated: m_array[index] == UNUSED
0
570 return false;
never executed: return false;
0
571 }
never executed: }
0
572 return false;
never executed: return false;
0
573} -
574 -
575inline void QInt64Set::clear() -
576{ -
577 Q_ASSERT_X(m_array, "QInt64Hash<T>::clear", "Hash set not allocated.");
never executed (the execution status of this line is deduced): qt_noop();
-
578 for (int i = 0; i < m_capacity; ++i)
never evaluated: i < m_capacity
0
579 m_array[i] = UNUSED;
never executed: m_array[i] = UNUSED;
0
580 m_count = 0;
never executed (the execution status of this line is deduced): m_count = 0;
-
581}
never executed: }
0
582 -
583//============================================================================// -
584// QTriangulator // -
585//============================================================================// -
586template<typename T> -
587class QTriangulator -
588{ -
589public: -
590 typedef QVarLengthArray<int, 6> ShortArray; -
591 -
592 //================================// -
593 // QTriangulator::ComplexToSimple // -
594 //================================// -
595 friend class ComplexToSimple; -
596 class ComplexToSimple -
597 { -
598 public: -
599 inline ComplexToSimple(QTriangulator<T> *parent) : m_parent(parent), -
600 m_edges(0), m_events(0), m_splits(0) { }
never executed: }
0
601 void decompose(); -
602 private: -
603 struct Edge -
604 { -
605 inline int &upper() {return pointingUp ? to : from;}
never executed: return pointingUp ? to : from;
0
606 inline int &lower() {return pointingUp ? from : to;}
never executed: return pointingUp ? from : to;
0
607 inline int upper() const {return pointingUp ? to : from;}
never executed: return pointingUp ? to : from;
0
608 inline int lower() const {return pointingUp ? from : to;}
never executed: return pointingUp ? from : to;
0
609 -
610 QRBTree<int>::Node *node; -
611 int from, to; // vertex -
612 int next, previous; // edge -
613 int winding; -
614 bool mayIntersect; -
615 bool pointingUp, originallyPointingUp; -
616 }; -
617 -
618 struct Intersection -
619 { -
620 bool operator < (const Intersection &other) const {return other.intersectionPoint < intersectionPoint;}
never executed: return other.intersectionPoint < intersectionPoint;
0
621 -
622 QIntersectionPoint intersectionPoint; -
623 int vertex; -
624 int leftEdge; -
625 int rightEdge; -
626 }; -
627 -
628 struct Split -
629 { -
630 int vertex; -
631 int edge; -
632 bool accurate; -
633 }; -
634 -
635 struct Event -
636 { -
637 enum Type {Upper, Lower}; -
638 inline bool operator < (const Event &other) const; -
639 -
640 QPodPoint point; -
641 Type type; -
642 int edge; -
643 }; -
644 -
645#ifdef Q_TRIANGULATOR_DEBUG -
646 friend class DebugDialog; -
647 friend class QTriangulator; -
648 class DebugDialog : public QDialog -
649 { -
650 public: -
651 DebugDialog(ComplexToSimple *parent, int currentVertex); -
652 protected: -
653 void paintEvent(QPaintEvent *); -
654 void wheelEvent(QWheelEvent *); -
655 void mouseMoveEvent(QMouseEvent *); -
656 void mousePressEvent(QMouseEvent *); -
657 private: -
658 ComplexToSimple *m_parent; -
659 QRectF m_window; -
660 QPoint m_lastMousePos; -
661 int m_vertex; -
662 }; -
663#endif -
664 -
665 void initEdges(); -
666 bool calculateIntersection(int left, int right); -
667 bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const; -
668 QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex) const; -
669 QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const; -
670 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> bounds(const QPodPoint &point) const; -
671 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> outerBounds(const QPodPoint &point) const; -
672 void splitEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint); -
673 void reorderEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost); -
674 void sortEdgeList(const QPodPoint eventPoint); -
675 void fillPriorityQueue(); -
676 void calculateIntersections(); -
677 int splitEdge(int splitIndex); -
678 bool splitEdgesAtIntersections(); -
679 void insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i); -
680 void removeUnwantedEdgesAndConnect(); -
681 void removeUnusedPoints(); -
682 -
683 QTriangulator *m_parent; -
684 QDataBuffer<Edge> m_edges; -
685 QRBTree<int> m_edgeList; -
686 QDataBuffer<Event> m_events; -
687 QDataBuffer<Split> m_splits; -
688 QMaxHeap<Intersection> m_topIntersection; -
689 QInt64Set m_processedEdgePairs; -
690 int m_initialPointCount; -
691 }; -
692#ifdef Q_TRIANGULATOR_DEBUG -
693 friend class ComplexToSimple::DebugDialog; -
694#endif -
695 -
696 //=================================// -
697 // QTriangulator::SimpleToMonotone // -
698 //=================================// -
699 friend class SimpleToMonotone; -
700 class SimpleToMonotone -
701 { -
702 public: -
703 inline SimpleToMonotone(QTriangulator<T> *parent) : m_parent(parent), m_edges(0), m_upperVertex(0) { }
never executed: }
0
704 void decompose(); -
705 private: -
706 enum VertexType {MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex}; -
707 -
708 struct Edge -
709 { -
710 QRBTree<int>::Node *node; -
711 int helper, twin, next, previous; -
712 T from, to; -
713 VertexType type; -
714 bool pointingUp; -
715 int upper() const {return (pointingUp ? to : from);}
never executed: return (pointingUp ? to : from);
0
716 int lower() const {return (pointingUp ? from : to);}
never executed: return (pointingUp ? from : to);
0
717 }; -
718 -
719 friend class CompareVertices; -
720 class CompareVertices -
721 { -
722 public: -
723 CompareVertices(SimpleToMonotone *parent) : m_parent(parent) { }
never executed: }
0
724 bool operator () (int i, int j) const; -
725 private: -
726 SimpleToMonotone *m_parent; -
727 }; -
728 -
729 void setupDataStructures(); -
730 void removeZeroLengthEdges(); -
731 void fillPriorityQueue(); -
732 bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const; -
733 // Returns the rightmost edge not to the right of the given edge. -
734 QRBTree<int>::Node *searchEdgeLeftOfEdge(int edgeIndex) const; -
735 // Returns the rightmost edge left of the given point. -
736 QRBTree<int>::Node *searchEdgeLeftOfPoint(int pointIndex) const; -
737 void classifyVertex(int i); -
738 void classifyVertices(); -
739 bool pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3); -
740 bool pointIsInSector(int vertex, int sector); -
741 int findSector(int edge, int vertex); -
742 void createDiagonal(int lower, int upper); -
743 void monotoneDecomposition(); -
744 -
745 QTriangulator *m_parent; -
746 QRBTree<int> m_edgeList; -
747 QDataBuffer<Edge> m_edges; -
748 QDataBuffer<int> m_upperVertex; -
749 bool m_clockwiseOrder; -
750 }; -
751 -
752 //====================================// -
753 // QTriangulator::MonotoneToTriangles // -
754 //====================================// -
755 friend class MonotoneToTriangles; -
756 class MonotoneToTriangles -
757 { -
758 public: -
759 inline MonotoneToTriangles(QTriangulator<T> *parent) : m_parent(parent) { }
never executed: }
0
760 void decompose(); -
761 private: -
762 inline T indices(int index) const {return m_parent->m_indices.at(index + m_first);}
never executed: return m_parent->m_indices.at(index + m_first);
0
763 inline int next(int index) const {return (index + 1) % m_length;}
never executed: return (index + 1) % m_length;
0
764 inline int previous(int index) const {return (index + m_length - 1) % m_length;}
never executed: return (index + m_length - 1) % m_length;
0
765 inline bool less(int i, int j) const {return m_parent->m_vertices.at((qint32)indices(i)) < m_parent->m_vertices.at(indices(j));}
never executed: return m_parent->m_vertices.at((qint32)indices(i)) < m_parent->m_vertices.at(indices(j));
0
766 inline bool leftOfEdge(int i, int j, int k) const -
767 { -
768 return qPointIsLeftOfLine(m_parent->m_vertices.at((qint32)indices(i)),
never executed: return qPointIsLeftOfLine(m_parent->m_vertices.at((qint32)indices(i)), m_parent->m_vertices.at((qint32)indices(j)), m_parent->m_vertices.at((qint32)indices(k)));
0
769 m_parent->m_vertices.at((qint32)indices(j)), m_parent->m_vertices.at((qint32)indices(k)));
never executed: return qPointIsLeftOfLine(m_parent->m_vertices.at((qint32)indices(i)), m_parent->m_vertices.at((qint32)indices(j)), m_parent->m_vertices.at((qint32)indices(k)));
0
770 } -
771 -
772 QTriangulator<T> *m_parent; -
773 int m_first; -
774 int m_length; -
775 }; -
776 -
777 inline QTriangulator() : m_vertices(0) { }
never executed: }
0
778 -
779 // Call this only once. -
780 void initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix); -
781 // Call this only once. -
782 void initialize(const QVectorPath &path, const QTransform &matrix, qreal lod); -
783 // Call this only once. -
784 void initialize(const QPainterPath &path, const QTransform &matrix, qreal lod); -
785 // Call either triangulate() or polyline() only once. -
786 QVertexSet<T> triangulate(); -
787 QVertexSet<T> polyline(); -
788private: -
789 QDataBuffer<QPodPoint> m_vertices; -
790 QVector<T> m_indices; -
791 uint m_hint; -
792}; -
793 -
794//============================================================================// -
795// QTriangulator // -
796//============================================================================// -
797 -
798template <typename T> -
799QVertexSet<T> QTriangulator<T>::triangulate() -
800{ -
801 for (int i = 0; i < m_vertices.size(); ++i) {
never evaluated: i < m_vertices.size()
0
802 Q_ASSERT(qAbs(m_vertices.at(i).x) < (1 << 21));
never executed (the execution status of this line is deduced): qt_noop();
-
803 Q_ASSERT(qAbs(m_vertices.at(i).y) < (1 << 21));
never executed (the execution status of this line is deduced): qt_noop();
-
804 }
never executed: }
0
805 -
806 if (!(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill)))
never evaluated: !(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill))
0
807 m_hint |= QVectorPath::OddEvenFill;
never executed: m_hint |= QVectorPath::OddEvenFill;
0
808 -
809 if (m_hint & QVectorPath::NonConvexShapeMask) {
never evaluated: m_hint & QVectorPath::NonConvexShapeMask
0
810 ComplexToSimple c2s(this);
never executed (the execution status of this line is deduced): ComplexToSimple c2s(this);
-
811 c2s.decompose();
never executed (the execution status of this line is deduced): c2s.decompose();
-
812 SimpleToMonotone s2m(this);
never executed (the execution status of this line is deduced): SimpleToMonotone s2m(this);
-
813 s2m.decompose();
never executed (the execution status of this line is deduced): s2m.decompose();
-
814 }
never executed: }
0
815 MonotoneToTriangles m2t(this);
never executed (the execution status of this line is deduced): MonotoneToTriangles m2t(this);
-
816 m2t.decompose();
never executed (the execution status of this line is deduced): m2t.decompose();
-
817 -
818 QVertexSet<T> result;
never executed (the execution status of this line is deduced): QVertexSet<T> result;
-
819 result.indices = m_indices;
never executed (the execution status of this line is deduced): result.indices = m_indices;
-
820 result.vertices.resize(2 * m_vertices.size());
never executed (the execution status of this line is deduced): result.vertices.resize(2 * m_vertices.size());
-
821 for (int i = 0; i < m_vertices.size(); ++i) {
never evaluated: i < m_vertices.size()
0
822 result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / Q_FIXED_POINT_SCALE;
never executed (the execution status of this line is deduced): result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / 32;
-
823 result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / Q_FIXED_POINT_SCALE;
never executed (the execution status of this line is deduced): result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / 32;
-
824 }
never executed: }
0
825 return result;
never executed: return result;
0
826} -
827 -
828template <typename T> -
829QVertexSet<T> QTriangulator<T>::polyline() -
830{ -
831 for (int i = 0; i < m_vertices.size(); ++i) {
never evaluated: i < m_vertices.size()
0
832 Q_ASSERT(qAbs(m_vertices.at(i).x) < (1 << 21));
never executed (the execution status of this line is deduced): qt_noop();
-
833 Q_ASSERT(qAbs(m_vertices.at(i).y) < (1 << 21));
never executed (the execution status of this line is deduced): qt_noop();
-
834 }
never executed: }
0
835 -
836 if (!(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill)))
never evaluated: !(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill))
0
837 m_hint |= QVectorPath::OddEvenFill;
never executed: m_hint |= QVectorPath::OddEvenFill;
0
838 -
839 if (m_hint & QVectorPath::NonConvexShapeMask) {
never evaluated: m_hint & QVectorPath::NonConvexShapeMask
0
840 ComplexToSimple c2s(this);
never executed (the execution status of this line is deduced): ComplexToSimple c2s(this);
-
841 c2s.decompose();
never executed (the execution status of this line is deduced): c2s.decompose();
-
842 }
never executed: }
0
843 -
844 QVertexSet<T> result;
never executed (the execution status of this line is deduced): QVertexSet<T> result;
-
845 result.indices = m_indices;
never executed (the execution status of this line is deduced): result.indices = m_indices;
-
846 result.vertices.resize(2 * m_vertices.size());
never executed (the execution status of this line is deduced): result.vertices.resize(2 * m_vertices.size());
-
847 for (int i = 0; i < m_vertices.size(); ++i) {
never evaluated: i < m_vertices.size()
0
848 result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / Q_FIXED_POINT_SCALE;
never executed (the execution status of this line is deduced): result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / 32;
-
849 result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / Q_FIXED_POINT_SCALE;
never executed (the execution status of this line is deduced): result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / 32;
-
850 }
never executed: }
0
851 return result;
never executed: return result;
0
852} -
853 -
854template <typename T> -
855void QTriangulator<T>::initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix) -
856{ -
857 m_hint = hint;
never executed (the execution status of this line is deduced): m_hint = hint;
-
858 m_vertices.resize(count);
never executed (the execution status of this line is deduced): m_vertices.resize(count);
-
859 m_indices.resize(count + 1);
never executed (the execution status of this line is deduced): m_indices.resize(count + 1);
-
860 for (int i = 0; i < count; ++i) {
never evaluated: i < count
0
861 qreal x, y;
never executed (the execution status of this line is deduced): qreal x, y;
-
862 matrix.map(polygon[2 * i + 0], polygon[2 * i + 1], &x, &y);
never executed (the execution status of this line is deduced): matrix.map(polygon[2 * i + 0], polygon[2 * i + 1], &x, &y);
-
863 m_vertices.at(i).x = qRound(x * Q_FIXED_POINT_SCALE);
never executed (the execution status of this line is deduced): m_vertices.at(i).x = qRound(x * 32);
-
864 m_vertices.at(i).y = qRound(y * Q_FIXED_POINT_SCALE);
never executed (the execution status of this line is deduced): m_vertices.at(i).y = qRound(y * 32);
-
865 m_indices[i] = i;
never executed (the execution status of this line is deduced): m_indices[i] = i;
-
866 }
never executed: }
0
867 m_indices[count] = T(-1); //Q_TRIANGULATE_END_OF_POLYGON
never executed (the execution status of this line is deduced): m_indices[count] = T(-1);
-
868}
never executed: }
0
869 -
870template <typename T> -
871void QTriangulator<T>::initialize(const QVectorPath &path, const QTransform &matrix, qreal lod) -
872{ -
873 m_hint = path.hints();
never executed (the execution status of this line is deduced): m_hint = path.hints();
-
874 // Curved paths will be converted to complex polygons. -
875 m_hint &= ~QVectorPath::CurvedShapeMask;
never executed (the execution status of this line is deduced): m_hint &= ~QVectorPath::CurvedShapeMask;
-
876 -
877 const qreal *p = path.points();
never executed (the execution status of this line is deduced): const qreal *p = path.points();
-
878 const QPainterPath::ElementType *e = path.elements();
never executed (the execution status of this line is deduced): const QPainterPath::ElementType *e = path.elements();
-
879 if (e) {
never evaluated: e
0
880 for (int i = 0; i < path.elementCount(); ++i, ++e, p += 2) {
never evaluated: i < path.elementCount()
0
881 switch (*e) { -
882 case QPainterPath::MoveToElement: -
883 if (!m_indices.isEmpty())
never evaluated: !m_indices.isEmpty()
0
884 m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
never executed: m_indices.push_back(T(-1));
0
885 // Fall through. -
886 case QPainterPath::LineToElement:
code before this statement never executed: case QPainterPath::LineToElement:
0
887 m_indices.push_back(T(m_vertices.size()));
never executed (the execution status of this line is deduced): m_indices.push_back(T(m_vertices.size()));
-
888 m_vertices.resize(m_vertices.size() + 1);
never executed (the execution status of this line is deduced): m_vertices.resize(m_vertices.size() + 1);
-
889 qreal x, y;
never executed (the execution status of this line is deduced): qreal x, y;
-
890 matrix.map(p[0], p[1], &x, &y);
never executed (the execution status of this line is deduced): matrix.map(p[0], p[1], &x, &y);
-
891 m_vertices.last().x = qRound(x * Q_FIXED_POINT_SCALE);
never executed (the execution status of this line is deduced): m_vertices.last().x = qRound(x * 32);
-
892 m_vertices.last().y = qRound(y * Q_FIXED_POINT_SCALE);
never executed (the execution status of this line is deduced): m_vertices.last().y = qRound(y * 32);
-
893 break;
never executed: break;
0
894 case QPainterPath::CurveToElement: -
895 { -
896 qreal pts[8];
never executed (the execution status of this line is deduced): qreal pts[8];
-
897 for (int i = 0; i < 4; ++i)
never evaluated: i < 4
0
898 matrix.map(p[2 * i - 2], p[2 * i - 1], &pts[2 * i + 0], &pts[2 * i + 1]);
never executed: matrix.map(p[2 * i - 2], p[2 * i - 1], &pts[2 * i + 0], &pts[2 * i + 1]);
0
899 for (int i = 0; i < 8; ++i)
never evaluated: i < 8
0
900 pts[i] *= lod;
never executed: pts[i] *= lod;
0
901 QBezier bezier = QBezier::fromPoints(QPointF(pts[0], pts[1]), QPointF(pts[2], pts[3]), QPointF(pts[4], pts[5]), QPointF(pts[6], pts[7]));
never executed (the execution status of this line is deduced): QBezier bezier = QBezier::fromPoints(QPointF(pts[0], pts[1]), QPointF(pts[2], pts[3]), QPointF(pts[4], pts[5]), QPointF(pts[6], pts[7]));
-
902 QPolygonF poly = bezier.toPolygon();
never executed (the execution status of this line is deduced): QPolygonF poly = bezier.toPolygon();
-
903 // Skip first point, it already exists in 'm_vertices'. -
904 for (int j = 1; j < poly.size(); ++j) {
never evaluated: j < poly.size()
0
905 m_indices.push_back(T(m_vertices.size()));
never executed (the execution status of this line is deduced): m_indices.push_back(T(m_vertices.size()));
-
906 m_vertices.resize(m_vertices.size() + 1);
never executed (the execution status of this line is deduced): m_vertices.resize(m_vertices.size() + 1);
-
907 m_vertices.last().x = qRound(poly.at(j).x() * Q_FIXED_POINT_SCALE / lod);
never executed (the execution status of this line is deduced): m_vertices.last().x = qRound(poly.at(j).x() * 32 / lod);
-
908 m_vertices.last().y = qRound(poly.at(j).y() * Q_FIXED_POINT_SCALE / lod);
never executed (the execution status of this line is deduced): m_vertices.last().y = qRound(poly.at(j).y() * 32 / lod);
-
909 }
never executed: }
0
910 } -
911 i += 2;
never executed (the execution status of this line is deduced): i += 2;
-
912 e += 2;
never executed (the execution status of this line is deduced): e += 2;
-
913 p += 4;
never executed (the execution status of this line is deduced): p += 4;
-
914 break;
never executed: break;
0
915 default: -
916 Q_ASSERT_X(0, "QTriangulator::triangulate", "Unexpected element type.");
never executed (the execution status of this line is deduced): qt_noop();
-
917 break;
never executed: break;
0
918 } -
919 }
never executed: }
0
920 } else {
never executed: }
0
921 for (int i = 0; i < path.elementCount(); ++i, p += 2) {
never evaluated: i < path.elementCount()
0
922 m_indices.push_back(T(m_vertices.size()));
never executed (the execution status of this line is deduced): m_indices.push_back(T(m_vertices.size()));
-
923 m_vertices.resize(m_vertices.size() + 1);
never executed (the execution status of this line is deduced): m_vertices.resize(m_vertices.size() + 1);
-
924 qreal x, y;
never executed (the execution status of this line is deduced): qreal x, y;
-
925 matrix.map(p[0], p[1], &x, &y);
never executed (the execution status of this line is deduced): matrix.map(p[0], p[1], &x, &y);
-
926 m_vertices.last().x = qRound(x * Q_FIXED_POINT_SCALE);
never executed (the execution status of this line is deduced): m_vertices.last().x = qRound(x * 32);
-
927 m_vertices.last().y = qRound(y * Q_FIXED_POINT_SCALE);
never executed (the execution status of this line is deduced): m_vertices.last().y = qRound(y * 32);
-
928 }
never executed: }
0
929 }
never executed: }
0
930 m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
never executed (the execution status of this line is deduced): m_indices.push_back(T(-1));
-
931}
never executed: }
0
932 -
933template <typename T> -
934void QTriangulator<T>::initialize(const QPainterPath &path, const QTransform &matrix, qreal lod) -
935{ -
936 initialize(qtVectorPathForPath(path), matrix, lod);
never executed (the execution status of this line is deduced): initialize(qtVectorPathForPath(path), matrix, lod);
-
937}
never executed: }
0
938 -
939//============================================================================// -
940// QTriangulator::ComplexToSimple // -
941//============================================================================// -
942template <typename T> -
943void QTriangulator<T>::ComplexToSimple::decompose() -
944{ -
945 m_initialPointCount = m_parent->m_vertices.size();
never executed (the execution status of this line is deduced): m_initialPointCount = m_parent->m_vertices.size();
-
946 initEdges();
never executed (the execution status of this line is deduced): initEdges();
-
947 do { -
948 calculateIntersections();
never executed (the execution status of this line is deduced): calculateIntersections();
-
949 } while (splitEdgesAtIntersections());
never executed: }
never evaluated: splitEdgesAtIntersections()
0
950 -
951 removeUnwantedEdgesAndConnect();
never executed (the execution status of this line is deduced): removeUnwantedEdgesAndConnect();
-
952 removeUnusedPoints();
never executed (the execution status of this line is deduced): removeUnusedPoints();
-
953 -
954 m_parent->m_indices.clear();
never executed (the execution status of this line is deduced): m_parent->m_indices.clear();
-
955 QBitArray processed(m_edges.size(), false);
never executed (the execution status of this line is deduced): QBitArray processed(m_edges.size(), false);
-
956 for (int first = 0; first < m_edges.size(); ++first) {
never evaluated: first < m_edges.size()
0
957 // If already processed, or if unused path, skip. -
958 if (processed.at(first) || m_edges.at(first).next == -1)
never evaluated: processed.at(first)
never evaluated: m_edges.at(first).next == -1
0
959 continue;
never executed: continue;
0
960 -
961 int i = first;
never executed (the execution status of this line is deduced): int i = first;
-
962 do { -
963 Q_ASSERT(!processed.at(i));
never executed (the execution status of this line is deduced): qt_noop();
-
964 Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i);
never executed (the execution status of this line is deduced): qt_noop();
-
965 m_parent->m_indices.push_back(m_edges.at(i).from);
never executed (the execution status of this line is deduced): m_parent->m_indices.push_back(m_edges.at(i).from);
-
966 processed.setBit(i);
never executed (the execution status of this line is deduced): processed.setBit(i);
-
967 i = m_edges.at(i).next; // CCW order
never executed (the execution status of this line is deduced): i = m_edges.at(i).next;
-
968 } while (i != first);
never executed: }
never evaluated: i != first
0
969 m_parent->m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
never executed (the execution status of this line is deduced): m_parent->m_indices.push_back(T(-1));
-
970 }
never executed: }
0
971}
never executed: }
0
972 -
973template <typename T> -
974void QTriangulator<T>::ComplexToSimple::initEdges() -
975{ -
976 // Initialize edge structure. -
977 // 'next' and 'previous' are not being initialized at this point. -
978 int first = 0;
never executed (the execution status of this line is deduced): int first = 0;
-
979 for (int i = 0; i < m_parent->m_indices.size(); ++i) {
never evaluated: i < m_parent->m_indices.size()
0
980 if (m_parent->m_indices.at(i) == T(-1)) { // Q_TRIANGULATE_END_OF_POLYGON
never evaluated: m_parent->m_indices.at(i) == T(-1)
0
981 if (m_edges.size() != first)
never evaluated: m_edges.size() != first
0
982 m_edges.last().to = m_edges.at(first).from;
never executed: m_edges.last().to = m_edges.at(first).from;
0
983 first = m_edges.size();
never executed (the execution status of this line is deduced): first = m_edges.size();
-
984 } else {
never executed: }
0
985 Q_ASSERT(i + 1 < m_parent->m_indices.size());
never executed (the execution status of this line is deduced): qt_noop();
-
986 // {node, from, to, next, previous, winding, mayIntersect, pointingUp, originallyPointingUp} -
987 Edge edge = {0, int(m_parent->m_indices.at(i)), int(m_parent->m_indices.at(i + 1)), -1, -1, 0, true, false, false};
never executed (the execution status of this line is deduced): Edge edge = {0, int(m_parent->m_indices.at(i)), int(m_parent->m_indices.at(i + 1)), -1, -1, 0, true, false, false};
-
988 m_edges.add(edge);
never executed (the execution status of this line is deduced): m_edges.add(edge);
-
989 }
never executed: }
0
990 } -
991 if (first != m_edges.size())
never evaluated: first != m_edges.size()
0
992 m_edges.last().to = m_edges.at(first).from;
never executed: m_edges.last().to = m_edges.at(first).from;
0
993 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
994 m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp =
never executed (the execution status of this line is deduced): m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp =
-
995 m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from);
never executed (the execution status of this line is deduced): m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from);
-
996 }
never executed: }
0
997}
never executed: }
0
998 -
999// Return true if new intersection was found -
1000template <typename T> -
1001bool QTriangulator<T>::ComplexToSimple::calculateIntersection(int left, int right) -
1002{ -
1003 const Edge &e1 = m_edges.at(left);
never executed (the execution status of this line is deduced): const Edge &e1 = m_edges.at(left);
-
1004 const Edge &e2 = m_edges.at(right);
never executed (the execution status of this line is deduced): const Edge &e2 = m_edges.at(right);
-
1005 -
1006 const QPodPoint &u1 = m_parent->m_vertices.at((qint32)e1.from);
never executed (the execution status of this line is deduced): const QPodPoint &u1 = m_parent->m_vertices.at((qint32)e1.from);
-
1007 const QPodPoint &u2 = m_parent->m_vertices.at((qint32)e1.to);
never executed (the execution status of this line is deduced): const QPodPoint &u2 = m_parent->m_vertices.at((qint32)e1.to);
-
1008 const QPodPoint &v1 = m_parent->m_vertices.at((qint32)e2.from);
never executed (the execution status of this line is deduced): const QPodPoint &v1 = m_parent->m_vertices.at((qint32)e2.from);
-
1009 const QPodPoint &v2 = m_parent->m_vertices.at((qint32)e2.to);
never executed (the execution status of this line is deduced): const QPodPoint &v2 = m_parent->m_vertices.at((qint32)e2.to);
-
1010 if (qMax(u1.x, u2.x) <= qMin(v1.x, v2.x))
never evaluated: qMax(u1.x, u2.x) <= qMin(v1.x, v2.x)
0
1011 return false;
never executed: return false;
0
1012 -
1013 quint64 key = (left > right ? (quint64(right) << 32) | quint64(left) : (quint64(left) << 32) | quint64(right));
never evaluated: left > right
0
1014 if (m_processedEdgePairs.contains(key))
never evaluated: m_processedEdgePairs.contains(key)
0
1015 return false;
never executed: return false;
0
1016 m_processedEdgePairs.insert(key);
never executed (the execution status of this line is deduced): m_processedEdgePairs.insert(key);
-
1017 -
1018 Intersection intersection;
never executed (the execution status of this line is deduced): Intersection intersection;
-
1019 intersection.leftEdge = left;
never executed (the execution status of this line is deduced): intersection.leftEdge = left;
-
1020 intersection.rightEdge = right;
never executed (the execution status of this line is deduced): intersection.rightEdge = right;
-
1021 intersection.intersectionPoint = QT_PREPEND_NAMESPACE(qIntersectionPoint)(u1, u2, v1, v2);
never executed (the execution status of this line is deduced): intersection.intersectionPoint = ::qIntersectionPoint(u1, u2, v1, v2);
-
1022 -
1023 if (!intersection.intersectionPoint.isValid())
never evaluated: !intersection.intersectionPoint.isValid()
0
1024 return false;
never executed: return false;
0
1025 -
1026 Q_ASSERT(intersection.intersectionPoint.isOnLine(u1, u2));
never executed (the execution status of this line is deduced): qt_noop();
-
1027 Q_ASSERT(intersection.intersectionPoint.isOnLine(v1, v2));
never executed (the execution status of this line is deduced): qt_noop();
-
1028 -
1029 intersection.vertex = m_parent->m_vertices.size();
never executed (the execution status of this line is deduced): intersection.vertex = m_parent->m_vertices.size();
-
1030 m_topIntersection.push(intersection);
never executed (the execution status of this line is deduced): m_topIntersection.push(intersection);
-
1031 m_parent->m_vertices.add(intersection.intersectionPoint.round());
never executed (the execution status of this line is deduced): m_parent->m_vertices.add(intersection.intersectionPoint.round());
-
1032 return true;
never executed: return true;
0
1033} -
1034 -
1035template <typename T> -
1036bool QTriangulator<T>::ComplexToSimple::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const -
1037{ -
1038 const Edge &leftEdge = m_edges.at(leftEdgeIndex);
never executed (the execution status of this line is deduced): const Edge &leftEdge = m_edges.at(leftEdgeIndex);
-
1039 const Edge &rightEdge = m_edges.at(rightEdgeIndex);
never executed (the execution status of this line is deduced): const Edge &rightEdge = m_edges.at(rightEdgeIndex);
-
1040 const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
never executed (the execution status of this line is deduced): const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
-
1041 const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
never executed (the execution status of this line is deduced): const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
-
1042 const QPodPoint &upper = m_parent->m_vertices.at(leftEdge.upper());
never executed (the execution status of this line is deduced): const QPodPoint &upper = m_parent->m_vertices.at(leftEdge.upper());
-
1043 if (upper.x < qMin(l.x, u.x))
never evaluated: upper.x < qMin(l.x, u.x)
0
1044 return true;
never executed: return true;
0
1045 if (upper.x > qMax(l.x, u.x))
never evaluated: upper.x > qMax(l.x, u.x)
0
1046 return false;
never executed: return false;
0
1047 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(upper, l, u);
never executed (the execution status of this line is deduced): qint64 d = ::qPointDistanceFromLine(upper, l, u);
-
1048 // d < 0: left, d > 0: right, d == 0: on top -
1049 if (d == 0)
never evaluated: d == 0
0
1050 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(leftEdge.lower()), l, u);
never executed: d = ::qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.lower()), l, u);
0
1051 return d < 0;
never executed: return d < 0;
0
1052} -
1053 -
1054template <typename T> -
1055QRBTree<int>::Node *QTriangulator<T>::ComplexToSimple::searchEdgeLeftOf(int edgeIndex) const -
1056{ -
1057 QRBTree<int>::Node *current = m_edgeList.root;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *current = m_edgeList.root;
-
1058 QRBTree<int>::Node *result = 0;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *result = 0;
-
1059 while (current) {
never evaluated: current
0
1060 if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
never evaluated: edgeIsLeftOfEdge(edgeIndex, current->data)
0
1061 current = current->left;
never executed (the execution status of this line is deduced): current = current->left;
-
1062 } else {
never executed: }
0
1063 result = current;
never executed (the execution status of this line is deduced): result = current;
-
1064 current = current->right;
never executed (the execution status of this line is deduced): current = current->right;
-
1065 }
never executed: }
0
1066 } -
1067 return result;
never executed: return result;
0
1068} -
1069 -
1070template <typename T> -
1071QRBTree<int>::Node *QTriangulator<T>::ComplexToSimple::searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const -
1072{ -
1073 if (!m_edgeList.root)
never evaluated: !m_edgeList.root
0
1074 return after;
never executed: return after;
0
1075 QRBTree<int>::Node *result = after;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *result = after;
-
1076 QRBTree<int>::Node *current = (after ? m_edgeList.next(after) : m_edgeList.front(m_edgeList.root));
never evaluated: after
0
1077 while (current) {
never evaluated: current
0
1078 if (edgeIsLeftOfEdge(edgeIndex, current->data))
never evaluated: edgeIsLeftOfEdge(edgeIndex, current->data)
0
1079 return result;
never executed: return result;
0
1080 result = current;
never executed (the execution status of this line is deduced): result = current;
-
1081 current = m_edgeList.next(current);
never executed (the execution status of this line is deduced): current = m_edgeList.next(current);
-
1082 }
never executed: }
0
1083 return result;
never executed: return result;
0
1084} -
1085 -
1086template <typename T> -
1087QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator<T>::ComplexToSimple::bounds(const QPodPoint &point) const -
1088{ -
1089 QRBTree<int>::Node *current = m_edgeList.root;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *current = m_edgeList.root;
-
1090 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0);
never executed (the execution status of this line is deduced): QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0);
-
1091 while (current) {
never evaluated: current
0
1092 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
never executed (the execution status of this line is deduced): const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
-
1093 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
never executed (the execution status of this line is deduced): const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
-
1094 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(point, v1, v2);
never executed (the execution status of this line is deduced): qint64 d = ::qPointDistanceFromLine(point, v1, v2);
-
1095 if (d == 0) {
never evaluated: d == 0
0
1096 result.first = result.second = current;
never executed (the execution status of this line is deduced): result.first = result.second = current;
-
1097 break;
never executed: break;
0
1098 } -
1099 current = (d < 0 ? current->left : current->right);
never evaluated: d < 0
0
1100 }
never executed: }
0
1101 if (current == 0)
never evaluated: current == 0
0
1102 return result;
never executed: return result;
0
1103 -
1104 current = result.first->left;
never executed (the execution status of this line is deduced): current = result.first->left;
-
1105 while (current) {
never evaluated: current
0
1106 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
never executed (the execution status of this line is deduced): const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
-
1107 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
never executed (the execution status of this line is deduced): const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
-
1108 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(point, v1, v2);
never executed (the execution status of this line is deduced): qint64 d = ::qPointDistanceFromLine(point, v1, v2);
-
1109 Q_ASSERT(d >= 0);
never executed (the execution status of this line is deduced): qt_noop();
-
1110 if (d == 0) {
never evaluated: d == 0
0
1111 result.first = current;
never executed (the execution status of this line is deduced): result.first = current;
-
1112 current = current->left;
never executed (the execution status of this line is deduced): current = current->left;
-
1113 } else {
never executed: }
0
1114 current = current->right;
never executed (the execution status of this line is deduced): current = current->right;
-
1115 }
never executed: }
0
1116 } -
1117 -
1118 current = result.second->right;
never executed (the execution status of this line is deduced): current = result.second->right;
-
1119 while (current) {
never evaluated: current
0
1120 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
never executed (the execution status of this line is deduced): const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
-
1121 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
never executed (the execution status of this line is deduced): const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
-
1122 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(point, v1, v2);
never executed (the execution status of this line is deduced): qint64 d = ::qPointDistanceFromLine(point, v1, v2);
-
1123 Q_ASSERT(d <= 0);
never executed (the execution status of this line is deduced): qt_noop();
-
1124 if (d == 0) {
never evaluated: d == 0
0
1125 result.second = current;
never executed (the execution status of this line is deduced): result.second = current;
-
1126 current = current->right;
never executed (the execution status of this line is deduced): current = current->right;
-
1127 } else {
never executed: }
0
1128 current = current->left;
never executed (the execution status of this line is deduced): current = current->left;
-
1129 }
never executed: }
0
1130 } -
1131 -
1132 return result;
never executed: return result;
0
1133} -
1134 -
1135template <typename T> -
1136QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator<T>::ComplexToSimple::outerBounds(const QPodPoint &point) const -
1137{ -
1138 QRBTree<int>::Node *current = m_edgeList.root;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *current = m_edgeList.root;
-
1139 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0);
never executed (the execution status of this line is deduced): QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0);
-
1140 -
1141 while (current) {
never evaluated: current
0
1142 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
never executed (the execution status of this line is deduced): const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
-
1143 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
never executed (the execution status of this line is deduced): const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
-
1144 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(point, v1, v2);
never executed (the execution status of this line is deduced): qint64 d = ::qPointDistanceFromLine(point, v1, v2);
-
1145 if (d == 0)
never evaluated: d == 0
0
1146 break;
never executed: break;
0
1147 if (d < 0) {
never evaluated: d < 0
0
1148 result.second = current;
never executed (the execution status of this line is deduced): result.second = current;
-
1149 current = current->left;
never executed (the execution status of this line is deduced): current = current->left;
-
1150 } else {
never executed: }
0
1151 result.first = current;
never executed (the execution status of this line is deduced): result.first = current;
-
1152 current = current->right;
never executed (the execution status of this line is deduced): current = current->right;
-
1153 }
never executed: }
0
1154 } -
1155 -
1156 if (!current)
never evaluated: !current
0
1157 return result;
never executed: return result;
0
1158 -
1159 QRBTree<int>::Node *mid = current;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *mid = current;
-
1160 -
1161 current = mid->left;
never executed (the execution status of this line is deduced): current = mid->left;
-
1162 while (current) {
never evaluated: current
0
1163 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
never executed (the execution status of this line is deduced): const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
-
1164 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
never executed (the execution status of this line is deduced): const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
-
1165 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(point, v1, v2);
never executed (the execution status of this line is deduced): qint64 d = ::qPointDistanceFromLine(point, v1, v2);
-
1166 Q_ASSERT(d >= 0);
never executed (the execution status of this line is deduced): qt_noop();
-
1167 if (d == 0) {
never evaluated: d == 0
0
1168 current = current->left;
never executed (the execution status of this line is deduced): current = current->left;
-
1169 } else {
never executed: }
0
1170 result.first = current;
never executed (the execution status of this line is deduced): result.first = current;
-
1171 current = current->right;
never executed (the execution status of this line is deduced): current = current->right;
-
1172 }
never executed: }
0
1173 } -
1174 -
1175 current = mid->right;
never executed (the execution status of this line is deduced): current = mid->right;
-
1176 while (current) {
never evaluated: current
0
1177 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
never executed (the execution status of this line is deduced): const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
-
1178 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
never executed (the execution status of this line is deduced): const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
-
1179 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(point, v1, v2);
never executed (the execution status of this line is deduced): qint64 d = ::qPointDistanceFromLine(point, v1, v2);
-
1180 Q_ASSERT(d <= 0);
never executed (the execution status of this line is deduced): qt_noop();
-
1181 if (d == 0) {
never evaluated: d == 0
0
1182 current = current->right;
never executed (the execution status of this line is deduced): current = current->right;
-
1183 } else {
never executed: }
0
1184 result.second = current;
never executed (the execution status of this line is deduced): result.second = current;
-
1185 current = current->left;
never executed (the execution status of this line is deduced): current = current->left;
-
1186 }
never executed: }
0
1187 } -
1188 -
1189 return result;
never executed: return result;
0
1190} -
1191 -
1192template <typename T> -
1193void QTriangulator<T>::ComplexToSimple::splitEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint) -
1194{ -
1195 Q_ASSERT(leftmost && rightmost);
never executed (the execution status of this line is deduced): qt_noop();
-
1196 -
1197 // Split. -
1198 for (;;) {
never executed (the execution status of this line is deduced): for (;;) {
-
1199 const QPodPoint &u = m_parent->m_vertices.at(m_edges.at(leftmost->data).from);
never executed (the execution status of this line is deduced): const QPodPoint &u = m_parent->m_vertices.at(m_edges.at(leftmost->data).from);
-
1200 const QPodPoint &v = m_parent->m_vertices.at(m_edges.at(leftmost->data).to);
never executed (the execution status of this line is deduced): const QPodPoint &v = m_parent->m_vertices.at(m_edges.at(leftmost->data).to);
-
1201 Q_ASSERT(intersectionPoint.isOnLine(u, v));
never executed (the execution status of this line is deduced): qt_noop();
-
1202 const Split split = {vertex, leftmost->data, intersectionPoint.isAccurate()};
never executed (the execution status of this line is deduced): const Split split = {vertex, leftmost->data, intersectionPoint.isAccurate()};
-
1203 if (intersectionPoint.xOffset.numerator != 0 || intersectionPoint.yOffset.numerator != 0 || (intersectionPoint.upperLeft != u && intersectionPoint.upperLeft != v))
never evaluated: intersectionPoint.xOffset.numerator != 0
never evaluated: intersectionPoint.yOffset.numerator != 0
never evaluated: intersectionPoint.upperLeft != u
never evaluated: intersectionPoint.upperLeft != v
0
1204 m_splits.add(split);
never executed: m_splits.add(split);
0
1205 if (leftmost == rightmost)
never evaluated: leftmost == rightmost
0
1206 break;
never executed: break;
0
1207 leftmost = m_edgeList.next(leftmost);
never executed (the execution status of this line is deduced): leftmost = m_edgeList.next(leftmost);
-
1208 }
never executed: }
0
1209}
never executed: }
0
1210 -
1211template <typename T> -
1212void QTriangulator<T>::ComplexToSimple::reorderEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost) -
1213{ -
1214 Q_ASSERT(leftmost && rightmost);
never executed (the execution status of this line is deduced): qt_noop();
-
1215 -
1216 QRBTree<int>::Node *storeLeftmost = leftmost;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *storeLeftmost = leftmost;
-
1217 QRBTree<int>::Node *storeRightmost = rightmost;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *storeRightmost = rightmost;
-
1218 -
1219 // Reorder. -
1220 while (leftmost != rightmost) {
never evaluated: leftmost != rightmost
0
1221 Edge &left = m_edges.at(leftmost->data);
never executed (the execution status of this line is deduced): Edge &left = m_edges.at(leftmost->data);
-
1222 Edge &right = m_edges.at(rightmost->data);
never executed (the execution status of this line is deduced): Edge &right = m_edges.at(rightmost->data);
-
1223 qSwap(left.node, right.node);
never executed (the execution status of this line is deduced): qSwap(left.node, right.node);
-
1224 qSwap(leftmost->data, rightmost->data);
never executed (the execution status of this line is deduced): qSwap(leftmost->data, rightmost->data);
-
1225 leftmost = m_edgeList.next(leftmost);
never executed (the execution status of this line is deduced): leftmost = m_edgeList.next(leftmost);
-
1226 if (leftmost == rightmost)
never evaluated: leftmost == rightmost
0
1227 break;
never executed: break;
0
1228 rightmost = m_edgeList.previous(rightmost);
never executed (the execution status of this line is deduced): rightmost = m_edgeList.previous(rightmost);
-
1229 }
never executed: }
0
1230 -
1231 rightmost = m_edgeList.next(storeRightmost);
never executed (the execution status of this line is deduced): rightmost = m_edgeList.next(storeRightmost);
-
1232 leftmost = m_edgeList.previous(storeLeftmost);
never executed (the execution status of this line is deduced): leftmost = m_edgeList.previous(storeLeftmost);
-
1233 if (leftmost)
never evaluated: leftmost
0
1234 calculateIntersection(leftmost->data, storeLeftmost->data);
never executed: calculateIntersection(leftmost->data, storeLeftmost->data);
0
1235 if (rightmost)
never evaluated: rightmost
0
1236 calculateIntersection(storeRightmost->data, rightmost->data);
never executed: calculateIntersection(storeRightmost->data, rightmost->data);
0
1237}
never executed: }
0
1238 -
1239template <typename T> -
1240void QTriangulator<T>::ComplexToSimple::sortEdgeList(const QPodPoint eventPoint) -
1241{ -
1242 QIntersectionPoint eventPoint2 = QT_PREPEND_NAMESPACE(qIntersectionPoint)(eventPoint);
never executed (the execution status of this line is deduced): QIntersectionPoint eventPoint2 = ::qIntersectionPoint(eventPoint);
-
1243 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint < eventPoint2) {
never evaluated: !m_topIntersection.isEmpty()
never evaluated: m_topIntersection.top().intersectionPoint < eventPoint2
0
1244 Intersection intersection = m_topIntersection.pop();
never executed (the execution status of this line is deduced): Intersection intersection = m_topIntersection.pop();
-
1245 -
1246 QIntersectionPoint currentIntersectionPoint = intersection.intersectionPoint;
never executed (the execution status of this line is deduced): QIntersectionPoint currentIntersectionPoint = intersection.intersectionPoint;
-
1247 int currentVertex = intersection.vertex;
never executed (the execution status of this line is deduced): int currentVertex = intersection.vertex;
-
1248 -
1249 QRBTree<int>::Node *leftmost = m_edges.at(intersection.leftEdge).node;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *leftmost = m_edges.at(intersection.leftEdge).node;
-
1250 QRBTree<int>::Node *rightmost = m_edges.at(intersection.rightEdge).node;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *rightmost = m_edges.at(intersection.rightEdge).node;
-
1251 -
1252 for (;;) {
never executed (the execution status of this line is deduced): for (;;) {
-
1253 QRBTree<int>::Node *previous = m_edgeList.previous(leftmost);
never executed (the execution status of this line is deduced): QRBTree<int>::Node *previous = m_edgeList.previous(leftmost);
-
1254 if (!previous)
never evaluated: !previous
0
1255 break;
never executed: break;
0
1256 const Edge &edge = m_edges.at(previous->data);
never executed (the execution status of this line is deduced): const Edge &edge = m_edges.at(previous->data);
-
1257 const QPodPoint &u = m_parent->m_vertices.at((qint32)edge.from);
never executed (the execution status of this line is deduced): const QPodPoint &u = m_parent->m_vertices.at((qint32)edge.from);
-
1258 const QPodPoint &v = m_parent->m_vertices.at((qint32)edge.to);
never executed (the execution status of this line is deduced): const QPodPoint &v = m_parent->m_vertices.at((qint32)edge.to);
-
1259 if (!currentIntersectionPoint.isOnLine(u, v)) {
never evaluated: !currentIntersectionPoint.isOnLine(u, v)
0
1260 Q_ASSERT(!currentIntersectionPoint.isAccurate() || qCross(currentIntersectionPoint.upperLeft - u, v - u) != 0);
never executed (the execution status of this line is deduced): qt_noop();
-
1261 break;
never executed: break;
0
1262 } -
1263 leftmost = previous;
never executed (the execution status of this line is deduced): leftmost = previous;
-
1264 }
never executed: }
0
1265 -
1266 for (;;) {
never executed (the execution status of this line is deduced): for (;;) {
-
1267 QRBTree<int>::Node *next = m_edgeList.next(rightmost);
never executed (the execution status of this line is deduced): QRBTree<int>::Node *next = m_edgeList.next(rightmost);
-
1268 if (!next)
never evaluated: !next
0
1269 break;
never executed: break;
0
1270 const Edge &edge = m_edges.at(next->data);
never executed (the execution status of this line is deduced): const Edge &edge = m_edges.at(next->data);
-
1271 const QPodPoint &u = m_parent->m_vertices.at((qint32)edge.from);
never executed (the execution status of this line is deduced): const QPodPoint &u = m_parent->m_vertices.at((qint32)edge.from);
-
1272 const QPodPoint &v = m_parent->m_vertices.at((qint32)edge.to);
never executed (the execution status of this line is deduced): const QPodPoint &v = m_parent->m_vertices.at((qint32)edge.to);
-
1273 if (!currentIntersectionPoint.isOnLine(u, v)) {
never evaluated: !currentIntersectionPoint.isOnLine(u, v)
0
1274 Q_ASSERT(!currentIntersectionPoint.isAccurate() || qCross(currentIntersectionPoint.upperLeft - u, v - u) != 0);
never executed (the execution status of this line is deduced): qt_noop();
-
1275 break;
never executed: break;
0
1276 } -
1277 rightmost = next;
never executed (the execution status of this line is deduced): rightmost = next;
-
1278 }
never executed: }
0
1279 -
1280 Q_ASSERT(leftmost && rightmost);
never executed (the execution status of this line is deduced): qt_noop();
-
1281 splitEdgeListRange(leftmost, rightmost, currentVertex, currentIntersectionPoint);
never executed (the execution status of this line is deduced): splitEdgeListRange(leftmost, rightmost, currentVertex, currentIntersectionPoint);
-
1282 reorderEdgeListRange(leftmost, rightmost);
never executed (the execution status of this line is deduced): reorderEdgeListRange(leftmost, rightmost);
-
1283 -
1284 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= currentIntersectionPoint)
never evaluated: !m_topIntersection.isEmpty()
never evaluated: m_topIntersection.top().intersectionPoint <= currentIntersectionPoint
0
1285 m_topIntersection.pop();
never executed: m_topIntersection.pop();
0
1286 -
1287#ifdef Q_TRIANGULATOR_DEBUG -
1288 DebugDialog dialog(this, intersection.vertex); -
1289 dialog.exec(); -
1290#endif -
1291 -
1292 }
never executed: }
0
1293}
never executed: }
0
1294 -
1295template <typename T> -
1296void QTriangulator<T>::ComplexToSimple::fillPriorityQueue() -
1297{ -
1298 m_events.reset();
never executed (the execution status of this line is deduced): m_events.reset();
-
1299 m_events.reserve(m_edges.size() * 2);
never executed (the execution status of this line is deduced): m_events.reserve(m_edges.size() * 2);
-
1300 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1301 Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1);
never executed (the execution status of this line is deduced): qt_noop();
-
1302 Q_ASSERT(m_edges.at(i).node == 0);
never executed (the execution status of this line is deduced): qt_noop();
-
1303 Q_ASSERT(m_edges.at(i).pointingUp == m_edges.at(i).originallyPointingUp);
never executed (the execution status of this line is deduced): qt_noop();
-
1304 Q_ASSERT(m_edges.at(i).pointingUp == (m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from)));
never executed (the execution status of this line is deduced): qt_noop();
-
1305 // Ignore zero-length edges. -
1306 if (m_parent->m_vertices.at(m_edges.at(i).to) != m_parent->m_vertices.at(m_edges.at(i).from)) {
never evaluated: m_parent->m_vertices.at(m_edges.at(i).to) != m_parent->m_vertices.at(m_edges.at(i).from)
0
1307 QPodPoint upper = m_parent->m_vertices.at(m_edges.at(i).upper());
never executed (the execution status of this line is deduced): QPodPoint upper = m_parent->m_vertices.at(m_edges.at(i).upper());
-
1308 QPodPoint lower = m_parent->m_vertices.at(m_edges.at(i).lower());
never executed (the execution status of this line is deduced): QPodPoint lower = m_parent->m_vertices.at(m_edges.at(i).lower());
-
1309 Event upperEvent = {{upper.x, upper.y}, Event::Upper, i};
never executed (the execution status of this line is deduced): Event upperEvent = {{upper.x, upper.y}, Event::Upper, i};
-
1310 Event lowerEvent = {{lower.x, lower.y}, Event::Lower, i};
never executed (the execution status of this line is deduced): Event lowerEvent = {{lower.x, lower.y}, Event::Lower, i};
-
1311 m_events.add(upperEvent);
never executed (the execution status of this line is deduced): m_events.add(upperEvent);
-
1312 m_events.add(lowerEvent);
never executed (the execution status of this line is deduced): m_events.add(lowerEvent);
-
1313 }
never executed: }
0
1314 }
never executed: }
0
1315 -
1316 std::sort(m_events.data(), m_events.data() + m_events.size());
never executed (the execution status of this line is deduced): std::sort(m_events.data(), m_events.data() + m_events.size());
-
1317}
never executed: }
0
1318 -
1319template <typename T> -
1320void QTriangulator<T>::ComplexToSimple::calculateIntersections() -
1321{ -
1322 fillPriorityQueue();
never executed (the execution status of this line is deduced): fillPriorityQueue();
-
1323 -
1324 Q_ASSERT(m_topIntersection.empty());
never executed (the execution status of this line is deduced): qt_noop();
-
1325 Q_ASSERT(m_edgeList.root == 0);
never executed (the execution status of this line is deduced): qt_noop();
-
1326 -
1327 // Find all intersection points. -
1328 while (!m_events.isEmpty()) {
never evaluated: !m_events.isEmpty()
0
1329 Event event = m_events.last();
never executed (the execution status of this line is deduced): Event event = m_events.last();
-
1330 sortEdgeList(event.point);
never executed (the execution status of this line is deduced): sortEdgeList(event.point);
-
1331 -
1332 // Find all edges in the edge list that contain the current vertex and mark them to be split later. -
1333 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> range = bounds(event.point);
never executed (the execution status of this line is deduced): QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> range = bounds(event.point);
-
1334 QRBTree<int>::Node *leftNode = range.first ? m_edgeList.previous(range.first) : 0;
never evaluated: range.first
0
1335 int vertex = (event.type == Event::Upper ? m_edges.at(event.edge).upper() : m_edges.at(event.edge).lower());
never evaluated: event.type == Event::Upper
0
1336 QIntersectionPoint eventPoint = QT_PREPEND_NAMESPACE(qIntersectionPoint)(event.point);
never executed (the execution status of this line is deduced): QIntersectionPoint eventPoint = ::qIntersectionPoint(event.point);
-
1337 -
1338 if (range.first != 0) {
never evaluated: range.first != 0
0
1339 splitEdgeListRange(range.first, range.second, vertex, eventPoint);
never executed (the execution status of this line is deduced): splitEdgeListRange(range.first, range.second, vertex, eventPoint);
-
1340 reorderEdgeListRange(range.first, range.second);
never executed (the execution status of this line is deduced): reorderEdgeListRange(range.first, range.second);
-
1341 }
never executed: }
0
1342 -
1343 // Handle the edges with start or end point in the current vertex. -
1344 while (!m_events.isEmpty() && m_events.last().point == event.point) {
never evaluated: !m_events.isEmpty()
never evaluated: m_events.last().point == event.point
0
1345 event = m_events.last();
never executed (the execution status of this line is deduced): event = m_events.last();
-
1346 m_events.pop_back();
never executed (the execution status of this line is deduced): m_events.pop_back();
-
1347 int i = event.edge;
never executed (the execution status of this line is deduced): int i = event.edge;
-
1348 -
1349 if (m_edges.at(i).node) {
never evaluated: m_edges.at(i).node
0
1350 // Remove edge from edge list. -
1351 Q_ASSERT(event.type == Event::Lower);
never executed (the execution status of this line is deduced): qt_noop();
-
1352 QRBTree<int>::Node *left = m_edgeList.previous(m_edges.at(i).node);
never executed (the execution status of this line is deduced): QRBTree<int>::Node *left = m_edgeList.previous(m_edges.at(i).node);
-
1353 QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node);
never executed (the execution status of this line is deduced): QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node);
-
1354 m_edgeList.deleteNode(m_edges.at(i).node);
never executed (the execution status of this line is deduced): m_edgeList.deleteNode(m_edges.at(i).node);
-
1355 if (!left || !right)
never evaluated: !left
never evaluated: !right
0
1356 continue;
never executed: continue;
0
1357 calculateIntersection(left->data, right->data);
never executed (the execution status of this line is deduced): calculateIntersection(left->data, right->data);
-
1358 } else {
never executed: }
0
1359 // Insert edge into edge list. -
1360 Q_ASSERT(event.type == Event::Upper);
never executed (the execution status of this line is deduced): qt_noop();
-
1361 QRBTree<int>::Node *left = searchEdgeLeftOf(i, leftNode);
never executed (the execution status of this line is deduced): QRBTree<int>::Node *left = searchEdgeLeftOf(i, leftNode);
-
1362 m_edgeList.attachAfter(left, m_edges.at(i).node = m_edgeList.newNode());
never executed (the execution status of this line is deduced): m_edgeList.attachAfter(left, m_edges.at(i).node = m_edgeList.newNode());
-
1363 m_edges.at(i).node->data = i;
never executed (the execution status of this line is deduced): m_edges.at(i).node->data = i;
-
1364 QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node);
never executed (the execution status of this line is deduced): QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node);
-
1365 if (left)
never evaluated: left
0
1366 calculateIntersection(left->data, i);
never executed: calculateIntersection(left->data, i);
0
1367 if (right)
never evaluated: right
0
1368 calculateIntersection(i, right->data);
never executed: calculateIntersection(i, right->data);
0
1369 }
never executed: }
0
1370 } -
1371 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= eventPoint)
never evaluated: !m_topIntersection.isEmpty()
never evaluated: m_topIntersection.top().intersectionPoint <= eventPoint
0
1372 m_topIntersection.pop();
never executed: m_topIntersection.pop();
0
1373#ifdef Q_TRIANGULATOR_DEBUG -
1374 DebugDialog dialog(this, vertex); -
1375 dialog.exec(); -
1376#endif -
1377 }
never executed: }
0
1378 m_processedEdgePairs.clear();
never executed (the execution status of this line is deduced): m_processedEdgePairs.clear();
-
1379}
never executed: }
0
1380 -
1381// Split an edge into two pieces at the given point. -
1382// The upper piece is pushed to the end of the 'm_edges' vector. -
1383// The lower piece replaces the old edge. -
1384// Return the edge whose 'from' is 'pointIndex'. -
1385template <typename T> -
1386int QTriangulator<T>::ComplexToSimple::splitEdge(int splitIndex) -
1387{ -
1388 const Split &split = m_splits.at(splitIndex);
never executed (the execution status of this line is deduced): const Split &split = m_splits.at(splitIndex);
-
1389 Edge &lowerEdge = m_edges.at(split.edge);
never executed (the execution status of this line is deduced): Edge &lowerEdge = m_edges.at(split.edge);
-
1390 Q_ASSERT(lowerEdge.node == 0);
never executed (the execution status of this line is deduced): qt_noop();
-
1391 Q_ASSERT(lowerEdge.previous == -1 && lowerEdge.next == -1);
never executed (the execution status of this line is deduced): qt_noop();
-
1392 -
1393 if (lowerEdge.from == split.vertex)
never evaluated: lowerEdge.from == split.vertex
0
1394 return split.edge;
never executed: return split.edge;
0
1395 if (lowerEdge.to == split.vertex)
never evaluated: lowerEdge.to == split.vertex
0
1396 return lowerEdge.next;
never executed: return lowerEdge.next;
0
1397 -
1398 // Check that angle >= 90 degrees. -
1399 //Q_ASSERT(qDot(m_points.at(m_edges.at(edgeIndex).from) - m_points.at(pointIndex), -
1400 // m_points.at(m_edges.at(edgeIndex).to) - m_points.at(pointIndex)) <= 0); -
1401 -
1402 Edge upperEdge = lowerEdge;
never executed (the execution status of this line is deduced): Edge upperEdge = lowerEdge;
-
1403 upperEdge.mayIntersect |= !split.accurate; // The edge may have been split before at an inaccurate split point.
never executed (the execution status of this line is deduced): upperEdge.mayIntersect |= !split.accurate;
-
1404 lowerEdge.mayIntersect = !split.accurate;
never executed (the execution status of this line is deduced): lowerEdge.mayIntersect = !split.accurate;
-
1405 if (lowerEdge.pointingUp) {
never evaluated: lowerEdge.pointingUp
0
1406 lowerEdge.to = upperEdge.from = split.vertex;
never executed (the execution status of this line is deduced): lowerEdge.to = upperEdge.from = split.vertex;
-
1407 m_edges.add(upperEdge);
never executed (the execution status of this line is deduced): m_edges.add(upperEdge);
-
1408 return m_edges.size() - 1;
never executed: return m_edges.size() - 1;
0
1409 } else { -
1410 lowerEdge.from = upperEdge.to = split.vertex;
never executed (the execution status of this line is deduced): lowerEdge.from = upperEdge.to = split.vertex;
-
1411 m_edges.add(upperEdge);
never executed (the execution status of this line is deduced): m_edges.add(upperEdge);
-
1412 return split.edge;
never executed: return split.edge;
0
1413 } -
1414} -
1415 -
1416template <typename T> -
1417bool QTriangulator<T>::ComplexToSimple::splitEdgesAtIntersections() -
1418{ -
1419 for (int i = 0; i < m_edges.size(); ++i)
never evaluated: i < m_edges.size()
0
1420 m_edges.at(i).mayIntersect = false;
never executed: m_edges.at(i).mayIntersect = false;
0
1421 bool checkForNewIntersections = false;
never executed (the execution status of this line is deduced): bool checkForNewIntersections = false;
-
1422 for (int i = 0; i < m_splits.size(); ++i) {
never evaluated: i < m_splits.size()
0
1423 splitEdge(i);
never executed (the execution status of this line is deduced): splitEdge(i);
-
1424 checkForNewIntersections |= !m_splits.at(i).accurate;
never executed (the execution status of this line is deduced): checkForNewIntersections |= !m_splits.at(i).accurate;
-
1425 }
never executed: }
0
1426 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1427 m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp =
never executed (the execution status of this line is deduced): m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp =
-
1428 m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from);
never executed (the execution status of this line is deduced): m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from);
-
1429 }
never executed: }
0
1430 m_splits.reset();
never executed (the execution status of this line is deduced): m_splits.reset();
-
1431 return checkForNewIntersections;
never executed: return checkForNewIntersections;
0
1432} -
1433 -
1434template <typename T> -
1435void QTriangulator<T>::ComplexToSimple::insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i) -
1436{ -
1437 // Edges with zero length should not reach this part. -
1438 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(i).from) != m_parent->m_vertices.at(m_edges.at(i).to));
never executed (the execution status of this line is deduced): qt_noop();
-
1439 -
1440 // Skip edges with unwanted winding number. -
1441 int windingNumber = m_edges.at(i).winding;
never executed (the execution status of this line is deduced): int windingNumber = m_edges.at(i).winding;
-
1442 if (m_edges.at(i).originallyPointingUp)
never evaluated: m_edges.at(i).originallyPointingUp
0
1443 ++windingNumber;
never executed: ++windingNumber;
0
1444 -
1445 // Make sure exactly one fill rule is specified. -
1446 Q_ASSERT(((m_parent->m_hint & QVectorPath::WindingFill) != 0) != ((m_parent->m_hint & QVectorPath::OddEvenFill) != 0));
never executed (the execution status of this line is deduced): qt_noop();
-
1447 -
1448 if ((m_parent->m_hint & QVectorPath::WindingFill) && windingNumber != 0 && windingNumber != 1)
never evaluated: (m_parent->m_hint & QVectorPath::WindingFill)
never evaluated: windingNumber != 0
never evaluated: windingNumber != 1
0
1449 return;
never executed: return;
0
1450 -
1451 // Skip cancelling edges. -
1452 if (!orderedEdges.isEmpty()) {
never evaluated: !orderedEdges.isEmpty()
0
1453 int j = orderedEdges[orderedEdges.size() - 1];
never executed (the execution status of this line is deduced): int j = orderedEdges[orderedEdges.size() - 1];
-
1454 // If the last edge is already connected in one end, it should not be cancelled. -
1455 if (m_edges.at(j).next == -1 && m_edges.at(j).previous == -1
never evaluated: m_edges.at(j).next == -1
never evaluated: m_edges.at(j).previous == -1
0
1456 && (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(j).to))
never evaluated: (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(j).to))
0
1457 && (m_parent->m_vertices.at(m_edges.at(i).to) == m_parent->m_vertices.at(m_edges.at(j).from))) {
never evaluated: (m_parent->m_vertices.at(m_edges.at(i).to) == m_parent->m_vertices.at(m_edges.at(j).from))
0
1458 orderedEdges.removeLast();
never executed (the execution status of this line is deduced): orderedEdges.removeLast();
-
1459 return;
never executed: return;
0
1460 } -
1461 }
never executed: }
0
1462 orderedEdges.append(i);
never executed (the execution status of this line is deduced): orderedEdges.append(i);
-
1463}
never executed: }
0
1464 -
1465template <typename T> -
1466void QTriangulator<T>::ComplexToSimple::removeUnwantedEdgesAndConnect() -
1467{ -
1468 Q_ASSERT(m_edgeList.root == 0);
never executed (the execution status of this line is deduced): qt_noop();
-
1469 // Initialize priority queue. -
1470 fillPriorityQueue();
never executed (the execution status of this line is deduced): fillPriorityQueue();
-
1471 -
1472 ShortArray orderedEdges;
never executed (the execution status of this line is deduced): ShortArray orderedEdges;
-
1473 -
1474 while (!m_events.isEmpty()) {
never evaluated: !m_events.isEmpty()
0
1475 Event event = m_events.last();
never executed (the execution status of this line is deduced): Event event = m_events.last();
-
1476 int edgeIndex = event.edge;
never executed (the execution status of this line is deduced): int edgeIndex = event.edge;
-
1477 -
1478 // Check that all the edges in the list crosses the current scanline -
1479 //if (m_edgeList.root) { -
1480 // for (QRBTree<int>::Node *node = m_edgeList.front(m_edgeList.root); node; node = m_edgeList.next(node)) { -
1481 // Q_ASSERT(event.point <= m_points.at(m_edges.at(node->data).lower())); -
1482 // } -
1483 //} -
1484 -
1485 orderedEdges.clear();
never executed (the execution status of this line is deduced): orderedEdges.clear();
-
1486 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> b = outerBounds(event.point);
never executed (the execution status of this line is deduced): QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> b = outerBounds(event.point);
-
1487 if (m_edgeList.root) {
never evaluated: m_edgeList.root
0
1488 QRBTree<int>::Node *current = (b.first ? m_edgeList.next(b.first) : m_edgeList.front(m_edgeList.root));
never evaluated: b.first
0
1489 // Process edges that are going to be removed from the edge list at the current event point. -
1490 while (current != b.second) {
never evaluated: current != b.second
0
1491 Q_ASSERT(current);
never executed (the execution status of this line is deduced): qt_noop();
-
1492 Q_ASSERT(m_edges.at(current->data).node == current);
never executed (the execution status of this line is deduced): qt_noop();
-
1493 Q_ASSERT(QT_PREPEND_NAMESPACE(qIntersectionPoint)(event.point).isOnLine(m_parent->m_vertices.at(m_edges.at(current->data).from), m_parent->m_vertices.at(m_edges.at(current->data).to)));
never executed (the execution status of this line is deduced): qt_noop();
-
1494 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(current->data).from) == event.point || m_parent->m_vertices.at(m_edges.at(current->data).to) == event.point);
never executed (the execution status of this line is deduced): qt_noop();
-
1495 insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
never executed (the execution status of this line is deduced): insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
-
1496 current = m_edgeList.next(current);
never executed (the execution status of this line is deduced): current = m_edgeList.next(current);
-
1497 }
never executed: }
0
1498 }
never executed: }
0
1499 -
1500 // Remove edges above the event point, insert edges below the event point. -
1501 do { -
1502 event = m_events.last();
never executed (the execution status of this line is deduced): event = m_events.last();
-
1503 m_events.pop_back();
never executed (the execution status of this line is deduced): m_events.pop_back();
-
1504 edgeIndex = event.edge;
never executed (the execution status of this line is deduced): edgeIndex = event.edge;
-
1505 -
1506 // Edges with zero length should not reach this part. -
1507 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(edgeIndex).from) != m_parent->m_vertices.at(m_edges.at(edgeIndex).to));
never executed (the execution status of this line is deduced): qt_noop();
-
1508 -
1509 if (m_edges.at(edgeIndex).node) {
never evaluated: m_edges.at(edgeIndex).node
0
1510 Q_ASSERT(event.type == Event::Lower);
never executed (the execution status of this line is deduced): qt_noop();
-
1511 Q_ASSERT(event.point == m_parent->m_vertices.at(m_edges.at(event.edge).lower()));
never executed (the execution status of this line is deduced): qt_noop();
-
1512 m_edgeList.deleteNode(m_edges.at(edgeIndex).node);
never executed (the execution status of this line is deduced): m_edgeList.deleteNode(m_edges.at(edgeIndex).node);
-
1513 } else {
never executed: }
0
1514 Q_ASSERT(event.type == Event::Upper);
never executed (the execution status of this line is deduced): qt_noop();
-
1515 Q_ASSERT(event.point == m_parent->m_vertices.at(m_edges.at(event.edge).upper()));
never executed (the execution status of this line is deduced): qt_noop();
-
1516 QRBTree<int>::Node *left = searchEdgeLeftOf(edgeIndex, b.first);
never executed (the execution status of this line is deduced): QRBTree<int>::Node *left = searchEdgeLeftOf(edgeIndex, b.first);
-
1517 m_edgeList.attachAfter(left, m_edges.at(edgeIndex).node = m_edgeList.newNode());
never executed (the execution status of this line is deduced): m_edgeList.attachAfter(left, m_edges.at(edgeIndex).node = m_edgeList.newNode());
-
1518 m_edges.at(edgeIndex).node->data = edgeIndex;
never executed (the execution status of this line is deduced): m_edges.at(edgeIndex).node->data = edgeIndex;
-
1519 }
never executed: }
0
1520 } while (!m_events.isEmpty() && m_events.last().point == event.point);
never evaluated: !m_events.isEmpty()
never evaluated: m_events.last().point == event.point
0
1521 -
1522 if (m_edgeList.root) {
never evaluated: m_edgeList.root
0
1523 QRBTree<int>::Node *current = (b.first ? m_edgeList.next(b.first) : m_edgeList.front(m_edgeList.root));
never evaluated: b.first
0
1524 -
1525 // Calculate winding number and turn counter-clockwise. -
1526 int currentWindingNumber = (b.first ? m_edges.at(b.first->data).winding : 0);
never evaluated: b.first
0
1527 while (current != b.second) {
never evaluated: current != b.second
0
1528 Q_ASSERT(current);
never executed (the execution status of this line is deduced): qt_noop();
-
1529 //Q_ASSERT(b.second == 0 || m_edgeList.order(current, b.second) < 0); -
1530 int i = current->data;
never executed (the execution status of this line is deduced): int i = current->data;
-
1531 Q_ASSERT(m_edges.at(i).node == current);
never executed (the execution status of this line is deduced): qt_noop();
-
1532 -
1533 // Winding number. -
1534 int ccwWindingNumber = m_edges.at(i).winding = currentWindingNumber;
never executed (the execution status of this line is deduced): int ccwWindingNumber = m_edges.at(i).winding = currentWindingNumber;
-
1535 if (m_edges.at(i).originallyPointingUp) {
never evaluated: m_edges.at(i).originallyPointingUp
0
1536 --m_edges.at(i).winding;
never executed (the execution status of this line is deduced): --m_edges.at(i).winding;
-
1537 } else {
never executed: }
0
1538 ++m_edges.at(i).winding;
never executed (the execution status of this line is deduced): ++m_edges.at(i).winding;
-
1539 ++ccwWindingNumber;
never executed (the execution status of this line is deduced): ++ccwWindingNumber;
-
1540 }
never executed: }
0
1541 currentWindingNumber = m_edges.at(i).winding;
never executed (the execution status of this line is deduced): currentWindingNumber = m_edges.at(i).winding;
-
1542 -
1543 // Turn counter-clockwise. -
1544 if ((ccwWindingNumber & 1) == 0) {
never evaluated: (ccwWindingNumber & 1) == 0
0
1545 Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1);
never executed (the execution status of this line is deduced): qt_noop();
-
1546 qSwap(m_edges.at(i).from, m_edges.at(i).to);
never executed (the execution status of this line is deduced): qSwap(m_edges.at(i).from, m_edges.at(i).to);
-
1547 m_edges.at(i).pointingUp = !m_edges.at(i).pointingUp;
never executed (the execution status of this line is deduced): m_edges.at(i).pointingUp = !m_edges.at(i).pointingUp;
-
1548 }
never executed: }
0
1549 -
1550 current = m_edgeList.next(current);
never executed (the execution status of this line is deduced): current = m_edgeList.next(current);
-
1551 }
never executed: }
0
1552 -
1553 // Process edges that were inserted into the edge list at the current event point. -
1554 current = (b.second ? m_edgeList.previous(b.second) : m_edgeList.back(m_edgeList.root));
never evaluated: b.second
0
1555 while (current != b.first) {
never evaluated: current != b.first
0
1556 Q_ASSERT(current);
never executed (the execution status of this line is deduced): qt_noop();
-
1557 Q_ASSERT(m_edges.at(current->data).node == current);
never executed (the execution status of this line is deduced): qt_noop();
-
1558 insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
never executed (the execution status of this line is deduced): insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
-
1559 current = m_edgeList.previous(current);
never executed (the execution status of this line is deduced): current = m_edgeList.previous(current);
-
1560 }
never executed: }
0
1561 }
never executed: }
0
1562 if (orderedEdges.isEmpty())
never evaluated: orderedEdges.isEmpty()
0
1563 continue;
never executed: continue;
0
1564 -
1565 Q_ASSERT((orderedEdges.size() & 1) == 0);
never executed (the execution status of this line is deduced): qt_noop();
-
1566 -
1567 // Connect edges. -
1568 // First make sure the first edge point towards the current point. -
1569 int i;
never executed (the execution status of this line is deduced): int i;
-
1570 if (m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).from) == event.point) {
never evaluated: m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).from) == event.point
0
1571 i = 1;
never executed (the execution status of this line is deduced): i = 1;
-
1572 int copy = orderedEdges[0]; // Make copy in case the append() will cause a reallocation.
never executed (the execution status of this line is deduced): int copy = orderedEdges[0];
-
1573 orderedEdges.append(copy);
never executed (the execution status of this line is deduced): orderedEdges.append(copy);
-
1574 } else {
never executed: }
0
1575 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).to) == event.point);
never executed (the execution status of this line is deduced): qt_noop();
-
1576 i = 0;
never executed (the execution status of this line is deduced): i = 0;
-
1577 }
never executed: }
0
1578 -
1579 // Remove references to duplicate points. First find the point with lowest index. -
1580 int pointIndex = INT_MAX;
never executed (the execution status of this line is deduced): int pointIndex = 2147483647;
-
1581 for (int j = i; j < orderedEdges.size(); j += 2) {
never evaluated: j < orderedEdges.size()
0
1582 Q_ASSERT(j + 1 < orderedEdges.size());
never executed (the execution status of this line is deduced): qt_noop();
-
1583 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[j]).to) == event.point);
never executed (the execution status of this line is deduced): qt_noop();
-
1584 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[j + 1]).from) == event.point);
never executed (the execution status of this line is deduced): qt_noop();
-
1585 if (m_edges.at(orderedEdges[j]).to < pointIndex)
never evaluated: m_edges.at(orderedEdges[j]).to < pointIndex
0
1586 pointIndex = m_edges.at(orderedEdges[j]).to;
never executed: pointIndex = m_edges.at(orderedEdges[j]).to;
0
1587 if (m_edges.at(orderedEdges[j + 1]).from < pointIndex)
never evaluated: m_edges.at(orderedEdges[j + 1]).from < pointIndex
0
1588 pointIndex = m_edges.at(orderedEdges[j + 1]).from;
never executed: pointIndex = m_edges.at(orderedEdges[j + 1]).from;
0
1589 }
never executed: }
0
1590 -
1591 for (; i < orderedEdges.size(); i += 2) {
never evaluated: i < orderedEdges.size()
0
1592 // Remove references to duplicate points by making all edges reference one common point. -
1593 m_edges.at(orderedEdges[i]).to = m_edges.at(orderedEdges[i + 1]).from = pointIndex;
never executed (the execution status of this line is deduced): m_edges.at(orderedEdges[i]).to = m_edges.at(orderedEdges[i + 1]).from = pointIndex;
-
1594 -
1595 Q_ASSERT(m_edges.at(orderedEdges[i]).pointingUp || m_edges.at(orderedEdges[i]).previous != -1);
never executed (the execution status of this line is deduced): qt_noop();
-
1596 Q_ASSERT(!m_edges.at(orderedEdges[i + 1]).pointingUp || m_edges.at(orderedEdges[i + 1]).next != -1);
never executed (the execution status of this line is deduced): qt_noop();
-
1597 -
1598 m_edges.at(orderedEdges[i]).next = orderedEdges[i + 1];
never executed (the execution status of this line is deduced): m_edges.at(orderedEdges[i]).next = orderedEdges[i + 1];
-
1599 m_edges.at(orderedEdges[i + 1]).previous = orderedEdges[i];
never executed (the execution status of this line is deduced): m_edges.at(orderedEdges[i + 1]).previous = orderedEdges[i];
-
1600 }
never executed: }
0
1601 } // end while
never executed: }
0
1602}
never executed: }
0
1603 -
1604template <typename T> -
1605void QTriangulator<T>::ComplexToSimple::removeUnusedPoints() { -
1606 QBitArray used(m_parent->m_vertices.size(), false);
never executed (the execution status of this line is deduced): QBitArray used(m_parent->m_vertices.size(), false);
-
1607 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1608 Q_ASSERT((m_edges.at(i).previous == -1) == (m_edges.at(i).next == -1));
never executed (the execution status of this line is deduced): qt_noop();
-
1609 if (m_edges.at(i).next != -1)
never evaluated: m_edges.at(i).next != -1
0
1610 used.setBit(m_edges.at(i).from);
never executed: used.setBit(m_edges.at(i).from);
0
1611 }
never executed: }
0
1612 QDataBuffer<quint32> newMapping(m_parent->m_vertices.size());
never executed (the execution status of this line is deduced): QDataBuffer<quint32> newMapping(m_parent->m_vertices.size());
-
1613 newMapping.resize(m_parent->m_vertices.size());
never executed (the execution status of this line is deduced): newMapping.resize(m_parent->m_vertices.size());
-
1614 int count = 0;
never executed (the execution status of this line is deduced): int count = 0;
-
1615 for (int i = 0; i < m_parent->m_vertices.size(); ++i) {
never evaluated: i < m_parent->m_vertices.size()
0
1616 if (used.at(i)) {
never evaluated: used.at(i)
0
1617 m_parent->m_vertices.at(count) = m_parent->m_vertices.at(i);
never executed (the execution status of this line is deduced): m_parent->m_vertices.at(count) = m_parent->m_vertices.at(i);
-
1618 newMapping.at(i) = count;
never executed (the execution status of this line is deduced): newMapping.at(i) = count;
-
1619 ++count;
never executed (the execution status of this line is deduced): ++count;
-
1620 }
never executed: }
0
1621 }
never executed: }
0
1622 m_parent->m_vertices.resize(count);
never executed (the execution status of this line is deduced): m_parent->m_vertices.resize(count);
-
1623 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1624 m_edges.at(i).from = newMapping.at(m_edges.at(i).from);
never executed (the execution status of this line is deduced): m_edges.at(i).from = newMapping.at(m_edges.at(i).from);
-
1625 m_edges.at(i).to = newMapping.at(m_edges.at(i).to);
never executed (the execution status of this line is deduced): m_edges.at(i).to = newMapping.at(m_edges.at(i).to);
-
1626 }
never executed: }
0
1627}
never executed: }
0
1628 -
1629template <typename T> -
1630inline bool QTriangulator<T>::ComplexToSimple::Event::operator < (const Event &other) const -
1631{ -
1632 if (point == other.point)
never evaluated: point == other.point
0
1633 return type < other.type; // 'Lower' has higher priority than 'Upper'.
never executed: return type < other.type;
0
1634 return other.point < point;
never executed: return other.point < point;
0
1635} -
1636 -
1637//============================================================================// -
1638// QTriangulator::ComplexToSimple::DebugDialog // -
1639//============================================================================// -
1640 -
1641#ifdef Q_TRIANGULATOR_DEBUG -
1642template <typename T> -
1643QTriangulator<T>::ComplexToSimple::DebugDialog::DebugDialog(ComplexToSimple *parent, int currentVertex) -
1644 : m_parent(parent), m_vertex(currentVertex) -
1645{ -
1646 QDataBuffer<QPodPoint> &vertices = m_parent->m_parent->m_vertices; -
1647 if (vertices.isEmpty()) -
1648 return; -
1649 -
1650 int minX, maxX, minY, maxY; -
1651 minX = maxX = vertices.at(0).x; -
1652 minY = maxY = vertices.at(0).y; -
1653 for (int i = 1; i < vertices.size(); ++i) { -
1654 minX = qMin(minX, vertices.at(i).x); -
1655 maxX = qMax(maxX, vertices.at(i).x); -
1656 minY = qMin(minY, vertices.at(i).y); -
1657 maxY = qMax(maxY, vertices.at(i).y); -
1658 } -
1659 int w = maxX - minX; -
1660 int h = maxY - minY; -
1661 qreal border = qMin(w, h) / 10.0; -
1662 m_window = QRectF(minX - border, minY - border, (maxX - minX + 2 * border), (maxY - minY + 2 * border)); -
1663} -
1664 -
1665template <typename T> -
1666void QTriangulator<T>::ComplexToSimple::DebugDialog::paintEvent(QPaintEvent *) -
1667{ -
1668 QPainter p(this); -
1669 p.setRenderHint(QPainter::Antialiasing, true); -
1670 p.fillRect(rect(), Qt::black); -
1671 QDataBuffer<QPodPoint> &vertices = m_parent->m_parent->m_vertices; -
1672 if (vertices.isEmpty()) -
1673 return; -
1674 -
1675 qreal halfPointSize = qMin(m_window.width(), m_window.height()) / 300.0; -
1676 p.setWindow(m_window.toRect()); -
1677 -
1678 p.setPen(Qt::white); -
1679 -
1680 QDataBuffer<Edge> &edges = m_parent->m_edges; -
1681 for (int i = 0; i < edges.size(); ++i) { -
1682 QPodPoint u = vertices.at(edges.at(i).from); -
1683 QPodPoint v = vertices.at(edges.at(i).to); -
1684 p.drawLine(u.x, u.y, v.x, v.y); -
1685 } -
1686 -
1687 for (int i = 0; i < vertices.size(); ++i) { -
1688 QPodPoint q = vertices.at(i); -
1689 p.fillRect(QRectF(q.x - halfPointSize, q.y - halfPointSize, 2 * halfPointSize, 2 * halfPointSize), Qt::red); -
1690 } -
1691 -
1692 Qt::GlobalColor colors[6] = {Qt::red, Qt::green, Qt::blue, Qt::cyan, Qt::magenta, Qt::yellow}; -
1693 p.setOpacity(0.5); -
1694 int count = 0; -
1695 if (m_parent->m_edgeList.root) { -
1696 QRBTree<int>::Node *current = m_parent->m_edgeList.front(m_parent->m_edgeList.root); -
1697 while (current) { -
1698 p.setPen(colors[count++ % 6]); -
1699 QPodPoint u = vertices.at(edges.at(current->data).from); -
1700 QPodPoint v = vertices.at(edges.at(current->data).to); -
1701 p.drawLine(u.x, u.y, v.x, v.y); -
1702 current = m_parent->m_edgeList.next(current); -
1703 } -
1704 } -
1705 -
1706 p.setOpacity(1.0); -
1707 QPodPoint q = vertices.at(m_vertex); -
1708 p.fillRect(QRectF(q.x - halfPointSize, q.y - halfPointSize, 2 * halfPointSize, 2 * halfPointSize), Qt::green); -
1709 -
1710 p.setPen(Qt::gray); -
1711 QDataBuffer<Split> &splits = m_parent->m_splits; -
1712 for (int i = 0; i < splits.size(); ++i) { -
1713 QPodPoint q = vertices.at(splits.at(i).vertex); -
1714 QPodPoint u = vertices.at(edges.at(splits.at(i).edge).from) - q; -
1715 QPodPoint v = vertices.at(edges.at(splits.at(i).edge).to) - q; -
1716 qreal uLen = sqrt(qreal(qDot(u, u))); -
1717 qreal vLen = sqrt(qreal(qDot(v, v))); -
1718 if (uLen) { -
1719 u.x *= 2 * halfPointSize / uLen; -
1720 u.y *= 2 * halfPointSize / uLen; -
1721 } -
1722 if (vLen) { -
1723 v.x *= 2 * halfPointSize / vLen; -
1724 v.y *= 2 * halfPointSize / vLen; -
1725 } -
1726 u += q; -
1727 v += q; -
1728 p.drawLine(u.x, u.y, v.x, v.y); -
1729 } -
1730} -
1731 -
1732template <typename T> -
1733void QTriangulator<T>::ComplexToSimple::DebugDialog::wheelEvent(QWheelEvent *event) -
1734{ -
1735 qreal scale = exp(-0.001 * event->delta()); -
1736 QPointF center = m_window.center(); -
1737 QPointF delta = scale * (m_window.bottomRight() - center); -
1738 m_window = QRectF(center - delta, center + delta); -
1739 event->accept(); -
1740 update(); -
1741} -
1742 -
1743template <typename T> -
1744void QTriangulator<T>::ComplexToSimple::DebugDialog::mouseMoveEvent(QMouseEvent *event) -
1745{ -
1746 if (event->buttons() & Qt::LeftButton) { -
1747 QPointF delta = event->pos() - m_lastMousePos; -
1748 delta.setX(delta.x() * m_window.width() / width()); -
1749 delta.setY(delta.y() * m_window.height() / height()); -
1750 m_window.translate(-delta.x(), -delta.y()); -
1751 m_lastMousePos = event->pos(); -
1752 event->accept(); -
1753 update(); -
1754 } -
1755} -
1756 -
1757template <typename T> -
1758void QTriangulator<T>::ComplexToSimple::DebugDialog::mousePressEvent(QMouseEvent *event) -
1759{ -
1760 if (event->button() == Qt::LeftButton) -
1761 m_lastMousePos = event->pos(); -
1762 event->accept(); -
1763} -
1764 -
1765 -
1766#endif -
1767 -
1768//============================================================================// -
1769// QTriangulator::SimpleToMonotone // -
1770//============================================================================// -
1771template <typename T> -
1772void QTriangulator<T>::SimpleToMonotone::decompose() -
1773{ -
1774 setupDataStructures();
never executed (the execution status of this line is deduced): setupDataStructures();
-
1775 removeZeroLengthEdges();
never executed (the execution status of this line is deduced): removeZeroLengthEdges();
-
1776 monotoneDecomposition();
never executed (the execution status of this line is deduced): monotoneDecomposition();
-
1777 -
1778 m_parent->m_indices.clear();
never executed (the execution status of this line is deduced): m_parent->m_indices.clear();
-
1779 QBitArray processed(m_edges.size(), false);
never executed (the execution status of this line is deduced): QBitArray processed(m_edges.size(), false);
-
1780 for (int first = 0; first < m_edges.size(); ++first) {
never evaluated: first < m_edges.size()
0
1781 if (processed.at(first))
never evaluated: processed.at(first)
0
1782 continue;
never executed: continue;
0
1783 int i = first;
never executed (the execution status of this line is deduced): int i = first;
-
1784 do { -
1785 Q_ASSERT(!processed.at(i));
never executed (the execution status of this line is deduced): qt_noop();
-
1786 Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i);
never executed (the execution status of this line is deduced): qt_noop();
-
1787 m_parent->m_indices.push_back(m_edges.at(i).from);
never executed (the execution status of this line is deduced): m_parent->m_indices.push_back(m_edges.at(i).from);
-
1788 processed.setBit(i);
never executed (the execution status of this line is deduced): processed.setBit(i);
-
1789 i = m_edges.at(i).next;
never executed (the execution status of this line is deduced): i = m_edges.at(i).next;
-
1790 } while (i != first);
never executed: }
never evaluated: i != first
0
1791 if (m_parent->m_indices.size() > 0 && m_parent->m_indices.back() != T(-1)) // Q_TRIANGULATE_END_OF_POLYGON
never evaluated: m_parent->m_indices.size() > 0
never evaluated: m_parent->m_indices.back() != T(-1)
0
1792 m_parent->m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
never executed: m_parent->m_indices.push_back(T(-1));
0
1793 }
never executed: }
0
1794}
never executed: }
0
1795 -
1796template <typename T> -
1797void QTriangulator<T>::SimpleToMonotone::setupDataStructures() -
1798{ -
1799 int i = 0;
never executed (the execution status of this line is deduced): int i = 0;
-
1800 Edge e;
never executed (the execution status of this line is deduced): Edge e;
-
1801 e.node = 0;
never executed (the execution status of this line is deduced): e.node = 0;
-
1802 e.twin = -1;
never executed (the execution status of this line is deduced): e.twin = -1;
-
1803 -
1804 while (i + 3 <= m_parent->m_indices.size()) {
never evaluated: i + 3 <= m_parent->m_indices.size()
0
1805 int start = m_edges.size();
never executed (the execution status of this line is deduced): int start = m_edges.size();
-
1806 -
1807 do { -
1808 e.from = m_parent->m_indices.at(i);
never executed (the execution status of this line is deduced): e.from = m_parent->m_indices.at(i);
-
1809 e.type = RegularVertex;
never executed (the execution status of this line is deduced): e.type = RegularVertex;
-
1810 e.next = m_edges.size() + 1;
never executed (the execution status of this line is deduced): e.next = m_edges.size() + 1;
-
1811 e.previous = m_edges.size() - 1;
never executed (the execution status of this line is deduced): e.previous = m_edges.size() - 1;
-
1812 m_edges.add(e);
never executed (the execution status of this line is deduced): m_edges.add(e);
-
1813 ++i;
never executed (the execution status of this line is deduced): ++i;
-
1814 Q_ASSERT(i < m_parent->m_indices.size());
never executed (the execution status of this line is deduced): qt_noop();
-
1815 } while (m_parent->m_indices.at(i) != T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
never executed: }
never evaluated: m_parent->m_indices.at(i) != T(-1)
0
1816 -
1817 m_edges.last().next = start;
never executed (the execution status of this line is deduced): m_edges.last().next = start;
-
1818 m_edges.at(start).previous = m_edges.size() - 1;
never executed (the execution status of this line is deduced): m_edges.at(start).previous = m_edges.size() - 1;
-
1819 ++i; // Skip Q_TRIANGULATE_END_OF_POLYGON.
never executed (the execution status of this line is deduced): ++i;
-
1820 }
never executed: }
0
1821 -
1822 for (i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1823 m_edges.at(i).to = m_edges.at(m_edges.at(i).next).from;
never executed (the execution status of this line is deduced): m_edges.at(i).to = m_edges.at(m_edges.at(i).next).from;
-
1824 m_edges.at(i).pointingUp = m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from);
never executed (the execution status of this line is deduced): m_edges.at(i).pointingUp = m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from);
-
1825 m_edges.at(i).helper = -1; // Not initialized here.
never executed (the execution status of this line is deduced): m_edges.at(i).helper = -1;
-
1826 }
never executed: }
0
1827}
never executed: }
0
1828 -
1829template <typename T> -
1830void QTriangulator<T>::SimpleToMonotone::removeZeroLengthEdges() -
1831{ -
1832 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1833 if (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(i).to)) {
never evaluated: m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(i).to)
0
1834 m_edges.at(m_edges.at(i).previous).next = m_edges.at(i).next;
never executed (the execution status of this line is deduced): m_edges.at(m_edges.at(i).previous).next = m_edges.at(i).next;
-
1835 m_edges.at(m_edges.at(i).next).previous = m_edges.at(i).previous;
never executed (the execution status of this line is deduced): m_edges.at(m_edges.at(i).next).previous = m_edges.at(i).previous;
-
1836 m_edges.at(m_edges.at(i).next).from = m_edges.at(i).from;
never executed (the execution status of this line is deduced): m_edges.at(m_edges.at(i).next).from = m_edges.at(i).from;
-
1837 m_edges.at(i).next = -1; // Mark as removed.
never executed (the execution status of this line is deduced): m_edges.at(i).next = -1;
-
1838 }
never executed: }
0
1839 }
never executed: }
0
1840 -
1841 QDataBuffer<int> newMapping(m_edges.size());
never executed (the execution status of this line is deduced): QDataBuffer<int> newMapping(m_edges.size());
-
1842 newMapping.resize(m_edges.size());
never executed (the execution status of this line is deduced): newMapping.resize(m_edges.size());
-
1843 int count = 0;
never executed (the execution status of this line is deduced): int count = 0;
-
1844 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1845 if (m_edges.at(i).next != -1) {
never evaluated: m_edges.at(i).next != -1
0
1846 m_edges.at(count) = m_edges.at(i);
never executed (the execution status of this line is deduced): m_edges.at(count) = m_edges.at(i);
-
1847 newMapping.at(i) = count;
never executed (the execution status of this line is deduced): newMapping.at(i) = count;
-
1848 ++count;
never executed (the execution status of this line is deduced): ++count;
-
1849 }
never executed: }
0
1850 }
never executed: }
0
1851 m_edges.resize(count);
never executed (the execution status of this line is deduced): m_edges.resize(count);
-
1852 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1853 m_edges.at(i).next = newMapping.at(m_edges.at(i).next);
never executed (the execution status of this line is deduced): m_edges.at(i).next = newMapping.at(m_edges.at(i).next);
-
1854 m_edges.at(i).previous = newMapping.at(m_edges.at(i).previous);
never executed (the execution status of this line is deduced): m_edges.at(i).previous = newMapping.at(m_edges.at(i).previous);
-
1855 }
never executed: }
0
1856}
never executed: }
0
1857 -
1858template <typename T> -
1859void QTriangulator<T>::SimpleToMonotone::fillPriorityQueue() -
1860{ -
1861 m_upperVertex.reset();
never executed (the execution status of this line is deduced): m_upperVertex.reset();
-
1862 m_upperVertex.reserve(m_edges.size());
never executed (the execution status of this line is deduced): m_upperVertex.reserve(m_edges.size());
-
1863 for (int i = 0; i < m_edges.size(); ++i)
never evaluated: i < m_edges.size()
0
1864 m_upperVertex.add(i);
never executed: m_upperVertex.add(i);
0
1865 CompareVertices cmp(this);
never executed (the execution status of this line is deduced): CompareVertices cmp(this);
-
1866 std::sort(m_upperVertex.data(), m_upperVertex.data() + m_upperVertex.size(), cmp);
never executed (the execution status of this line is deduced): std::sort(m_upperVertex.data(), m_upperVertex.data() + m_upperVertex.size(), cmp);
-
1867 //for (int i = 1; i < m_upperVertex.size(); ++i) { -
1868 // Q_ASSERT(!cmp(m_upperVertex.at(i), m_upperVertex.at(i - 1))); -
1869 //} -
1870}
never executed: }
0
1871 -
1872template <typename T> -
1873bool QTriangulator<T>::SimpleToMonotone::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const -
1874{ -
1875 const Edge &leftEdge = m_edges.at(leftEdgeIndex);
never executed (the execution status of this line is deduced): const Edge &leftEdge = m_edges.at(leftEdgeIndex);
-
1876 const Edge &rightEdge = m_edges.at(rightEdgeIndex);
never executed (the execution status of this line is deduced): const Edge &rightEdge = m_edges.at(rightEdgeIndex);
-
1877 const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
never executed (the execution status of this line is deduced): const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
-
1878 const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
never executed (the execution status of this line is deduced): const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
-
1879 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(leftEdge.upper()), l, u);
never executed (the execution status of this line is deduced): qint64 d = ::qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.upper()), l, u);
-
1880 // d < 0: left, d > 0: right, d == 0: on top -
1881 if (d == 0)
never evaluated: d == 0
0
1882 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(leftEdge.lower()), l, u);
never executed: d = ::qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.lower()), l, u);
0
1883 return d < 0;
never executed: return d < 0;
0
1884} -
1885 -
1886// Returns the rightmost edge not to the right of the given edge. -
1887template <typename T> -
1888QRBTree<int>::Node *QTriangulator<T>::SimpleToMonotone::searchEdgeLeftOfEdge(int edgeIndex) const -
1889{ -
1890 QRBTree<int>::Node *current = m_edgeList.root;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *current = m_edgeList.root;
-
1891 QRBTree<int>::Node *result = 0;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *result = 0;
-
1892 while (current) {
never evaluated: current
0
1893 if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
never evaluated: edgeIsLeftOfEdge(edgeIndex, current->data)
0
1894 current = current->left;
never executed (the execution status of this line is deduced): current = current->left;
-
1895 } else {
never executed: }
0
1896 result = current;
never executed (the execution status of this line is deduced): result = current;
-
1897 current = current->right;
never executed (the execution status of this line is deduced): current = current->right;
-
1898 }
never executed: }
0
1899 } -
1900 return result;
never executed: return result;
0
1901} -
1902 -
1903// Returns the rightmost edge left of the given point. -
1904template <typename T> -
1905QRBTree<int>::Node *QTriangulator<T>::SimpleToMonotone::searchEdgeLeftOfPoint(int pointIndex) const -
1906{ -
1907 QRBTree<int>::Node *current = m_edgeList.root;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *current = m_edgeList.root;
-
1908 QRBTree<int>::Node *result = 0;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *result = 0;
-
1909 while (current) {
never evaluated: current
0
1910 const QPodPoint &p1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
never executed (the execution status of this line is deduced): const QPodPoint &p1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
-
1911 const QPodPoint &p2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
never executed (the execution status of this line is deduced): const QPodPoint &p2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
-
1912 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(pointIndex), p1, p2);
never executed (the execution status of this line is deduced): qint64 d = ::qPointDistanceFromLine(m_parent->m_vertices.at(pointIndex), p1, p2);
-
1913 if (d <= 0) {
never evaluated: d <= 0
0
1914 current = current->left;
never executed (the execution status of this line is deduced): current = current->left;
-
1915 } else {
never executed: }
0
1916 result = current;
never executed (the execution status of this line is deduced): result = current;
-
1917 current = current->right;
never executed (the execution status of this line is deduced): current = current->right;
-
1918 }
never executed: }
0
1919 } -
1920 return result;
never executed: return result;
0
1921} -
1922 -
1923template <typename T> -
1924void QTriangulator<T>::SimpleToMonotone::classifyVertex(int i) -
1925{ -
1926 Edge &e2 = m_edges.at(i);
never executed (the execution status of this line is deduced): Edge &e2 = m_edges.at(i);
-
1927 const Edge &e1 = m_edges.at(e2.previous);
never executed (the execution status of this line is deduced): const Edge &e1 = m_edges.at(e2.previous);
-
1928 -
1929 bool startOrSplit = (e1.pointingUp && !e2.pointingUp);
never evaluated: e1.pointingUp
never evaluated: !e2.pointingUp
0
1930 bool endOrMerge = (!e1.pointingUp && e2.pointingUp);
never evaluated: !e1.pointingUp
never evaluated: e2.pointingUp
0
1931 -
1932 const QPodPoint &p1 = m_parent->m_vertices.at(e1.from);
never executed (the execution status of this line is deduced): const QPodPoint &p1 = m_parent->m_vertices.at(e1.from);
-
1933 const QPodPoint &p2 = m_parent->m_vertices.at(e2.from);
never executed (the execution status of this line is deduced): const QPodPoint &p2 = m_parent->m_vertices.at(e2.from);
-
1934 const QPodPoint &p3 = m_parent->m_vertices.at(e2.to);
never executed (the execution status of this line is deduced): const QPodPoint &p3 = m_parent->m_vertices.at(e2.to);
-
1935 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(p1, p2, p3);
never executed (the execution status of this line is deduced): qint64 d = ::qPointDistanceFromLine(p1, p2, p3);
-
1936 Q_ASSERT(d != 0 || (!startOrSplit && !endOrMerge));
never executed (the execution status of this line is deduced): qt_noop();
-
1937 -
1938 e2.type = RegularVertex;
never executed (the execution status of this line is deduced): e2.type = RegularVertex;
-
1939 -
1940 if (m_clockwiseOrder) {
never evaluated: m_clockwiseOrder
0
1941 if (startOrSplit)
never evaluated: startOrSplit
0
1942 e2.type = (d < 0 ? SplitVertex : StartVertex);
never executed: e2.type = (d < 0 ? SplitVertex : StartVertex);
never evaluated: d < 0
0
1943 else if (endOrMerge)
never evaluated: endOrMerge
0
1944 e2.type = (d < 0 ? MergeVertex : EndVertex);
never executed: e2.type = (d < 0 ? MergeVertex : EndVertex);
never evaluated: d < 0
0
1945 } else { -
1946 if (startOrSplit)
never evaluated: startOrSplit
0
1947 e2.type = (d > 0 ? SplitVertex : StartVertex);
never executed: e2.type = (d > 0 ? SplitVertex : StartVertex);
never evaluated: d > 0
0
1948 else if (endOrMerge)
never evaluated: endOrMerge
0
1949 e2.type = (d > 0 ? MergeVertex : EndVertex);
never executed: e2.type = (d > 0 ? MergeVertex : EndVertex);
never evaluated: d > 0
0
1950 } -
1951} -
1952 -
1953template <typename T> -
1954void QTriangulator<T>::SimpleToMonotone::classifyVertices() -
1955{ -
1956 for (int i = 0; i < m_edges.size(); ++i)
never evaluated: i < m_edges.size()
0
1957 classifyVertex(i);
never executed: classifyVertex(i);
0
1958}
never executed: }
0
1959 -
1960template <typename T> -
1961bool QTriangulator<T>::SimpleToMonotone::pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3) -
1962{ -
1963 bool leftOfPreviousEdge = !qPointIsLeftOfLine(p, v2, v1);
never executed (the execution status of this line is deduced): bool leftOfPreviousEdge = !qPointIsLeftOfLine(p, v2, v1);
-
1964 bool leftOfNextEdge = !qPointIsLeftOfLine(p, v3, v2);
never executed (the execution status of this line is deduced): bool leftOfNextEdge = !qPointIsLeftOfLine(p, v3, v2);
-
1965 -
1966 if (qPointIsLeftOfLine(v1, v2, v3))
never evaluated: qPointIsLeftOfLine(v1, v2, v3)
0
1967 return leftOfPreviousEdge && leftOfNextEdge;
never executed: return leftOfPreviousEdge && leftOfNextEdge;
0
1968 else -
1969 return leftOfPreviousEdge || leftOfNextEdge;
never executed: return leftOfPreviousEdge || leftOfNextEdge;
0
1970} -
1971 -
1972template <typename T> -
1973bool QTriangulator<T>::SimpleToMonotone::pointIsInSector(int vertex, int sector) -
1974{ -
1975 const QPodPoint &center = m_parent->m_vertices.at(m_edges.at(sector).from);
never executed (the execution status of this line is deduced): const QPodPoint &center = m_parent->m_vertices.at(m_edges.at(sector).from);
-
1976 // Handle degenerate edges. -
1977 while (m_parent->m_vertices.at(m_edges.at(vertex).from) == center)
never evaluated: m_parent->m_vertices.at(m_edges.at(vertex).from) == center
0
1978 vertex = m_edges.at(vertex).next;
never executed: vertex = m_edges.at(vertex).next;
0
1979 int next = m_edges.at(sector).next;
never executed (the execution status of this line is deduced): int next = m_edges.at(sector).next;
-
1980 while (m_parent->m_vertices.at(m_edges.at(next).from) == center)
never evaluated: m_parent->m_vertices.at(m_edges.at(next).from) == center
0
1981 next = m_edges.at(next).next;
never executed: next = m_edges.at(next).next;
0
1982 int previous = m_edges.at(sector).previous;
never executed (the execution status of this line is deduced): int previous = m_edges.at(sector).previous;
-
1983 while (m_parent->m_vertices.at(m_edges.at(previous).from) == center)
never evaluated: m_parent->m_vertices.at(m_edges.at(previous).from) == center
0
1984 previous = m_edges.at(previous).previous;
never executed: previous = m_edges.at(previous).previous;
0
1985 -
1986 const QPodPoint &p = m_parent->m_vertices.at(m_edges.at(vertex).from);
never executed (the execution status of this line is deduced): const QPodPoint &p = m_parent->m_vertices.at(m_edges.at(vertex).from);
-
1987 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(previous).from);
never executed (the execution status of this line is deduced): const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(previous).from);
-
1988 const QPodPoint &v3 = m_parent->m_vertices.at(m_edges.at(next).from);
never executed (the execution status of this line is deduced): const QPodPoint &v3 = m_parent->m_vertices.at(m_edges.at(next).from);
-
1989 if (m_clockwiseOrder)
never evaluated: m_clockwiseOrder
0
1990 return pointIsInSector(p, v3, center, v1);
never executed: return pointIsInSector(p, v3, center, v1);
0
1991 else -
1992 return pointIsInSector(p, v1, center, v3);
never executed: return pointIsInSector(p, v1, center, v3);
0
1993} -
1994 -
1995template <typename T> -
1996int QTriangulator<T>::SimpleToMonotone::findSector(int edge, int vertex) -
1997{ -
1998 while (!pointIsInSector(vertex, edge)) {
never evaluated: !pointIsInSector(vertex, edge)
0
1999 edge = m_edges.at(m_edges.at(edge).previous).twin;
never executed (the execution status of this line is deduced): edge = m_edges.at(m_edges.at(edge).previous).twin;
-
2000 Q_ASSERT(edge != -1);
never executed (the execution status of this line is deduced): qt_noop();
-
2001 }
never executed: }
0
2002 return edge;
never executed: return edge;
0
2003} -
2004 -
2005template <typename T> -
2006void QTriangulator<T>::SimpleToMonotone::createDiagonal(int lower, int upper) -
2007{ -
2008 lower = findSector(lower, upper);
never executed (the execution status of this line is deduced): lower = findSector(lower, upper);
-
2009 upper = findSector(upper, lower);
never executed (the execution status of this line is deduced): upper = findSector(upper, lower);
-
2010 -
2011 int prevLower = m_edges.at(lower).previous;
never executed (the execution status of this line is deduced): int prevLower = m_edges.at(lower).previous;
-
2012 int prevUpper = m_edges.at(upper).previous;
never executed (the execution status of this line is deduced): int prevUpper = m_edges.at(upper).previous;
-
2013 -
2014 Edge e;
never executed (the execution status of this line is deduced): Edge e;
-
2015 -
2016 e.twin = m_edges.size() + 1;
never executed (the execution status of this line is deduced): e.twin = m_edges.size() + 1;
-
2017 e.next = upper;
never executed (the execution status of this line is deduced): e.next = upper;
-
2018 e.previous = prevLower;
never executed (the execution status of this line is deduced): e.previous = prevLower;
-
2019 e.from = m_edges.at(lower).from;
never executed (the execution status of this line is deduced): e.from = m_edges.at(lower).from;
-
2020 e.to = m_edges.at(upper).from;
never executed (the execution status of this line is deduced): e.to = m_edges.at(upper).from;
-
2021 m_edges.at(upper).previous = m_edges.at(prevLower).next = int(m_edges.size());
never executed (the execution status of this line is deduced): m_edges.at(upper).previous = m_edges.at(prevLower).next = int(m_edges.size());
-
2022 m_edges.add(e);
never executed (the execution status of this line is deduced): m_edges.add(e);
-
2023 -
2024 e.twin = m_edges.size() - 1;
never executed (the execution status of this line is deduced): e.twin = m_edges.size() - 1;
-
2025 e.next = lower;
never executed (the execution status of this line is deduced): e.next = lower;
-
2026 e.previous = prevUpper;
never executed (the execution status of this line is deduced): e.previous = prevUpper;
-
2027 e.from = m_edges.at(upper).from;
never executed (the execution status of this line is deduced): e.from = m_edges.at(upper).from;
-
2028 e.to = m_edges.at(lower).from;
never executed (the execution status of this line is deduced): e.to = m_edges.at(lower).from;
-
2029 m_edges.at(lower).previous = m_edges.at(prevUpper).next = int(m_edges.size());
never executed (the execution status of this line is deduced): m_edges.at(lower).previous = m_edges.at(prevUpper).next = int(m_edges.size());
-
2030 m_edges.add(e);
never executed (the execution status of this line is deduced): m_edges.add(e);
-
2031}
never executed: }
0
2032 -
2033template <typename T> -
2034void QTriangulator<T>::SimpleToMonotone::monotoneDecomposition() -
2035{ -
2036 if (m_edges.isEmpty())
never evaluated: m_edges.isEmpty()
0
2037 return;
never executed: return;
0
2038 -
2039 Q_ASSERT(!m_edgeList.root);
never executed (the execution status of this line is deduced): qt_noop();
-
2040 QDataBuffer<QPair<int, int> > diagonals(m_upperVertex.size());
never executed (the execution status of this line is deduced): QDataBuffer<QPair<int, int> > diagonals(m_upperVertex.size());
-
2041 -
2042 int i = 0;
never executed (the execution status of this line is deduced): int i = 0;
-
2043 for (int index = 1; index < m_edges.size(); ++index) {
never evaluated: index < m_edges.size()
0
2044 if (m_parent->m_vertices.at(m_edges.at(index).from) < m_parent->m_vertices.at(m_edges.at(i).from))
never evaluated: m_parent->m_vertices.at(m_edges.at(index).from) < m_parent->m_vertices.at(m_edges.at(i).from)
0
2045 i = index;
never executed: i = index;
0
2046 }
never executed: }
0
2047 Q_ASSERT(i < m_edges.size());
never executed (the execution status of this line is deduced): qt_noop();
-
2048 int j = m_edges.at(i).previous;
never executed (the execution status of this line is deduced): int j = m_edges.at(i).previous;
-
2049 Q_ASSERT(j < m_edges.size());
never executed (the execution status of this line is deduced): qt_noop();
-
2050 m_clockwiseOrder = qPointIsLeftOfLine(m_parent->m_vertices.at((quint32)m_edges.at(i).from),
never executed (the execution status of this line is deduced): m_clockwiseOrder = qPointIsLeftOfLine(m_parent->m_vertices.at((quint32)m_edges.at(i).from),
-
2051 m_parent->m_vertices.at((quint32)m_edges.at(j).from), m_parent->m_vertices.at((quint32)m_edges.at(i).to));
never executed (the execution status of this line is deduced): m_parent->m_vertices.at((quint32)m_edges.at(j).from), m_parent->m_vertices.at((quint32)m_edges.at(i).to));
-
2052 -
2053 classifyVertices();
never executed (the execution status of this line is deduced): classifyVertices();
-
2054 fillPriorityQueue();
never executed (the execution status of this line is deduced): fillPriorityQueue();
-
2055 -
2056 // debug: set helpers explicitly (shouldn't be necessary) -
2057 //for (int i = 0; i < m_edges.size(); ++i) -
2058 // m_edges.at(i).helper = m_edges.at(i).upper(); -
2059 -
2060 while (!m_upperVertex.isEmpty()) {
never evaluated: !m_upperVertex.isEmpty()
0
2061 i = m_upperVertex.last();
never executed (the execution status of this line is deduced): i = m_upperVertex.last();
-
2062 Q_ASSERT(i < m_edges.size());
never executed (the execution status of this line is deduced): qt_noop();
-
2063 m_upperVertex.pop_back();
never executed (the execution status of this line is deduced): m_upperVertex.pop_back();
-
2064 j = m_edges.at(i).previous;
never executed (the execution status of this line is deduced): j = m_edges.at(i).previous;
-
2065 Q_ASSERT(j < m_edges.size());
never executed (the execution status of this line is deduced): qt_noop();
-
2066 -
2067 QRBTree<int>::Node *leftEdgeNode = 0;
never executed (the execution status of this line is deduced): QRBTree<int>::Node *leftEdgeNode = 0;
-
2068 -
2069 switch (m_edges.at(i).type) { -
2070 case RegularVertex: -
2071 // If polygon interior is to the right of the vertex... -
2072 if (m_edges.at(i).pointingUp == m_clockwiseOrder) {
never evaluated: m_edges.at(i).pointingUp == m_clockwiseOrder
0
2073 if (m_edges.at(i).node) {
never evaluated: m_edges.at(i).node
0
2074 Q_ASSERT(!m_edges.at(j).node);
never executed (the execution status of this line is deduced): qt_noop();
-
2075 if (m_edges.at(m_edges.at(i).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(i).helper).type == MergeVertex
0
2076 diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
0
2077 m_edges.at(j).node = m_edges.at(i).node;
never executed (the execution status of this line is deduced): m_edges.at(j).node = m_edges.at(i).node;
-
2078 m_edges.at(i).node = 0;
never executed (the execution status of this line is deduced): m_edges.at(i).node = 0;
-
2079 m_edges.at(j).node->data = j;
never executed (the execution status of this line is deduced): m_edges.at(j).node->data = j;
-
2080 m_edges.at(j).helper = i;
never executed (the execution status of this line is deduced): m_edges.at(j).helper = i;
-
2081 } else if (m_edges.at(j).node) {
never executed: }
never evaluated: m_edges.at(j).node
0
2082 Q_ASSERT(!m_edges.at(i).node);
never executed (the execution status of this line is deduced): qt_noop();
-
2083 if (m_edges.at(m_edges.at(j).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(j).helper).type == MergeVertex
0
2084 diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
0
2085 m_edges.at(i).node = m_edges.at(j).node;
never executed (the execution status of this line is deduced): m_edges.at(i).node = m_edges.at(j).node;
-
2086 m_edges.at(j).node = 0;
never executed (the execution status of this line is deduced): m_edges.at(j).node = 0;
-
2087 m_edges.at(i).node->data = i;
never executed (the execution status of this line is deduced): m_edges.at(i).node->data = i;
-
2088 m_edges.at(i).helper = i;
never executed (the execution status of this line is deduced): m_edges.at(i).helper = i;
-
2089 } else {
never executed: }
0
2090 qWarning("Inconsistent polygon. (#1)");
never executed (the execution status of this line is deduced): QMessageLogger("opengl/qtriangulator.cpp", 2090, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#1)");
-
2091 }
never executed: }
0
2092 } else { -
2093 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
never executed (the execution status of this line is deduced): leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
-
2094 if (leftEdgeNode) {
never evaluated: leftEdgeNode
0
2095 if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex
0
2096 diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
0
2097 m_edges.at(leftEdgeNode->data).helper = i;
never executed (the execution status of this line is deduced): m_edges.at(leftEdgeNode->data).helper = i;
-
2098 } else {
never executed: }
0
2099 qWarning("Inconsistent polygon. (#2)");
never executed (the execution status of this line is deduced): QMessageLogger("opengl/qtriangulator.cpp", 2099, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#2)");
-
2100 }
never executed: }
0
2101 } -
2102 break;
never executed: break;
0
2103 case SplitVertex: -
2104 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
never executed (the execution status of this line is deduced): leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
-
2105 if (leftEdgeNode) {
never evaluated: leftEdgeNode
0
2106 diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
never executed (the execution status of this line is deduced): diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
-
2107 m_edges.at(leftEdgeNode->data).helper = i;
never executed (the execution status of this line is deduced): m_edges.at(leftEdgeNode->data).helper = i;
-
2108 } else {
never executed: }
0
2109 qWarning("Inconsistent polygon. (#3)");
never executed (the execution status of this line is deduced): QMessageLogger("opengl/qtriangulator.cpp", 2109, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#3)");
-
2110 }
never executed: }
0
2111 // Fall through. -
2112 case StartVertex:
code before this statement never executed: case StartVertex:
0
2113 if (m_clockwiseOrder) {
never evaluated: m_clockwiseOrder
0
2114 leftEdgeNode = searchEdgeLeftOfEdge(j);
never executed (the execution status of this line is deduced): leftEdgeNode = searchEdgeLeftOfEdge(j);
-
2115 QRBTree<int>::Node *node = m_edgeList.newNode();
never executed (the execution status of this line is deduced): QRBTree<int>::Node *node = m_edgeList.newNode();
-
2116 node->data = j;
never executed (the execution status of this line is deduced): node->data = j;
-
2117 m_edges.at(j).node = node;
never executed (the execution status of this line is deduced): m_edges.at(j).node = node;
-
2118 m_edges.at(j).helper = i;
never executed (the execution status of this line is deduced): m_edges.at(j).helper = i;
-
2119 m_edgeList.attachAfter(leftEdgeNode, node);
never executed (the execution status of this line is deduced): m_edgeList.attachAfter(leftEdgeNode, node);
-
2120 Q_ASSERT(m_edgeList.validate());
never executed (the execution status of this line is deduced): qt_noop();
-
2121 } else {
never executed: }
0
2122 leftEdgeNode = searchEdgeLeftOfEdge(i);
never executed (the execution status of this line is deduced): leftEdgeNode = searchEdgeLeftOfEdge(i);
-
2123 QRBTree<int>::Node *node = m_edgeList.newNode();
never executed (the execution status of this line is deduced): QRBTree<int>::Node *node = m_edgeList.newNode();
-
2124 node->data = i;
never executed (the execution status of this line is deduced): node->data = i;
-
2125 m_edges.at(i).node = node;
never executed (the execution status of this line is deduced): m_edges.at(i).node = node;
-
2126 m_edges.at(i).helper = i;
never executed (the execution status of this line is deduced): m_edges.at(i).helper = i;
-
2127 m_edgeList.attachAfter(leftEdgeNode, node);
never executed (the execution status of this line is deduced): m_edgeList.attachAfter(leftEdgeNode, node);
-
2128 Q_ASSERT(m_edgeList.validate());
never executed (the execution status of this line is deduced): qt_noop();
-
2129 }
never executed: }
0
2130 break;
never executed: break;
0
2131 case MergeVertex: -
2132 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
never executed (the execution status of this line is deduced): leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
-
2133 if (leftEdgeNode) {
never evaluated: leftEdgeNode
0
2134 if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex
0
2135 diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
0
2136 m_edges.at(leftEdgeNode->data).helper = i;
never executed (the execution status of this line is deduced): m_edges.at(leftEdgeNode->data).helper = i;
-
2137 } else {
never executed: }
0
2138 qWarning("Inconsistent polygon. (#4)");
never executed (the execution status of this line is deduced): QMessageLogger("opengl/qtriangulator.cpp", 2138, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#4)");
-
2139 }
never executed: }
0
2140 // Fall through. -
2141 case EndVertex:
code before this statement never executed: case EndVertex:
0
2142 if (m_clockwiseOrder) {
never evaluated: m_clockwiseOrder
0
2143 if (m_edges.at(m_edges.at(i).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(i).helper).type == MergeVertex
0
2144 diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
0
2145 if (m_edges.at(i).node) {
never evaluated: m_edges.at(i).node
0
2146 m_edgeList.deleteNode(m_edges.at(i).node);
never executed (the execution status of this line is deduced): m_edgeList.deleteNode(m_edges.at(i).node);
-
2147 Q_ASSERT(m_edgeList.validate());
never executed (the execution status of this line is deduced): qt_noop();
-
2148 } else {
never executed: }
0
2149 qWarning("Inconsistent polygon. (#5)");
never executed (the execution status of this line is deduced): QMessageLogger("opengl/qtriangulator.cpp", 2149, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#5)");
-
2150 }
never executed: }
0
2151 } else { -
2152 if (m_edges.at(m_edges.at(j).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(j).helper).type == MergeVertex
0
2153 diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
0
2154 if (m_edges.at(j).node) {
never evaluated: m_edges.at(j).node
0
2155 m_edgeList.deleteNode(m_edges.at(j).node);
never executed (the execution status of this line is deduced): m_edgeList.deleteNode(m_edges.at(j).node);
-
2156 Q_ASSERT(m_edgeList.validate());
never executed (the execution status of this line is deduced): qt_noop();
-
2157 } else {
never executed: }
0
2158 qWarning("Inconsistent polygon. (#6)");
never executed (the execution status of this line is deduced): QMessageLogger("opengl/qtriangulator.cpp", 2158, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#6)");
-
2159 }
never executed: }
0
2160 } -
2161 break;
never executed: break;
0
2162 } -
2163 }
never executed: }
0
2164 -
2165 for (int i = 0; i < diagonals.size(); ++i)
never evaluated: i < diagonals.size()
0
2166 createDiagonal(diagonals.at(i).first, diagonals.at(i).second);
never executed: createDiagonal(diagonals.at(i).first, diagonals.at(i).second);
0
2167}
never executed: }
0
2168 -
2169template <typename T> -
2170bool QTriangulator<T>::SimpleToMonotone::CompareVertices::operator () (int i, int j) const -
2171{ -
2172 if (m_parent->m_edges.at(i).from == m_parent->m_edges.at(j).from)
never evaluated: m_parent->m_edges.at(i).from == m_parent->m_edges.at(j).from
0
2173 return m_parent->m_edges.at(i).type > m_parent->m_edges.at(j).type;
never executed: return m_parent->m_edges.at(i).type > m_parent->m_edges.at(j).type;
0
2174 return m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from) >
never executed: return m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from) > m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from);
0
2175 m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from);
never executed: return m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from) > m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from);
0
2176} -
2177 -
2178//============================================================================// -
2179// QTriangulator::MonotoneToTriangles // -
2180//============================================================================// -
2181template <typename T> -
2182void QTriangulator<T>::MonotoneToTriangles::decompose() -
2183{ -
2184 QVector<T> result;
never executed (the execution status of this line is deduced): QVector<T> result;
-
2185 QDataBuffer<int> stack(m_parent->m_indices.size());
never executed (the execution status of this line is deduced): QDataBuffer<int> stack(m_parent->m_indices.size());
-
2186 m_first = 0;
never executed (the execution status of this line is deduced): m_first = 0;
-
2187 // Require at least three more indices. -
2188 while (m_first + 3 <= m_parent->m_indices.size()) {
never evaluated: m_first + 3 <= m_parent->m_indices.size()
0
2189 m_length = 0;
never executed (the execution status of this line is deduced): m_length = 0;
-
2190 while (m_parent->m_indices.at(m_first + m_length) != T(-1)) { // Q_TRIANGULATE_END_OF_POLYGON
never evaluated: m_parent->m_indices.at(m_first + m_length) != T(-1)
0
2191 ++m_length;
never executed (the execution status of this line is deduced): ++m_length;
-
2192 Q_ASSERT(m_first + m_length < m_parent->m_indices.size());
never executed (the execution status of this line is deduced): qt_noop();
-
2193 }
never executed: }
0
2194 if (m_length < 3) {
never evaluated: m_length < 3
0
2195 m_first += m_length + 1;
never executed (the execution status of this line is deduced): m_first += m_length + 1;
-
2196 continue;
never executed: continue;
0
2197 } -
2198 -
2199 int minimum = 0;
never executed (the execution status of this line is deduced): int minimum = 0;
-
2200 while (less(next(minimum), minimum))
never evaluated: less(next(minimum), minimum)
0
2201 minimum = next(minimum);
never executed: minimum = next(minimum);
0
2202 while (less(previous(minimum), minimum))
never evaluated: less(previous(minimum), minimum)
0
2203 minimum = previous(minimum);
never executed: minimum = previous(minimum);
0
2204 -
2205 stack.reset();
never executed (the execution status of this line is deduced): stack.reset();
-
2206 stack.add(minimum);
never executed (the execution status of this line is deduced): stack.add(minimum);
-
2207 int left = previous(minimum);
never executed (the execution status of this line is deduced): int left = previous(minimum);
-
2208 int right = next(minimum);
never executed (the execution status of this line is deduced): int right = next(minimum);
-
2209 bool stackIsOnLeftSide;
never executed (the execution status of this line is deduced): bool stackIsOnLeftSide;
-
2210 bool clockwiseOrder = leftOfEdge(minimum, left, right);
never executed (the execution status of this line is deduced): bool clockwiseOrder = leftOfEdge(minimum, left, right);
-
2211 -
2212 if (less(left, right)) {
never evaluated: less(left, right)
0
2213 stack.add(left);
never executed (the execution status of this line is deduced): stack.add(left);
-
2214 left = previous(left);
never executed (the execution status of this line is deduced): left = previous(left);
-
2215 stackIsOnLeftSide = true;
never executed (the execution status of this line is deduced): stackIsOnLeftSide = true;
-
2216 } else {
never executed: }
0
2217 stack.add(right);
never executed (the execution status of this line is deduced): stack.add(right);
-
2218 right = next(right);
never executed (the execution status of this line is deduced): right = next(right);
-
2219 stackIsOnLeftSide = false;
never executed (the execution status of this line is deduced): stackIsOnLeftSide = false;
-
2220 }
never executed: }
0
2221 -
2222 for (int count = 0; count + 2 < m_length; ++count)
never evaluated: count + 2 < m_length
0
2223 { -
2224 Q_ASSERT(stack.size() >= 2);
never executed (the execution status of this line is deduced): qt_noop();
-
2225 if (less(left, right)) {
never evaluated: less(left, right)
0
2226 if (stackIsOnLeftSide == false) {
never evaluated: stackIsOnLeftSide == false
0
2227 for (int i = 0; i + 1 < stack.size(); ++i) {
never evaluated: i + 1 < stack.size()
0
2228 result.push_back(indices(stack.at(i + 1)));
never executed (the execution status of this line is deduced): result.push_back(indices(stack.at(i + 1)));
-
2229 result.push_back(indices(left));
never executed (the execution status of this line is deduced): result.push_back(indices(left));
-
2230 result.push_back(indices(stack.at(i)));
never executed (the execution status of this line is deduced): result.push_back(indices(stack.at(i)));
-
2231 }
never executed: }
0
2232 stack.first() = stack.last();
never executed (the execution status of this line is deduced): stack.first() = stack.last();
-
2233 stack.resize(1);
never executed (the execution status of this line is deduced): stack.resize(1);
-
2234 } else {
never executed: }
0
2235 while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(left, stack.at(stack.size() - 2), stack.last()))) {
never evaluated: stack.size() >= 2
never evaluated: (clockwiseOrder ^ !leftOfEdge(left, stack.at(stack.size() - 2), stack.last()))
0
2236 result.push_back(indices(stack.at(stack.size() - 2)));
never executed (the execution status of this line is deduced): result.push_back(indices(stack.at(stack.size() - 2)));
-
2237 result.push_back(indices(left));
never executed (the execution status of this line is deduced): result.push_back(indices(left));
-
2238 result.push_back(indices(stack.last()));
never executed (the execution status of this line is deduced): result.push_back(indices(stack.last()));
-
2239 stack.pop_back();
never executed (the execution status of this line is deduced): stack.pop_back();
-
2240 }
never executed: }
0
2241 }
never executed: }
0
2242 stack.add(left);
never executed (the execution status of this line is deduced): stack.add(left);
-
2243 left = previous(left);
never executed (the execution status of this line is deduced): left = previous(left);
-
2244 stackIsOnLeftSide = true;
never executed (the execution status of this line is deduced): stackIsOnLeftSide = true;
-
2245 } else {
never executed: }
0
2246 if (stackIsOnLeftSide == true) {
never evaluated: stackIsOnLeftSide == true
0
2247 for (int i = 0; i + 1 < stack.size(); ++i) {
never evaluated: i + 1 < stack.size()
0
2248 result.push_back(indices(stack.at(i)));
never executed (the execution status of this line is deduced): result.push_back(indices(stack.at(i)));
-
2249 result.push_back(indices(right));
never executed (the execution status of this line is deduced): result.push_back(indices(right));
-
2250 result.push_back(indices(stack.at(i + 1)));
never executed (the execution status of this line is deduced): result.push_back(indices(stack.at(i + 1)));
-
2251 }
never executed: }
0
2252 stack.first() = stack.last();
never executed (the execution status of this line is deduced): stack.first() = stack.last();
-
2253 stack.resize(1);
never executed (the execution status of this line is deduced): stack.resize(1);
-
2254 } else {
never executed: }
0
2255 while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(right, stack.last(), stack.at(stack.size() - 2)))) {
never evaluated: stack.size() >= 2
never evaluated: (clockwiseOrder ^ !leftOfEdge(right, stack.last(), stack.at(stack.size() - 2)))
0
2256 result.push_back(indices(stack.last()));
never executed (the execution status of this line is deduced): result.push_back(indices(stack.last()));
-
2257 result.push_back(indices(right));
never executed (the execution status of this line is deduced): result.push_back(indices(right));
-
2258 result.push_back(indices(stack.at(stack.size() - 2)));
never executed (the execution status of this line is deduced): result.push_back(indices(stack.at(stack.size() - 2)));
-
2259 stack.pop_back();
never executed (the execution status of this line is deduced): stack.pop_back();
-
2260 }
never executed: }
0
2261 }
never executed: }
0
2262 stack.add(right);
never executed (the execution status of this line is deduced): stack.add(right);
-
2263 right = next(right);
never executed (the execution status of this line is deduced): right = next(right);
-
2264 stackIsOnLeftSide = false;
never executed (the execution status of this line is deduced): stackIsOnLeftSide = false;
-
2265 }
never executed: }
0
2266 } -
2267 -
2268 m_first += m_length + 1;
never executed (the execution status of this line is deduced): m_first += m_length + 1;
-
2269 }
never executed: }
0
2270 m_parent->m_indices = result;
never executed (the execution status of this line is deduced): m_parent->m_indices = result;
-
2271}
never executed: }
0
2272 -
2273//============================================================================// -
2274// qTriangulate // -
2275//============================================================================// -
2276 -
2277static bool hasElementIndexUint() -
2278{ -
2279 QOpenGLContext *context = QOpenGLContext::currentContext();
never executed (the execution status of this line is deduced): QOpenGLContext *context = QOpenGLContext::currentContext();
-
2280 if (!context)
never evaluated: !context
0
2281 return false;
never executed: return false;
0
2282 return static_cast<QOpenGLExtensions *>(context->functions())->hasOpenGLExtension(QOpenGLExtensions::ElementIndexUint);
never executed: return static_cast<QOpenGLExtensions *>(context->functions())->hasOpenGLExtension(QOpenGLExtensions::ElementIndexUint);
0
2283} -
2284 -
2285Q_GUI_EXPORT QTriangleSet qTriangulate(const qreal *polygon, -
2286 int count, uint hint, const QTransform &matrix) -
2287{ -
2288 QTriangleSet triangleSet;
never executed (the execution status of this line is deduced): QTriangleSet triangleSet;
-
2289 if (hasElementIndexUint()) {
never evaluated: hasElementIndexUint()
0
2290 QTriangulator<quint32> triangulator;
never executed (the execution status of this line is deduced): QTriangulator<quint32> triangulator;
-
2291 triangulator.initialize(polygon, count, hint, matrix);
never executed (the execution status of this line is deduced): triangulator.initialize(polygon, count, hint, matrix);
-
2292 QVertexSet<quint32> vertexSet = triangulator.triangulate();
never executed (the execution status of this line is deduced): QVertexSet<quint32> vertexSet = triangulator.triangulate();
-
2293 triangleSet.vertices = vertexSet.vertices;
never executed (the execution status of this line is deduced): triangleSet.vertices = vertexSet.vertices;
-
2294 triangleSet.indices.setDataUint(vertexSet.indices);
never executed (the execution status of this line is deduced): triangleSet.indices.setDataUint(vertexSet.indices);
-
2295 -
2296 } else {
never executed: }
0
2297 QTriangulator<quint16> triangulator;
never executed (the execution status of this line is deduced): QTriangulator<quint16> triangulator;
-
2298 triangulator.initialize(polygon, count, hint, matrix);
never executed (the execution status of this line is deduced): triangulator.initialize(polygon, count, hint, matrix);
-
2299 QVertexSet<quint16> vertexSet = triangulator.triangulate();
never executed (the execution status of this line is deduced): QVertexSet<quint16> vertexSet = triangulator.triangulate();
-
2300 triangleSet.vertices = vertexSet.vertices;
never executed (the execution status of this line is deduced): triangleSet.vertices = vertexSet.vertices;
-
2301 triangleSet.indices.setDataUshort(vertexSet.indices);
never executed (the execution status of this line is deduced): triangleSet.indices.setDataUshort(vertexSet.indices);
-
2302 }
never executed: }
0
2303 return triangleSet;
never executed: return triangleSet;
0
2304} -
2305 -
2306Q_GUI_EXPORT QTriangleSet qTriangulate(const QVectorPath &path, -
2307 const QTransform &matrix, qreal lod) -
2308{ -
2309 QTriangleSet triangleSet;
never executed (the execution status of this line is deduced): QTriangleSet triangleSet;
-
2310 if (hasElementIndexUint()) {
never evaluated: hasElementIndexUint()
0
2311 QTriangulator<quint32> triangulator;
never executed (the execution status of this line is deduced): QTriangulator<quint32> triangulator;
-
2312 triangulator.initialize(path, matrix, lod);
never executed (the execution status of this line is deduced): triangulator.initialize(path, matrix, lod);
-
2313 QVertexSet<quint32> vertexSet = triangulator.triangulate();
never executed (the execution status of this line is deduced): QVertexSet<quint32> vertexSet = triangulator.triangulate();
-
2314 triangleSet.vertices = vertexSet.vertices;
never executed (the execution status of this line is deduced): triangleSet.vertices = vertexSet.vertices;
-
2315 triangleSet.indices.setDataUint(vertexSet.indices);
never executed (the execution status of this line is deduced): triangleSet.indices.setDataUint(vertexSet.indices);
-
2316 } else {
never executed: }
0
2317 QTriangulator<quint16> triangulator;
never executed (the execution status of this line is deduced): QTriangulator<quint16> triangulator;
-
2318 triangulator.initialize(path, matrix, lod);
never executed (the execution status of this line is deduced): triangulator.initialize(path, matrix, lod);
-
2319 QVertexSet<quint16> vertexSet = triangulator.triangulate();
never executed (the execution status of this line is deduced): QVertexSet<quint16> vertexSet = triangulator.triangulate();
-
2320 triangleSet.vertices = vertexSet.vertices;
never executed (the execution status of this line is deduced): triangleSet.vertices = vertexSet.vertices;
-
2321 triangleSet.indices.setDataUshort(vertexSet.indices);
never executed (the execution status of this line is deduced): triangleSet.indices.setDataUshort(vertexSet.indices);
-
2322 }
never executed: }
0
2323 return triangleSet;
never executed: return triangleSet;
0
2324} -
2325 -
2326QTriangleSet qTriangulate(const QPainterPath &path, -
2327 const QTransform &matrix, qreal lod) -
2328{ -
2329 QTriangleSet triangleSet;
never executed (the execution status of this line is deduced): QTriangleSet triangleSet;
-
2330 if (hasElementIndexUint()) {
never evaluated: hasElementIndexUint()
0
2331 QTriangulator<quint32> triangulator;
never executed (the execution status of this line is deduced): QTriangulator<quint32> triangulator;
-
2332 triangulator.initialize(path, matrix, lod);
never executed (the execution status of this line is deduced): triangulator.initialize(path, matrix, lod);
-
2333 QVertexSet<quint32> vertexSet = triangulator.triangulate();
never executed (the execution status of this line is deduced): QVertexSet<quint32> vertexSet = triangulator.triangulate();
-
2334 triangleSet.vertices = vertexSet.vertices;
never executed (the execution status of this line is deduced): triangleSet.vertices = vertexSet.vertices;
-
2335 triangleSet.indices.setDataUint(vertexSet.indices);
never executed (the execution status of this line is deduced): triangleSet.indices.setDataUint(vertexSet.indices);
-
2336 } else {
never executed: }
0
2337 QTriangulator<quint16> triangulator;
never executed (the execution status of this line is deduced): QTriangulator<quint16> triangulator;
-
2338 triangulator.initialize(path, matrix, lod);
never executed (the execution status of this line is deduced): triangulator.initialize(path, matrix, lod);
-
2339 QVertexSet<quint16> vertexSet = triangulator.triangulate();
never executed (the execution status of this line is deduced): QVertexSet<quint16> vertexSet = triangulator.triangulate();
-
2340 triangleSet.vertices = vertexSet.vertices;
never executed (the execution status of this line is deduced): triangleSet.vertices = vertexSet.vertices;
-
2341 triangleSet.indices.setDataUshort(vertexSet.indices);
never executed (the execution status of this line is deduced): triangleSet.indices.setDataUshort(vertexSet.indices);
-
2342 }
never executed: }
0
2343 return triangleSet;
never executed: return triangleSet;
0
2344} -
2345 -
2346QPolylineSet qPolyline(const QVectorPath &path, -
2347 const QTransform &matrix, qreal lod) -
2348{ -
2349 QPolylineSet polyLineSet;
never executed (the execution status of this line is deduced): QPolylineSet polyLineSet;
-
2350 if (hasElementIndexUint()) {
never evaluated: hasElementIndexUint()
0
2351 QTriangulator<quint32> triangulator;
never executed (the execution status of this line is deduced): QTriangulator<quint32> triangulator;
-
2352 triangulator.initialize(path, matrix, lod);
never executed (the execution status of this line is deduced): triangulator.initialize(path, matrix, lod);
-
2353 QVertexSet<quint32> vertexSet = triangulator.polyline();
never executed (the execution status of this line is deduced): QVertexSet<quint32> vertexSet = triangulator.polyline();
-
2354 polyLineSet.vertices = vertexSet.vertices;
never executed (the execution status of this line is deduced): polyLineSet.vertices = vertexSet.vertices;
-
2355 polyLineSet.indices.setDataUint(vertexSet.indices);
never executed (the execution status of this line is deduced): polyLineSet.indices.setDataUint(vertexSet.indices);
-
2356 } else {
never executed: }
0
2357 QTriangulator<quint16> triangulator;
never executed (the execution status of this line is deduced): QTriangulator<quint16> triangulator;
-
2358 triangulator.initialize(path, matrix, lod);
never executed (the execution status of this line is deduced): triangulator.initialize(path, matrix, lod);
-
2359 QVertexSet<quint16> vertexSet = triangulator.polyline();
never executed (the execution status of this line is deduced): QVertexSet<quint16> vertexSet = triangulator.polyline();
-
2360 polyLineSet.vertices = vertexSet.vertices;
never executed (the execution status of this line is deduced): polyLineSet.vertices = vertexSet.vertices;
-
2361 polyLineSet.indices.setDataUshort(vertexSet.indices);
never executed (the execution status of this line is deduced): polyLineSet.indices.setDataUshort(vertexSet.indices);
-
2362 }
never executed: }
0
2363 return polyLineSet;
never executed: return polyLineSet;
0
2364} -
2365 -
2366QPolylineSet qPolyline(const QPainterPath &path, -
2367 const QTransform &matrix, qreal lod) -
2368{ -
2369 QPolylineSet polyLineSet;
never executed (the execution status of this line is deduced): QPolylineSet polyLineSet;
-
2370 if (hasElementIndexUint()) {
never evaluated: hasElementIndexUint()
0
2371 QTriangulator<quint32> triangulator;
never executed (the execution status of this line is deduced): QTriangulator<quint32> triangulator;
-
2372 triangulator.initialize(path, matrix, lod);
never executed (the execution status of this line is deduced): triangulator.initialize(path, matrix, lod);
-
2373 QVertexSet<quint32> vertexSet = triangulator.polyline();
never executed (the execution status of this line is deduced): QVertexSet<quint32> vertexSet = triangulator.polyline();
-
2374 polyLineSet.vertices = vertexSet.vertices;
never executed (the execution status of this line is deduced): polyLineSet.vertices = vertexSet.vertices;
-
2375 polyLineSet.indices.setDataUint(vertexSet.indices);
never executed (the execution status of this line is deduced): polyLineSet.indices.setDataUint(vertexSet.indices);
-
2376 } else {
never executed: }
0
2377 QTriangulator<quint16> triangulator;
never executed (the execution status of this line is deduced): QTriangulator<quint16> triangulator;
-
2378 triangulator.initialize(path, matrix, lod);
never executed (the execution status of this line is deduced): triangulator.initialize(path, matrix, lod);
-
2379 QVertexSet<quint16> vertexSet = triangulator.polyline();
never executed (the execution status of this line is deduced): QVertexSet<quint16> vertexSet = triangulator.polyline();
-
2380 polyLineSet.vertices = vertexSet.vertices;
never executed (the execution status of this line is deduced): polyLineSet.vertices = vertexSet.vertices;
-
2381 polyLineSet.indices.setDataUshort(vertexSet.indices);
never executed (the execution status of this line is deduced): polyLineSet.indices.setDataUshort(vertexSet.indices);
-
2382 }
never executed: }
0
2383 return polyLineSet;
never executed: return polyLineSet;
0
2384} -
2385 -
2386QT_END_NAMESPACE -
2387 -
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial