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

source code of qtbase/src/gui/painting/qtriangulator.cpp