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