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