qtriangulator.cpp

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