qtriangulator.cpp

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