Qt 4.8
qtriangulator.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtOpenGL 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 Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 
42 #include "qtriangulator_p.h"
43 
44 #include <QtGui/qdialog.h>
45 #include <QtGui/qevent.h>
46 #include <QtGui/qpainter.h>
47 #include <QtGui/qpainterpath.h>
48 #include <QtGui/private/qbezier_p.h>
49 #include <QtGui/private/qdatabuffer_p.h>
50 #include <QtCore/qbitarray.h>
51 #include <QtCore/qvarlengtharray.h>
52 #include <QtCore/qqueue.h>
53 #include <QtCore/qglobal.h>
54 #include <QtCore/qpoint.h>
55 #include <QtCore/qalgorithms.h>
56 #include <QtDebug>
57 
58 #include <math.h>
59 
60 #include <private/qgl_p.h>
61 
63 
64 //#define Q_TRIANGULATOR_DEBUG
65 
66 #define Q_FIXED_POINT_SCALE 32
67 
68 // Quick sort.
69 template <class T, class LessThan>
70 #ifdef Q_CC_RVCT // RVCT 2.2 doesn't see recursive _static_ template function
71 void sort(T *array, int count, LessThan lessThan)
72 #else
73 static void sort(T *array, int count, LessThan lessThan)
74 #endif
75 {
76  // If the number of elements fall below some threshold, use insertion sort.
77  const int INSERTION_SORT_LIMIT = 7; // About 7 is fastest on my computer...
78  if (count <= INSERTION_SORT_LIMIT) {
79  for (int i = 1; i < count; ++i) {
80  T temp = array[i];
81  int j = i;
82  while (j > 0 && lessThan(temp, array[j - 1])) {
83  array[j] = array[j - 1];
84  --j;
85  }
86  array[j] = temp;
87  }
88  return;
89  }
90 
91  int high = count - 1;
92  int low = 0;
93  int mid = high / 2;
94  if (lessThan(array[mid], array[low]))
95  qSwap(array[mid], array[low]);
96  if (lessThan(array[high], array[mid]))
97  qSwap(array[high], array[mid]);
98  if (lessThan(array[mid], array[low]))
99  qSwap(array[mid], array[low]);
100 
101  --high;
102  ++low;
103  qSwap(array[mid], array[high]);
104  int pivot = high;
105  --high;
106 
107  while (low <= high) {
108  while (!lessThan(array[pivot], array[low])) {
109  ++low;
110  if (low > high)
111  goto sort_loop_end;
112  }
113  while (!lessThan(array[high], array[pivot])) {
114  --high;
115  if (low > high)
116  goto sort_loop_end;
117  }
118  qSwap(array[low], array[high]);
119  ++low;
120  --high;
121  }
122 sort_loop_end:
123  if (low != pivot)
124  qSwap(array[pivot], array[low]);
125  sort(array, low, lessThan);
126  sort(array + low + 1, count - low - 1, lessThan);
127 }
128 
129 // Quick sort.
130 template <class T>
131 #ifdef Q_CC_RVCT
132 void sort(T *array, int count) // RVCT 2.2 doesn't see recursive _static_ template function
133 #else
134 static void sort(T *array, int count)
135 #endif
136 {
137  // If the number of elements fall below some threshold, use insertion sort.
138  const int INSERTION_SORT_LIMIT = 25; // About 25 is fastest on my computer...
139  if (count <= INSERTION_SORT_LIMIT) {
140  for (int i = 1; i < count; ++i) {
141  T temp = array[i];
142  int j = i;
143  while (j > 0 && (temp < array[j - 1])) {
144  array[j] = array[j - 1];
145  --j;
146  }
147  array[j] = temp;
148  }
149  return;
150  }
151 
152  int high = count - 1;
153  int low = 0;
154  int mid = high / 2;
155  if ((array[mid] < array[low]))
156  qSwap(array[mid], array[low]);
157  if ((array[high] < array[mid]))
158  qSwap(array[high], array[mid]);
159  if ((array[mid] < array[low]))
160  qSwap(array[mid], array[low]);
161 
162  --high;
163  ++low;
164  qSwap(array[mid], array[high]);
165  int pivot = high;
166  --high;
167 
168  while (low <= high) {
169  while (!(array[pivot] < array[low])) {
170  ++low;
171  if (low > high)
172  goto sort_loop_end;
173  }
174  while (!(array[high] < array[pivot])) {
175  --high;
176  if (low > high)
177  goto sort_loop_end;
178  }
179  qSwap(array[low], array[high]);
180  ++low;
181  --high;
182  }
183 sort_loop_end:
184  if (low != pivot)
185  qSwap(array[pivot], array[low]);
186  sort(array, low);
187  sort(array + low + 1, count - low - 1);
188 }
189 
190 template<typename T>
192 {
193  inline QVertexSet() { }
194  inline QVertexSet(const QVertexSet<T> &other) : vertices(other.vertices), indices(other.indices) { }
195  QVertexSet<T> &operator = (const QVertexSet<T> &other) {vertices = other.vertices; indices = other.indices; return *this;}
196 
197  // 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, ...
198  QVector<qreal> vertices; // [x[0], y[0], x[1], y[1], x[2], ...]
199  QVector<T> indices; // [i[0], j[0], k[0], i[1], j[1], k[1], i[2], ...]
200 };
201 
202 //============================================================================//
203 // QFraction //
204 //============================================================================//
205 
206 // Fraction must be in the range [0, 1)
207 struct QFraction
208 {
209  // Comparison operators must not be called on invalid fractions.
210  inline bool operator < (const QFraction &other) const;
211  inline bool operator == (const QFraction &other) const;
212  inline bool operator != (const QFraction &other) const {return !(*this == other);}
213  inline bool operator > (const QFraction &other) const {return other < *this;}
214  inline bool operator >= (const QFraction &other) const {return !(*this < other);}
215  inline bool operator <= (const QFraction &other) const {return !(*this > other);}
216 
217  inline bool isValid() const {return denominator != 0;}
218 
219  // numerator and denominator must not have common denominators.
220  quint64 numerator, denominator;
221 };
222 
223 static inline quint64 gcd(quint64 x, quint64 y)
224 {
225  while (y != 0) {
226  quint64 z = y;
227  y = x % y;
228  x = z;
229  }
230  return x;
231 }
232 
233 static inline int compare(quint64 a, quint64 b)
234 {
235  return (a > b) - (a < b);
236 }
237 
238 // Compare a/b with c/d.
239 // Return negative if less, 0 if equal, positive if greater.
240 // a < b, c < d
242 {
243  const quint64 LIMIT = Q_UINT64_C(0x100000000);
244  for (;;) {
245  // If the products 'ad' and 'bc' fit into 64 bits, they can be directly compared.
246  if (b < LIMIT && d < LIMIT)
247  return compare(a * d, b * c);
248 
249  if (a == 0 || c == 0)
250  return compare(a, c);
251 
252  // a/b < c/d <=> d/c < b/a
253  quint64 b_div_a = b / a;
254  quint64 d_div_c = d / c;
255  if (b_div_a != d_div_c)
256  return compare(d_div_c, b_div_a);
257 
258  // floor(d/c) == floor(b/a)
259  // frac(d/c) < frac(b/a) ?
260  // frac(x/y) = (x%y)/y
261  d -= d_div_c * c; //d %= c;
262  b -= b_div_a * a; //b %= a;
263  qSwap(a, d);
264  qSwap(b, c);
265  }
266 }
267 
268 // Fraction must be in the range [0, 1)
269 // Assume input is valid.
271  QFraction result;
272  if (n == 0) {
273  result.numerator = 0;
274  result.denominator = 1;
275  } else {
276  quint64 g = gcd(n, d);
277  result.numerator = n / g;
278  result.denominator = d / g;
279  }
280  return result;
281 }
282 
283 inline bool QFraction::operator < (const QFraction &other) const
284 {
285  return qCompareFractions(numerator, denominator, other.numerator, other.denominator) < 0;
286 }
287 
288 inline bool QFraction::operator == (const QFraction &other) const
289 {
290  return numerator == other.numerator && denominator == other.denominator;
291 }
292 
293 //============================================================================//
294 // QPodPoint //
295 //============================================================================//
296 
297 struct QPodPoint
298 {
299  inline bool operator < (const QPodPoint &other) const
300  {
301  if (y != other.y)
302  return y < other.y;
303  return x < other.x;
304  }
305 
306  inline bool operator > (const QPodPoint &other) const {return other < *this;}
307  inline bool operator <= (const QPodPoint &other) const {return !(*this > other);}
308  inline bool operator >= (const QPodPoint &other) const {return !(*this < other);}
309  inline bool operator == (const QPodPoint &other) const {return x == other.x && y == other.y;}
310  inline bool operator != (const QPodPoint &other) const {return x != other.x || y != other.y;}
311 
312  inline QPodPoint &operator += (const QPodPoint &other) {x += other.x; y += other.y; return *this;}
313  inline QPodPoint &operator -= (const QPodPoint &other) {x -= other.x; y -= other.y; return *this;}
314  inline QPodPoint operator + (const QPodPoint &other) const {QPodPoint result = {x + other.x, y + other.y}; return result;}
315  inline QPodPoint operator - (const QPodPoint &other) const {QPodPoint result = {x - other.x, y - other.y}; return result;}
316 
317  int x;
318  int y;
319 };
320 
321 static inline qint64 qCross(const QPodPoint &u, const QPodPoint &v)
322 {
323  return qint64(u.x) * qint64(v.y) - qint64(u.y) * qint64(v.x);
324 }
325 
326 static inline qint64 qDot(const QPodPoint &u, const QPodPoint &v)
327 {
328  return qint64(u.x) * qint64(v.x) + qint64(u.y) * qint64(v.y);
329 }
330 
331 // Return positive value if 'p' is to the right of the line 'v1'->'v2', negative if left of the
332 // line and zero if exactly on the line.
333 // The returned value is the z-component of the qCross product between 'v2-v1' and 'p-v1',
334 // which is twice the signed area of the triangle 'p'->'v1'->'v2' (positive for CW order).
335 static inline qint64 qPointDistanceFromLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
336 {
337  return qCross(v2 - v1, p - v1);
338 }
339 
340 static inline bool qPointIsLeftOfLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
341 {
342  return QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(p, v1, v2) < 0;
343 }
344 
345 // Return:
346 // -1 if u < v
347 // 0 if u == v
348 // 1 if u > v
349 static int comparePoints(const QPodPoint &u, const QPodPoint &v)
350 {
351  if (u.y < v.y)
352  return -1;
353  if (u.y > v.y)
354  return 1;
355  if (u.x < v.x)
356  return -1;
357  if (u.x > v.x)
358  return 1;
359  return 0;
360 }
361 
362 //============================================================================//
363 // QIntersectionPoint //
364 //============================================================================//
365 
367 {
368  inline bool isValid() const {return xOffset.isValid() && yOffset.isValid();}
369  QPodPoint round() const;
370  inline bool isAccurate() const {return xOffset.numerator == 0 && yOffset.numerator == 0;}
371  bool operator < (const QIntersectionPoint &other) const;
372  bool operator == (const QIntersectionPoint &other) const;
373  inline bool operator != (const QIntersectionPoint &other) const {return !(*this == other);}
374  inline bool operator > (const QIntersectionPoint &other) const {return other < *this;}
375  inline bool operator >= (const QIntersectionPoint &other) const {return !(*this < other);}
376  inline bool operator <= (const QIntersectionPoint &other) const {return !(*this > other);}
377  bool isOnLine(const QPodPoint &u, const QPodPoint &v) const;
378 
382 };
383 
385 {
386  // upperLeft = point, xOffset = 0/1, yOffset = 0/1.
387  QIntersectionPoint p = {{point.x, point.y}, {0, 1}, {0, 1}};
388  return p;
389 }
390 
391 static inline QIntersectionPoint qIntersectionPoint(int x, int y)
392 {
393  // upperLeft = (x, y), xOffset = 0/1, yOffset = 0/1.
394  QIntersectionPoint p = {{x, y}, {0, 1}, {0, 1}};
395  return p;
396 }
397 
398 static QIntersectionPoint qIntersectionPoint(const QPodPoint &u1, const QPodPoint &u2, const QPodPoint &v1, const QPodPoint &v2)
399 {
400  QIntersectionPoint result = {{0, 0}, {0, 0}, {0, 0}};
401 
402  QPodPoint u = u2 - u1;
403  QPodPoint v = v2 - v1;
404  qint64 d1 = qCross(u, v1 - u1);
405  qint64 d2 = qCross(u, v2 - u1);
406  qint64 det = d2 - d1;
407  qint64 d3 = qCross(v, u1 - v1);
408  qint64 d4 = d3 - det; //qCross(v, u2 - v1);
409 
410  // Check that the math is correct.
411  Q_ASSERT(d4 == qCross(v, u2 - v1));
412 
413  // The intersection point can be expressed as:
414  // v1 - v * d1/det
415  // v2 - v * d2/det
416  // u1 + u * d3/det
417  // u2 + u * d4/det
418 
419  // I'm only interested in lines that are crossing, so ignore parallel lines even if they overlap.
420  if (det == 0)
421  return result;
422 
423  if (det < 0) {
424  det = -det;
425  d1 = -d1;
426  d2 = -d2;
427  d3 = -d3;
428  d4 = -d4;
429  }
430 
431  // I'm only interested in lines intersecting at their interior, not at their end points.
432  // The lines intersect at their interior if and only if 'd1 < 0', 'd2 > 0', 'd3 < 0' and 'd4 > 0'.
433  if (d1 >= 0 || d2 <= 0 || d3 <= 0 || d4 >= 0)
434  return result;
435 
436  // Calculate the intersection point as follows:
437  // v1 - v * d1/det | v1 <= v2 (component-wise)
438  // v2 - v * d2/det | v2 < v1 (component-wise)
439 
440  // Assuming 21 bits per vector component.
441  // TODO: Make code path for 31 bits per vector component.
442  if (v.x >= 0) {
443  result.upperLeft.x = v1.x + (-v.x * d1) / det;
444  result.xOffset = qFraction(quint64(-v.x * d1) % quint64(det), quint64(det));
445  } else {
446  result.upperLeft.x = v2.x + (-v.x * d2) / det;
447  result.xOffset = qFraction(quint64(-v.x * d2) % quint64(det), quint64(det));
448  }
449 
450  if (v.y >= 0) {
451  result.upperLeft.y = v1.y + (-v.y * d1) / det;
452  result.yOffset = qFraction(quint64(-v.y * d1) % quint64(det), quint64(det));
453  } else {
454  result.upperLeft.y = v2.y + (-v.y * d2) / det;
455  result.yOffset = qFraction(quint64(-v.y * d2) % quint64(det), quint64(det));
456  }
457 
458  Q_ASSERT(result.xOffset.isValid());
459  Q_ASSERT(result.yOffset.isValid());
460  return result;
461 }
462 
464 {
465  QPodPoint result = upperLeft;
466  if (2 * xOffset.numerator >= xOffset.denominator)
467  ++result.x;
468  if (2 * yOffset.numerator >= yOffset.denominator)
469  ++result.y;
470  return result;
471 }
472 
474 {
475  if (upperLeft.y != other.upperLeft.y)
476  return upperLeft.y < other.upperLeft.y;
477  if (yOffset != other.yOffset)
478  return yOffset < other.yOffset;
479  if (upperLeft.x != other.upperLeft.x)
480  return upperLeft.x < other.upperLeft.x;
481  return xOffset < other.xOffset;
482 }
483 
485 {
486  return upperLeft == other.upperLeft && xOffset == other.xOffset && yOffset == other.yOffset;
487 }
488 
489 // Returns true if this point is on the infinite line passing through 'u' and 'v'.
490 bool QIntersectionPoint::isOnLine(const QPodPoint &u, const QPodPoint &v) const
491 {
492  // TODO: Make code path for coordinates with more than 21 bits.
493  const QPodPoint p = upperLeft - u;
494  const QPodPoint q = v - u;
495  bool isHorizontal = p.y == 0 && yOffset.numerator == 0;
496  bool isVertical = p.x == 0 && xOffset.numerator == 0;
497  if (isHorizontal && isVertical)
498  return true;
499  if (isHorizontal)
500  return q.y == 0;
501  if (q.y == 0)
502  return false;
503  if (isVertical)
504  return q.x == 0;
505  if (q.x == 0)
506  return false;
507 
508  // At this point, 'p+offset' and 'q' cannot lie on the x or y axis.
509 
510  if (((q.x < 0) == (q.y < 0)) != ((p.x < 0) == (p.y < 0)))
511  return false; // 'p + offset' and 'q' pass through different quadrants.
512 
513  // Move all coordinates into the first quadrant.
514  quint64 nx, ny;
515  if (p.x < 0)
516  nx = quint64(-p.x) * xOffset.denominator - xOffset.numerator;
517  else
518  nx = quint64(p.x) * xOffset.denominator + xOffset.numerator;
519  if (p.y < 0)
520  ny = quint64(-p.y) * yOffset.denominator - yOffset.numerator;
521  else
522  ny = quint64(p.y) * yOffset.denominator + yOffset.numerator;
523 
524  return qFraction(quint64(qAbs(q.x)) * xOffset.denominator, quint64(qAbs(q.y)) * yOffset.denominator) == qFraction(nx, ny);
525 }
526 
527 //============================================================================//
528 // QMaxHeap //
529 //============================================================================//
530 
531 template <class T>
532 class QMaxHeap
533 {
534 public:
535  QMaxHeap() : m_data(0) {}
536  inline int size() const {return m_data.size();}
537  inline bool empty() const {return m_data.isEmpty();}
538  inline bool isEmpty() const {return m_data.isEmpty();}
539  void push(const T &x);
540  T pop();
541  inline const T &top() const {return m_data.first();}
542 private:
543  static inline int parent(int i) {return (i - 1) / 2;}
544  static inline int left(int i) {return 2 * i + 1;}
545  static inline int right(int i) {return 2 * i + 2;}
546 
548 };
549 
550 template <class T>
551 void QMaxHeap<T>::push(const T &x)
552 {
553  int current = m_data.size();
554  int parent = QMaxHeap::parent(current);
555  m_data.add(x);
556  while (current != 0 && m_data.at(parent) < x) {
557  m_data.at(current) = m_data.at(parent);
558  current = parent;
559  parent = QMaxHeap::parent(current);
560  }
561  m_data.at(current) = x;
562 }
563 
564 template <class T>
566 {
567  T result = m_data.first();
568  T back = m_data.last();
569  m_data.pop_back();
570  if (!m_data.isEmpty()) {
571  int current = 0;
572  for (;;) {
573  int left = QMaxHeap::left(current);
574  int right = QMaxHeap::right(current);
575  if (left >= m_data.size())
576  break;
577  int greater = left;
578  if (right < m_data.size() && m_data.at(left) < m_data.at(right))
579  greater = right;
580  if (m_data.at(greater) < back)
581  break;
582  m_data.at(current) = m_data.at(greater);
583  current = greater;
584  }
585  m_data.at(current) = back;
586  }
587  return result;
588 }
589 
590 //============================================================================//
591 // QRBTree //
592 //============================================================================//
593 
594 template <class T>
595 struct QRBTree
596 {
597  struct Node
598  {
599  inline Node() : parent(0), left(0), right(0), red(true) { }
600  inline ~Node() {if (left) delete left; if (right) delete right;}
601  T data;
605  bool red;
606  };
607 
608  inline QRBTree() : root(0), freeList(0) { }
609  inline ~QRBTree();
610 
611  inline void clear();
612 
613  void attachBefore(Node *parent, Node *child);
614  void attachAfter(Node *parent, Node *child);
615 
616  inline Node *front(Node *node) const;
617  inline Node *back(Node *node) const;
618  Node *next(Node *node) const;
619  Node *previous(Node *node) const;
620 
621  inline void deleteNode(Node *&node);
622  inline Node *newNode();
623 
624  // Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise.
625  // 'left' and 'right' cannot be null.
626  int order(Node *left, Node *right);
627  inline bool validate() const;
628 
629 private:
630  void rotateLeft(Node *node);
631  void rotateRight(Node *node);
632  void update(Node *node);
633 
634  inline void attachLeft(Node *parent, Node *child);
635  inline void attachRight(Node *parent, Node *child);
636 
637  int blackDepth(Node *top) const;
638  bool checkRedBlackProperty(Node *top) const;
639 
640  void swapNodes(Node *n1, Node *n2);
641  void detach(Node *node);
642 
643  // 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree.
644  void rebalance(Node *node);
645 
646 public:
648 private:
650 };
651 
652 template <class T>
654 {
655  clear();
656  while (freeList) {
657  // Avoid recursively calling the destructor, as this list may become large.
658  Node *next = freeList->right;
659  freeList->right = 0;
660  delete freeList;
661  freeList = next;
662  }
663 }
664 
665 template <class T>
666 inline void QRBTree<T>::clear()
667 {
668  if (root)
669  delete root;
670  root = 0;
671 }
672 
673 template <class T>
675 {
676  // | | //
677  // N B //
678  // / \ / \ //
679  // A B ---> N D //
680  // / \ / \ //
681  // C D A C //
682 
683  Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
684  ref = node->right;
685  node->right->parent = node->parent;
686 
687  // : //
688  // N //
689  // / :| //
690  // A B //
691  // / \ //
692  // C D //
693 
694  node->right = ref->left;
695  if (ref->left)
696  ref->left->parent = node;
697 
698  // : | //
699  // N B //
700  // / \ : \ //
701  // A C D //
702 
703  ref->left = node;
704  node->parent = ref;
705 
706  // | //
707  // B //
708  // / \ //
709  // N D //
710  // / \ //
711  // A C //
712 }
713 
714 template <class T>
716 {
717  // | | //
718  // N A //
719  // / \ / \ //
720  // A B ---> C N //
721  // / \ / \ //
722  // C D D B //
723 
724  Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
725  ref = node->left;
726  node->left->parent = node->parent;
727 
728  node->left = ref->right;
729  if (ref->right)
730  ref->right->parent = node;
731 
732  ref->right = node;
733  node->parent = ref;
734 }
735 
736 template <class T>
737 void QRBTree<T>::update(Node *node) // call this after inserting a node
738 {
739  for (;;) {
740  Node *parent = node->parent;
741 
742  // if the node is the root, color it black
743  if (!parent) {
744  node->red = false;
745  return;
746  }
747 
748  // if the parent is black, the node can be left red
749  if (!parent->red)
750  return;
751 
752  // at this point, the parent is red and cannot be the root
753  Node *grandpa = parent->parent;
754  Q_ASSERT(grandpa);
755 
756  Node *uncle = (parent == grandpa->left ? grandpa->right : grandpa->left);
757  if (uncle && uncle->red) {
758  // grandpa's black, parent and uncle are red.
759  // let parent and uncle be black, grandpa red and recursively update grandpa.
760  Q_ASSERT(!grandpa->red);
761  parent->red = false;
762  uncle->red = false;
763  grandpa->red = true;
764  node = grandpa;
765  continue;
766  }
767 
768  // at this point, uncle is black
769  if (node == parent->right && parent == grandpa->left)
770  rotateLeft(node = parent);
771  else if (node == parent->left && parent == grandpa->right)
772  rotateRight(node = parent);
773  parent = node->parent;
774 
775  if (parent == grandpa->left) {
776  rotateRight(grandpa);
777  parent->red = false;
778  grandpa->red = true;
779  } else {
780  rotateLeft(grandpa);
781  parent->red = false;
782  grandpa->red = true;
783  }
784  return;
785  }
786 }
787 
788 template <class T>
789 inline void QRBTree<T>::attachLeft(Node *parent, Node *child)
790 {
791  Q_ASSERT(!parent->left);
792  parent->left = child;
793  child->parent = parent;
794  update(child);
795 }
796 
797 template <class T>
798 inline void QRBTree<T>::attachRight(Node *parent, Node *child)
799 {
800  Q_ASSERT(!parent->right);
801  parent->right = child;
802  child->parent = parent;
803  update(child);
804 }
805 
806 template <class T>
807 void QRBTree<T>::attachBefore(Node *parent, Node *child)
808 {
809  if (!root)
810  update(root = child);
811  else if (!parent)
812  attachRight(back(root), child);
813  else if (parent->left)
814  attachRight(back(parent->left), child);
815  else
816  attachLeft(parent, child);
817 }
818 
819 template <class T>
820 void QRBTree<T>::attachAfter(Node *parent, Node *child)
821 {
822  if (!root)
823  update(root = child);
824  else if (!parent)
825  attachLeft(front(root), child);
826  else if (parent->right)
827  attachLeft(front(parent->right), child);
828  else
829  attachRight(parent, child);
830 }
831 
832 template <class T>
834 {
835  // Since iterators must not be invalidated, it is not sufficient to only swap the data.
836  if (n1->parent == n2) {
837  n1->parent = n2->parent;
838  n2->parent = n1;
839  } else if (n2->parent == n1) {
840  n2->parent = n1->parent;
841  n1->parent = n2;
842  } else {
843  qSwap(n1->parent, n2->parent);
844  }
845 
846  qSwap(n1->left, n2->left);
847  qSwap(n1->right, n2->right);
848  qSwap(n1->red, n2->red);
849 
850  if (n1->parent) {
851  if (n1->parent->left == n2)
852  n1->parent->left = n1;
853  else
854  n1->parent->right = n1;
855  } else {
856  root = n1;
857  }
858 
859  if (n2->parent) {
860  if (n2->parent->left == n1)
861  n2->parent->left = n2;
862  else
863  n2->parent->right = n2;
864  } else {
865  root = n2;
866  }
867 
868  if (n1->left)
869  n1->left->parent = n1;
870  if (n1->right)
871  n1->right->parent = n1;
872 
873  if (n2->left)
874  n2->left->parent = n2;
875  if (n2->right)
876  n2->right->parent = n2;
877 }
878 
879 template <class T>
880 void QRBTree<T>::detach(Node *node) // call this before removing a node.
881 {
882  if (node->right)
883  swapNodes(node, front(node->right));
884 
885  Node *child = (node->left ? node->left : node->right);
886 
887  if (!node->red) {
888  if (child && child->red)
889  child->red = false;
890  else
891  rebalance(node);
892  }
893 
894  Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
895  ref = child;
896  if (child)
897  child->parent = node->parent;
898  node->left = node->right = node->parent = 0;
899 }
900 
901 // 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree.
902 template <class T>
904 {
905  Q_ASSERT(!node->red);
906  for (;;) {
907  if (!node->parent)
908  return;
909 
910  // at this point, node is not a parent, it is black, thus it must have a sibling.
911  Node *sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
912  Q_ASSERT(sibling);
913 
914  if (sibling->red) {
915  sibling->red = false;
916  node->parent->red = true;
917  if (node == node->parent->left)
918  rotateLeft(node->parent);
919  else
920  rotateRight(node->parent);
921  sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
922  Q_ASSERT(sibling);
923  }
924 
925  // at this point, the sibling is black.
926  Q_ASSERT(!sibling->red);
927 
928  if ((!sibling->left || !sibling->left->red) && (!sibling->right || !sibling->right->red)) {
929  bool parentWasRed = node->parent->red;
930  sibling->red = true;
931  node->parent->red = false;
932  if (parentWasRed)
933  return;
934  node = node->parent;
935  continue;
936  }
937 
938  // at this point, at least one of the sibling's children is red.
939 
940  if (node == node->parent->left) {
941  if (!sibling->right || !sibling->right->red) {
942  Q_ASSERT(sibling->left);
943  sibling->red = true;
944  sibling->left->red = false;
945  rotateRight(sibling);
946 
947  sibling = sibling->parent;
948  Q_ASSERT(sibling);
949  }
950  sibling->red = node->parent->red;
951  node->parent->red = false;
952 
953  Q_ASSERT(sibling->right->red);
954  sibling->right->red = false;
955  rotateLeft(node->parent);
956  } else {
957  if (!sibling->left || !sibling->left->red) {
958  Q_ASSERT(sibling->right);
959  sibling->red = true;
960  sibling->right->red = false;
961  rotateLeft(sibling);
962 
963  sibling = sibling->parent;
964  Q_ASSERT(sibling);
965  }
966  sibling->red = node->parent->red;
967  node->parent->red = false;
968 
969  Q_ASSERT(sibling->left->red);
970  sibling->left->red = false;
971  rotateRight(node->parent);
972  }
973  return;
974  }
975 }
976 
977 template <class T>
978 inline typename QRBTree<T>::Node *QRBTree<T>::front(Node *node) const
979 {
980  while (node->left)
981  node = node->left;
982  return node;
983 }
984 
985 template <class T>
986 inline typename QRBTree<T>::Node *QRBTree<T>::back(Node *node) const
987 {
988  while (node->right)
989  node = node->right;
990  return node;
991 }
992 
993 template <class T>
994 typename QRBTree<T>::Node *QRBTree<T>::next(Node *node) const
995 {
996  if (node->right)
997  return front(node->right);
998  while (node->parent && node == node->parent->right)
999  node = node->parent;
1000  return node->parent;
1001 }
1002 
1003 template <class T>
1005 {
1006  if (node->left)
1007  return back(node->left);
1008  while (node->parent && node == node->parent->left)
1009  node = node->parent;
1010  return node->parent;
1011 }
1012 
1013 template <class T>
1015 {
1016  if (!top)
1017  return 0;
1018  int leftDepth = blackDepth(top->left);
1019  int rightDepth = blackDepth(top->right);
1020  if (leftDepth != rightDepth)
1021  return -1;
1022  if (!top->red)
1023  ++leftDepth;
1024  return leftDepth;
1025 }
1026 
1027 template <class T>
1029 {
1030  if (!top)
1031  return true;
1032  if (top->left && !checkRedBlackProperty(top->left))
1033  return false;
1034  if (top->right && !checkRedBlackProperty(top->right))
1035  return false;
1036  return !(top->red && ((top->left && top->left->red) || (top->right && top->right->red)));
1037 }
1038 
1039 template <class T>
1040 inline bool QRBTree<T>::validate() const
1041 {
1042  return checkRedBlackProperty(root) && blackDepth(root) != -1;
1043 }
1044 
1045 template <class T>
1046 inline void QRBTree<T>::deleteNode(Node *&node)
1047 {
1048  Q_ASSERT(node);
1049  detach(node);
1050  node->right = freeList;
1051  freeList = node;
1052  node = 0;
1053 }
1054 
1055 template <class T>
1057 {
1058  if (freeList) {
1059  Node *node = freeList;
1060  freeList = freeList->right;
1061  node->parent = node->left = node->right = 0;
1062  node->red = true;
1063  return node;
1064  }
1065  return new Node;
1066 }
1067 
1068 // Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise.
1069 // 'left' and 'right' cannot be null.
1070 template <class T>
1072 {
1073  Q_ASSERT(left && right);
1074  if (left == right)
1075  return 0;
1076 
1077  QVector<Node *> leftAncestors;
1078  QVector<Node *> rightAncestors;
1079  while (left) {
1080  leftAncestors.push_back(left);
1081  left = left->parent;
1082  }
1083  while (right) {
1084  rightAncestors.push_back(right);
1085  right = right->parent;
1086  }
1087  Q_ASSERT(leftAncestors.back() == root && rightAncestors.back() == root);
1088 
1089  while (!leftAncestors.empty() && !rightAncestors.empty() && leftAncestors.back() == rightAncestors.back()) {
1090  leftAncestors.pop_back();
1091  rightAncestors.pop_back();
1092  }
1093 
1094  if (!leftAncestors.empty())
1095  return (leftAncestors.back() == leftAncestors.back()->parent->left ? -1 : 1);
1096 
1097  if (!rightAncestors.empty())
1098  return (rightAncestors.back() == rightAncestors.back()->parent->right ? -1 : 1);
1099 
1100  // The code should never reach this point.
1101  Q_ASSERT(!leftAncestors.empty() || !rightAncestors.empty());
1102  return 0;
1103 }
1104 
1105 //============================================================================//
1106 // QInt64Hash //
1107 //============================================================================//
1108 
1109 // Copied from qhash.cpp
1110 static const uchar prime_deltas[] = {
1111  0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3,
1112  1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0
1113 };
1114 
1115 // Copied from qhash.cpp
1116 static inline int primeForNumBits(int numBits)
1117 {
1118  return (1 << numBits) + prime_deltas[numBits];
1119 }
1120 
1121 static inline int primeForCount(int count)
1122 {
1123  int low = 0;
1124  int high = 32;
1125  for (int i = 0; i < 5; ++i) {
1126  int mid = (high + low) / 2;
1127  if (count >= 1 << mid)
1128  low = mid;
1129  else
1130  high = mid;
1131  }
1132  return primeForNumBits(high);
1133 }
1134 
1135 // Hash set of quint64s. Elements cannot be removed without clearing the
1136 // entire set. A value of -1 is used to mark unused entries.
1138 {
1139 public:
1140  inline QInt64Set(int capacity = 64);
1141  inline ~QInt64Set() {if (m_array) delete[] m_array;}
1142  inline bool isValid() const {return m_array;}
1143  void insert(quint64 key);
1144  bool contains(quint64 key) const;
1145  inline void clear();
1146 private:
1147  bool rehash(int capacity);
1148 
1149  static const quint64 UNUSED;
1150 
1153  int m_count;
1154 };
1155 
1156 const quint64 QInt64Set::UNUSED = quint64(-1);
1157 
1158 inline QInt64Set::QInt64Set(int capacity)
1159 {
1160  m_capacity = primeForCount(capacity);
1161  m_array = new quint64[m_capacity];
1162  if (m_array)
1163  clear();
1164  else
1165  m_capacity = 0;
1166 }
1167 
1168 bool QInt64Set::rehash(int capacity)
1169 {
1170  quint64 *oldArray = m_array;
1171  int oldCapacity = m_capacity;
1172 
1173  m_capacity = capacity;
1174  m_array = new quint64[m_capacity];
1175  if (m_array) {
1176  clear();
1177  if (oldArray) {
1178  for (int i = 0; i < oldCapacity; ++i) {
1179  if (oldArray[i] != UNUSED)
1180  insert(oldArray[i]);
1181  }
1182  delete[] oldArray;
1183  }
1184  return true;
1185  } else {
1186  m_capacity = oldCapacity;
1187  m_array = oldArray;
1188  return false;
1189  }
1190 }
1191 
1193 {
1194  if (m_count > 3 * m_capacity / 4)
1195  rehash(primeForCount(2 * m_capacity));
1196  Q_ASSERT_X(m_array, "QInt64Hash<T>::insert", "Hash set not allocated.");
1197  int index = int(key % m_capacity);
1198  for (int i = 0; i < m_capacity; ++i) {
1199  index += i;
1200  if (index >= m_capacity)
1201  index -= m_capacity;
1202  if (m_array[index] == key)
1203  return;
1204  if (m_array[index] == UNUSED) {
1205  ++m_count;
1206  m_array[index] = key;
1207  return;
1208  }
1209  }
1210  Q_ASSERT_X(0, "QInt64Hash<T>::insert", "Hash set full.");
1211 }
1212 
1214 {
1215  Q_ASSERT_X(m_array, "QInt64Hash<T>::contains", "Hash set not allocated.");
1216  int index = int(key % m_capacity);
1217  for (int i = 0; i < m_capacity; ++i) {
1218  index += i;
1219  if (index >= m_capacity)
1220  index -= m_capacity;
1221  if (m_array[index] == key)
1222  return true;
1223  if (m_array[index] == UNUSED)
1224  return false;
1225  }
1226  return false;
1227 }
1228 
1229 inline void QInt64Set::clear()
1230 {
1231  Q_ASSERT_X(m_array, "QInt64Hash<T>::clear", "Hash set not allocated.");
1232  for (int i = 0; i < m_capacity; ++i)
1233  m_array[i] = UNUSED;
1234  m_count = 0;
1235 }
1236 
1237 //============================================================================//
1238 // QRingBuffer //
1239 //============================================================================//
1240 
1241 // T must be POD.
1242 template <class T>
1243 class QRingBuffer
1244 {
1245 public:
1246  inline QRingBuffer() : m_array(0), m_head(0), m_size(0), m_capacity(0) { }
1247  inline ~QRingBuffer() {if (m_array) delete[] m_array;}
1248  bool reallocate(int capacity);
1249  inline const T &head() const {Q_ASSERT(m_size > 0); return m_array[m_head];}
1250  inline const T &dequeue();
1251  inline void enqueue(const T &x);
1252  inline bool isEmpty() const {return m_size == 0;}
1253 private:
1255  int m_head;
1256  int m_size;
1258 };
1259 
1260 template <class T>
1261 bool QRingBuffer<T>::reallocate(int capacity)
1262 {
1263  T *oldArray = m_array;
1264  m_array = new T[capacity];
1265  if (m_array) {
1266  if (oldArray) {
1267  if (m_head + m_size > m_capacity) {
1268  memcpy(m_array, oldArray + m_head, (m_capacity - m_head) * sizeof(T));
1269  memcpy(m_array + (m_capacity - m_head), oldArray, (m_head + m_size - m_capacity) * sizeof(T));
1270  } else {
1271  memcpy(m_array, oldArray + m_head, m_size * sizeof(T));
1272  }
1273  delete[] oldArray;
1274  }
1275  m_capacity = capacity;
1276  m_head = 0;
1277  return true;
1278  } else {
1279  m_array = oldArray;
1280  return false;
1281  }
1282 }
1283 
1284 template <class T>
1285 inline const T &QRingBuffer<T>::dequeue()
1286 {
1287  Q_ASSERT(m_size > 0);
1288  Q_ASSERT(m_array);
1289  Q_ASSERT(m_capacity >= m_size);
1290  int index = m_head;
1291  if (++m_head >= m_capacity)
1292  m_head -= m_capacity;
1293  --m_size;
1294  return m_array[index];
1295 }
1296 
1297 template <class T>
1298 inline void QRingBuffer<T>::enqueue(const T &x)
1299 {
1300  if (m_size == m_capacity)
1301  reallocate(qMax(2 * m_capacity, 64));
1302  int index = m_head + m_size;
1303  if (index >= m_capacity)
1304  index -= m_capacity;
1305  m_array[index] = x;
1306  ++m_size;
1307 }
1308 
1309 //============================================================================//
1310 // QTriangulator //
1311 //============================================================================//
1312 
1314 
1315 template<typename T>
1317 {
1318 public:
1320 
1321  //================================//
1322  // QTriangulator::ComplexToSimple //
1323  //================================//
1324  friend class ComplexToSimple;
1326  {
1327  public:
1328  inline ComplexToSimple(QTriangulator<T> *parent) : m_parent(parent),
1329  m_edges(0), m_events(0), m_splits(0) { }
1330  void decompose();
1331  private:
1332  struct Edge
1333  {
1334  inline int &upper() {return pointingUp ? to : from;}
1335  inline int &lower() {return pointingUp ? from : to;}
1336  inline int upper() const {return pointingUp ? to : from;}
1337  inline int lower() const {return pointingUp ? from : to;}
1338 
1340  int from, to; // vertex
1341  int next, previous; // edge
1342  int winding;
1344  bool pointingUp, originallyPointingUp;
1345  };
1346 
1347  friend class CompareEdges;
1349  {
1350  public:
1351  inline CompareEdges(ComplexToSimple *parent) : m_parent(parent) { }
1352  bool operator () (int i, int j) const;
1353  private:
1355  };
1356 
1358  {
1359  bool operator < (const Intersection &other) const {return other.intersectionPoint < intersectionPoint;}
1360 
1362  int vertex;
1365  };
1366 
1367  struct Split
1368  {
1369  int vertex;
1370  int edge;
1371  bool accurate;
1372  };
1373 
1374  struct Event
1375  {
1376  enum Type {Upper, Lower};
1377  inline bool operator < (const Event &other) const;
1378 
1381  int edge;
1382  };
1383 
1384 #ifdef Q_TRIANGULATOR_DEBUG
1385  friend class DebugDialog;
1386  friend class QTriangulator;
1387  class DebugDialog : public QDialog
1388  {
1389  public:
1390  DebugDialog(ComplexToSimple *parent, int currentVertex);
1391  protected:
1392  void paintEvent(QPaintEvent *);
1393  void wheelEvent(QWheelEvent *);
1394  void mouseMoveEvent(QMouseEvent *);
1395  void mousePressEvent(QMouseEvent *);
1396  private:
1397  ComplexToSimple *m_parent;
1398  QRectF m_window;
1399  QPoint m_lastMousePos;
1400  int m_vertex;
1401  };
1402 #endif
1403 
1404  void initEdges();
1405  bool calculateIntersection(int left, int right);
1406  bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const;
1407  QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex) const;
1408  QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const;
1409  QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> bounds(const QPodPoint &point) const;
1410  QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> outerBounds(const QPodPoint &point) const;
1411  void splitEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint);
1412  void reorderEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost);
1413  void sortEdgeList(const QPodPoint eventPoint);
1414  void fillPriorityQueue();
1415  void calculateIntersections();
1416  int splitEdge(int splitIndex);
1417  bool splitEdgesAtIntersections();
1418  void insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i);
1419  void removeUnwantedEdgesAndConnect();
1420  void removeUnusedPoints();
1421 
1430  };
1431 #ifdef Q_TRIANGULATOR_DEBUG
1432  friend class ComplexToSimple::DebugDialog;
1433 #endif
1434 
1435  //=================================//
1436  // QTriangulator::SimpleToMonotone //
1437  //=================================//
1438  friend class SimpleToMonotone;
1440  {
1441  public:
1442  inline SimpleToMonotone(QTriangulator<T> *parent) : m_parent(parent), m_edges(0), m_upperVertex(0) { }
1443  void decompose();
1444  private:
1445  enum VertexType {MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex};
1446 
1447  struct Edge
1448  {
1450  int helper, twin, next, previous;
1451  T from, to;
1454  int upper() const {return (pointingUp ? to : from);}
1455  int lower() const {return (pointingUp ? from : to);}
1456  };
1457 
1458  friend class CompareVertices;
1460  {
1461  public:
1462  CompareVertices(SimpleToMonotone *parent) : m_parent(parent) { }
1463  bool operator () (int i, int j) const;
1464  private:
1466  };
1467 
1468  void setupDataStructures();
1469  void removeZeroLengthEdges();
1470  void fillPriorityQueue();
1471  bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const;
1472  // Returns the rightmost edge not to the right of the given edge.
1473  QRBTree<int>::Node *searchEdgeLeftOfEdge(int edgeIndex) const;
1474  // Returns the rightmost edge left of the given point.
1475  QRBTree<int>::Node *searchEdgeLeftOfPoint(int pointIndex) const;
1476  void classifyVertex(int i);
1477  void classifyVertices();
1478  bool pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3);
1479  bool pointIsInSector(int vertex, int sector);
1480  int findSector(int edge, int vertex);
1481  void createDiagonal(int lower, int upper);
1482  void monotoneDecomposition();
1483 
1489  };
1490 
1491  //====================================//
1492  // QTriangulator::MonotoneToTriangles //
1493  //====================================//
1494  friend class MonotoneToTriangles;
1496  {
1497  public:
1498  inline MonotoneToTriangles(QTriangulator<T> *parent) : m_parent(parent) { }
1499  void decompose();
1500  private:
1501  inline T indices(int index) const {return m_parent->m_indices.at(index + m_first);}
1502  inline int next(int index) const {return (index + 1) % m_length;}
1503  inline int previous(int index) const {return (index + m_length - 1) % m_length;}
1504  inline bool less(int i, int j) const {return m_parent->m_vertices.at((qint32)indices(i)) < m_parent->m_vertices.at(indices(j));}
1505  inline bool leftOfEdge(int i, int j, int k) const
1506  {
1507  return qPointIsLeftOfLine(m_parent->m_vertices.at((qint32)indices(i)),
1508  m_parent->m_vertices.at((qint32)indices(j)), m_parent->m_vertices.at((qint32)indices(k)));
1509  }
1510 
1512  int m_first;
1514  };
1515 
1516  inline QTriangulator() : m_vertices(0) { }
1517 
1518  // Call this only once.
1519  void initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix);
1520  // Call this only once.
1521  void initialize(const QVectorPath &path, const QTransform &matrix, qreal lod);
1522  // Call this only once.
1523  void initialize(const QPainterPath &path, const QTransform &matrix, qreal lod);
1524  // Call either triangulate() or polyline() only once.
1525  QVertexSet<T> triangulate();
1526  QVertexSet<T> polyline();
1527 private:
1531 };
1532 
1533 //============================================================================//
1534 // QTriangulator //
1535 //============================================================================//
1536 
1537 template <typename T>
1539 {
1540  for (int i = 0; i < m_vertices.size(); ++i) {
1541  Q_ASSERT(qAbs(m_vertices.at(i).x) < (1 << 21));
1542  Q_ASSERT(qAbs(m_vertices.at(i).y) < (1 << 21));
1543  }
1544 
1546  m_hint |= QVectorPath::OddEvenFill;
1547 
1548  if (m_hint & QVectorPath::NonConvexShapeMask) {
1549  ComplexToSimple c2s(this);
1550  c2s.decompose();
1551  SimpleToMonotone s2m(this);
1552  s2m.decompose();
1553  }
1554  MonotoneToTriangles m2t(this);
1555  m2t.decompose();
1556 
1557  QVertexSet<T> result;
1558  result.indices = m_indices;
1559  result.vertices.resize(2 * m_vertices.size());
1560  for (int i = 0; i < m_vertices.size(); ++i) {
1561  result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / Q_FIXED_POINT_SCALE;
1562  result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / Q_FIXED_POINT_SCALE;
1563  }
1564  return result;
1565 }
1566 
1567 template <typename T>
1569 {
1570  QVertexSet<T> result;
1571  result.indices = m_indices;
1572  result.vertices.resize(2 * m_vertices.size());
1573  for (int i = 0; i < m_vertices.size(); ++i) {
1574  result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / Q_FIXED_POINT_SCALE;
1575  result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / Q_FIXED_POINT_SCALE;
1576  }
1577  return result;
1578 }
1579 
1580 template <typename T>
1581 void QTriangulator<T>::initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix)
1582 {
1583  m_hint = hint;
1584  m_vertices.resize(count);
1585  m_indices.resize(count + 1);
1586  for (int i = 0; i < count; ++i) {
1587  qreal x, y;
1588  matrix.map(polygon[2 * i + 0], polygon[2 * i + 1], &x, &y);
1589  m_vertices.at(i).x = qRound(x * Q_FIXED_POINT_SCALE);
1590  m_vertices.at(i).y = qRound(y * Q_FIXED_POINT_SCALE);
1591  m_indices[i] = i;
1592  }
1593  m_indices[count] = T(-1); //Q_TRIANGULATE_END_OF_POLYGON
1594 }
1595 
1596 template <typename T>
1597 void QTriangulator<T>::initialize(const QVectorPath &path, const QTransform &matrix, qreal lod)
1598 {
1599  m_hint = path.hints();
1600  // Curved paths will be converted to complex polygons.
1601  m_hint &= ~QVectorPath::CurvedShapeMask;
1602 
1603  const qreal *p = path.points();
1604  const QPainterPath::ElementType *e = path.elements();
1605  if (e) {
1606  for (int i = 0; i < path.elementCount(); ++i, ++e, p += 2) {
1607  switch (*e) {
1609  if (!m_indices.isEmpty())
1610  m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
1611  // Fall through.
1613  m_indices.push_back(T(m_vertices.size()));
1614  m_vertices.resize(m_vertices.size() + 1);
1615  qreal x, y;
1616  matrix.map(p[0], p[1], &x, &y);
1617  m_vertices.last().x = qRound(x * Q_FIXED_POINT_SCALE);
1618  m_vertices.last().y = qRound(y * Q_FIXED_POINT_SCALE);
1619  break;
1621  {
1622  qreal pts[8];
1623  for (int i = 0; i < 4; ++i)
1624  matrix.map(p[2 * i - 2], p[2 * i - 1], &pts[2 * i + 0], &pts[2 * i + 1]);
1625  for (int i = 0; i < 8; ++i)
1626  pts[i] *= lod;
1627  QBezier bezier = QBezier::fromPoints(QPointF(pts[0], pts[1]), QPointF(pts[2], pts[3]), QPointF(pts[4], pts[5]), QPointF(pts[6], pts[7]));
1628  QPolygonF poly = bezier.toPolygon();
1629  // Skip first point, it already exists in 'm_vertices'.
1630  for (int j = 1; j < poly.size(); ++j) {
1631  m_indices.push_back(T(m_vertices.size()));
1632  m_vertices.resize(m_vertices.size() + 1);
1633  m_vertices.last().x = qRound(poly.at(j).x() * Q_FIXED_POINT_SCALE / lod);
1634  m_vertices.last().y = qRound(poly.at(j).y() * Q_FIXED_POINT_SCALE / lod);
1635  }
1636  }
1637  i += 2;
1638  e += 2;
1639  p += 4;
1640  break;
1641  default:
1642  Q_ASSERT_X(0, "QTriangulator::triangulate", "Unexpected element type.");
1643  break;
1644  }
1645  }
1646  } else {
1647  for (int i = 0; i < path.elementCount(); ++i, p += 2) {
1648  m_indices.push_back(T(m_vertices.size()));
1649  m_vertices.resize(m_vertices.size() + 1);
1650  qreal x, y;
1651  matrix.map(p[0], p[1], &x, &y);
1652  m_vertices.last().x = qRound(x * Q_FIXED_POINT_SCALE);
1653  m_vertices.last().y = qRound(y * Q_FIXED_POINT_SCALE);
1654  }
1655  }
1656  m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
1657 }
1658 
1659 template <typename T>
1660 void QTriangulator<T>::initialize(const QPainterPath &path, const QTransform &matrix, qreal lod)
1661 {
1662  initialize(qtVectorPathForPath(path), matrix, lod);
1663 }
1664 
1665 //============================================================================//
1666 // QTriangulator::ComplexToSimple //
1667 //============================================================================//
1668 template <typename T>
1670 {
1671  m_initialPointCount = m_parent->m_vertices.size();
1672  initEdges();
1673  do {
1674  calculateIntersections();
1675  } while (splitEdgesAtIntersections());
1676 
1677  removeUnwantedEdgesAndConnect();
1678  removeUnusedPoints();
1679 
1680  m_parent->m_indices.clear();
1681  QBitArray processed(m_edges.size(), false);
1682  for (int first = 0; first < m_edges.size(); ++first) {
1683  // If already processed, or if unused path, skip.
1684  if (processed.at(first) || m_edges.at(first).next == -1)
1685  continue;
1686 
1687  int i = first;
1688  do {
1689  Q_ASSERT(!processed.at(i));
1690  Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i);
1691  m_parent->m_indices.push_back(m_edges.at(i).from);
1692  processed.setBit(i);
1693  i = m_edges.at(i).next; // CCW order
1694  } while (i != first);
1695  m_parent->m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
1696  }
1697 }
1698 
1699 template <typename T>
1701 {
1702  // Initialize edge structure.
1703  // 'next' and 'previous' are not being initialized at this point.
1704  int first = 0;
1705  for (int i = 0; i < m_parent->m_indices.size(); ++i) {
1706  if (m_parent->m_indices.at(i) == T(-1)) { // Q_TRIANGULATE_END_OF_POLYGON
1707  if (m_edges.size() != first)
1708  m_edges.last().to = m_edges.at(first).from;
1709  first = m_edges.size();
1710  } else {
1711  Q_ASSERT(i + 1 < m_parent->m_indices.size());
1712  // {node, from, to, next, previous, winding, mayIntersect, pointingUp, originallyPointingUp}
1713  Edge edge = {0, int(m_parent->m_indices.at(i)), int(m_parent->m_indices.at(i + 1)), -1, -1, 0, true, false, false};
1714  m_edges.add(edge);
1715  }
1716  }
1717  if (first != m_edges.size())
1718  m_edges.last().to = m_edges.at(first).from;
1719  for (int i = 0; i < m_edges.size(); ++i) {
1720  m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp =
1721  m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from);
1722  }
1723 }
1724 
1725 // Return true if new intersection was found
1726 template <typename T>
1728 {
1729  const Edge &e1 = m_edges.at(left);
1730  const Edge &e2 = m_edges.at(right);
1731 
1732  const QPodPoint &u1 = m_parent->m_vertices.at((qint32)e1.from);
1733  const QPodPoint &u2 = m_parent->m_vertices.at((qint32)e1.to);
1734  const QPodPoint &v1 = m_parent->m_vertices.at((qint32)e2.from);
1735  const QPodPoint &v2 = m_parent->m_vertices.at((qint32)e2.to);
1736  if (qMax(u1.x, u2.x) <= qMin(v1.x, v2.x))
1737  return false;
1738 
1739  quint64 key = (left > right ? (quint64(right) << 32) | quint64(left) : (quint64(left) << 32) | quint64(right));
1740  if (m_processedEdgePairs.contains(key))
1741  return false;
1742  m_processedEdgePairs.insert(key);
1743 
1744  Intersection intersection;
1745  intersection.leftEdge = left;
1746  intersection.rightEdge = right;
1747  intersection.intersectionPoint = QT_PREPEND_NAMESPACE(qIntersectionPoint)(u1, u2, v1, v2);
1748 
1749  if (!intersection.intersectionPoint.isValid())
1750  return false;
1751 
1752  Q_ASSERT(intersection.intersectionPoint.isOnLine(u1, u2));
1753  Q_ASSERT(intersection.intersectionPoint.isOnLine(v1, v2));
1754 
1755  intersection.vertex = m_parent->m_vertices.size();
1756  m_topIntersection.push(intersection);
1757  m_parent->m_vertices.add(intersection.intersectionPoint.round());
1758  return true;
1759 }
1760 
1761 template <typename T>
1762 bool QTriangulator<T>::ComplexToSimple::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const
1763 {
1764  const Edge &leftEdge = m_edges.at(leftEdgeIndex);
1765  const Edge &rightEdge = m_edges.at(rightEdgeIndex);
1766  const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
1767  const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
1768  const QPodPoint &upper = m_parent->m_vertices.at(leftEdge.upper());
1769  if (upper.x < qMin(l.x, u.x))
1770  return true;
1771  if (upper.x > qMax(l.x, u.x))
1772  return false;
1774  // d < 0: left, d > 0: right, d == 0: on top
1775  if (d == 0)
1776  d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(leftEdge.lower()), l, u);
1777  return d < 0;
1778 }
1779 
1780 template <typename T>
1781 QRBTreeIntNodePointer QTriangulator<T>::ComplexToSimple::searchEdgeLeftOf(int edgeIndex) const
1782 {
1783  QRBTree<int>::Node *current = m_edgeList.root;
1784  QRBTree<int>::Node *result = 0;
1785  while (current) {
1786  if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
1787  current = current->left;
1788  } else {
1789  result = current;
1790  current = current->right;
1791  }
1792  }
1793  return result;
1794 }
1795 
1796 template <typename T>
1797 QRBTreeIntNodePointer QTriangulator<T>::ComplexToSimple::searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const
1798 {
1799  if (!m_edgeList.root)
1800  return after;
1801  QRBTree<int>::Node *result = after;
1802  QRBTree<int>::Node *current = (after ? m_edgeList.next(after) : m_edgeList.front(m_edgeList.root));
1803  while (current) {
1804  if (edgeIsLeftOfEdge(edgeIndex, current->data))
1805  return result;
1806  result = current;
1807  current = m_edgeList.next(current);
1808  }
1809  return result;
1810 }
1811 
1812 template <typename T>
1814 {
1815  QRBTree<int>::Node *current = m_edgeList.root;
1816  QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0);
1817  while (current) {
1818  const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1819  const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1821  if (d == 0) {
1822  result.first = result.second = current;
1823  break;
1824  }
1825  current = (d < 0 ? current->left : current->right);
1826  }
1827  if (current == 0)
1828  return result;
1829 
1830  current = result.first->left;
1831  while (current) {
1832  const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1833  const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1835  Q_ASSERT(d >= 0);
1836  if (d == 0) {
1837  result.first = current;
1838  current = current->left;
1839  } else {
1840  current = current->right;
1841  }
1842  }
1843 
1844  current = result.second->right;
1845  while (current) {
1846  const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1847  const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1849  Q_ASSERT(d <= 0);
1850  if (d == 0) {
1851  result.second = current;
1852  current = current->right;
1853  } else {
1854  current = current->left;
1855  }
1856  }
1857 
1858  return result;
1859 }
1860 
1861 template <typename T>
1863 {
1864  QRBTree<int>::Node *current = m_edgeList.root;
1865  QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0);
1866 
1867  while (current) {
1868  const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1869  const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1871  if (d == 0)
1872  break;
1873  if (d < 0) {
1874  result.second = current;
1875  current = current->left;
1876  } else {
1877  result.first = current;
1878  current = current->right;
1879  }
1880  }
1881 
1882  if (!current)
1883  return result;
1884 
1885  QRBTree<int>::Node *mid = current;
1886 
1887  current = mid->left;
1888  while (current) {
1889  const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1890  const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1892  Q_ASSERT(d >= 0);
1893  if (d == 0) {
1894  current = current->left;
1895  } else {
1896  result.first = current;
1897  current = current->right;
1898  }
1899  }
1900 
1901  current = mid->right;
1902  while (current) {
1903  const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1904  const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1906  Q_ASSERT(d <= 0);
1907  if (d == 0) {
1908  current = current->right;
1909  } else {
1910  result.second = current;
1911  current = current->left;
1912  }
1913  }
1914 
1915  return result;
1916 }
1917 
1918 template <typename T>
1920 {
1921  Q_ASSERT(leftmost && rightmost);
1922 
1923  // Split.
1924  for (;;) {
1925  const QPodPoint &u = m_parent->m_vertices.at(m_edges.at(leftmost->data).from);
1926  const QPodPoint &v = m_parent->m_vertices.at(m_edges.at(leftmost->data).to);
1927  Q_ASSERT(intersectionPoint.isOnLine(u, v));
1928  const Split split = {vertex, leftmost->data, intersectionPoint.isAccurate()};
1929  if (intersectionPoint.xOffset.numerator != 0 || intersectionPoint.yOffset.numerator != 0 || (intersectionPoint.upperLeft != u && intersectionPoint.upperLeft != v))
1930  m_splits.add(split);
1931  if (leftmost == rightmost)
1932  break;
1933  leftmost = m_edgeList.next(leftmost);
1934  }
1935 }
1936 
1937 template <typename T>
1939 {
1940  Q_ASSERT(leftmost && rightmost);
1941 
1942  QRBTree<int>::Node *storeLeftmost = leftmost;
1943  QRBTree<int>::Node *storeRightmost = rightmost;
1944 
1945  // Reorder.
1946  while (leftmost != rightmost) {
1947  Edge &left = m_edges.at(leftmost->data);
1948  Edge &right = m_edges.at(rightmost->data);
1949  qSwap(left.node, right.node);
1950  qSwap(leftmost->data, rightmost->data);
1951  leftmost = m_edgeList.next(leftmost);
1952  if (leftmost == rightmost)
1953  break;
1954  rightmost = m_edgeList.previous(rightmost);
1955  }
1956 
1957  rightmost = m_edgeList.next(storeRightmost);
1958  leftmost = m_edgeList.previous(storeLeftmost);
1959  if (leftmost)
1960  calculateIntersection(leftmost->data, storeLeftmost->data);
1961  if (rightmost)
1962  calculateIntersection(storeRightmost->data, rightmost->data);
1963 }
1964 
1965 template <typename T>
1967 {
1968  QIntersectionPoint eventPoint2 = QT_PREPEND_NAMESPACE(qIntersectionPoint)(eventPoint);
1969  while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint < eventPoint2) {
1970  Intersection intersection = m_topIntersection.pop();
1971 
1972  QIntersectionPoint currentIntersectionPoint = intersection.intersectionPoint;
1973  int currentVertex = intersection.vertex;
1974 
1975  QRBTree<int>::Node *leftmost = m_edges.at(intersection.leftEdge).node;
1976  QRBTree<int>::Node *rightmost = m_edges.at(intersection.rightEdge).node;
1977 
1978  for (;;) {
1979  QRBTree<int>::Node *previous = m_edgeList.previous(leftmost);
1980  if (!previous)
1981  break;
1982  const Edge &edge = m_edges.at(previous->data);
1983  const QPodPoint &u = m_parent->m_vertices.at((qint32)edge.from);
1984  const QPodPoint &v = m_parent->m_vertices.at((qint32)edge.to);
1985  if (!currentIntersectionPoint.isOnLine(u, v)) {
1986  Q_ASSERT(!currentIntersectionPoint.isAccurate() || qCross(currentIntersectionPoint.upperLeft - u, v - u) != 0);
1987  break;
1988  }
1989  leftmost = previous;
1990  }
1991 
1992  for (;;) {
1993  QRBTree<int>::Node *next = m_edgeList.next(rightmost);
1994  if (!next)
1995  break;
1996  const Edge &edge = m_edges.at(next->data);
1997  const QPodPoint &u = m_parent->m_vertices.at((qint32)edge.from);
1998  const QPodPoint &v = m_parent->m_vertices.at((qint32)edge.to);
1999  if (!currentIntersectionPoint.isOnLine(u, v)) {
2000  Q_ASSERT(!currentIntersectionPoint.isAccurate() || qCross(currentIntersectionPoint.upperLeft - u, v - u) != 0);
2001  break;
2002  }
2003  rightmost = next;
2004  }
2005 
2006  Q_ASSERT(leftmost && rightmost);
2007  splitEdgeListRange(leftmost, rightmost, currentVertex, currentIntersectionPoint);
2008  reorderEdgeListRange(leftmost, rightmost);
2009 
2010  while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= currentIntersectionPoint)
2011  m_topIntersection.pop();
2012 
2013 #ifdef Q_TRIANGULATOR_DEBUG
2014  DebugDialog dialog(this, intersection.vertex);
2015  dialog.exec();
2016 #endif
2017 
2018  }
2019 }
2020 
2021 template <typename T>
2023 {
2024  m_events.reset();
2025  m_events.reserve(m_edges.size() * 2);
2026  for (int i = 0; i < m_edges.size(); ++i) {
2027  Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1);
2028  Q_ASSERT(m_edges.at(i).node == 0);
2029  Q_ASSERT(m_edges.at(i).pointingUp == m_edges.at(i).originallyPointingUp);
2030  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)));
2031  // Ignore zero-length edges.
2032  if (m_parent->m_vertices.at(m_edges.at(i).to) != m_parent->m_vertices.at(m_edges.at(i).from)) {
2033  QPodPoint upper = m_parent->m_vertices.at(m_edges.at(i).upper());
2034  QPodPoint lower = m_parent->m_vertices.at(m_edges.at(i).lower());
2035  Event upperEvent = {{upper.x, upper.y}, Event::Upper, i};
2036  Event lowerEvent = {{lower.x, lower.y}, Event::Lower, i};
2037  m_events.add(upperEvent);
2038  m_events.add(lowerEvent);
2039  }
2040  }
2041  //qSort(m_events.data(), m_events.data() + m_events.size());
2042  sort(m_events.data(), m_events.size());
2043 }
2044 
2045 template <typename T>
2047 {
2048  fillPriorityQueue();
2049 
2050  Q_ASSERT(m_topIntersection.empty());
2051  Q_ASSERT(m_edgeList.root == 0);
2052 
2053  // Find all intersection points.
2054  while (!m_events.isEmpty()) {
2055  Event event = m_events.last();
2056  sortEdgeList(event.point);
2057 
2058  // Find all edges in the edge list that contain the current vertex and mark them to be split later.
2059  QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> range = bounds(event.point);
2060  QRBTree<int>::Node *leftNode = range.first ? m_edgeList.previous(range.first) : 0;
2061  int vertex = (event.type == Event::Upper ? m_edges.at(event.edge).upper() : m_edges.at(event.edge).lower());
2062  QIntersectionPoint eventPoint = QT_PREPEND_NAMESPACE(qIntersectionPoint)(event.point);
2063 
2064  if (range.first != 0) {
2065  splitEdgeListRange(range.first, range.second, vertex, eventPoint);
2066  reorderEdgeListRange(range.first, range.second);
2067  }
2068 
2069  // Handle the edges with start or end point in the current vertex.
2070  while (!m_events.isEmpty() && m_events.last().point == event.point) {
2071  event = m_events.last();
2072  m_events.pop_back();
2073  int i = event.edge;
2074 
2075  if (m_edges.at(i).node) {
2076  // Remove edge from edge list.
2077  Q_ASSERT(event.type == Event::Lower);
2078  QRBTree<int>::Node *left = m_edgeList.previous(m_edges.at(i).node);
2079  QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node);
2080  m_edgeList.deleteNode(m_edges.at(i).node);
2081  if (!left || !right)
2082  continue;
2083  calculateIntersection(left->data, right->data);
2084  } else {
2085  // Insert edge into edge list.
2086  Q_ASSERT(event.type == Event::Upper);
2087  QRBTree<int>::Node *left = searchEdgeLeftOf(i, leftNode);
2088  m_edgeList.attachAfter(left, m_edges.at(i).node = m_edgeList.newNode());
2089  m_edges.at(i).node->data = i;
2090  QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node);
2091  if (left)
2092  calculateIntersection(left->data, i);
2093  if (right)
2094  calculateIntersection(i, right->data);
2095  }
2096  }
2097  while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= eventPoint)
2098  m_topIntersection.pop();
2099 #ifdef Q_TRIANGULATOR_DEBUG
2100  DebugDialog dialog(this, vertex);
2101  dialog.exec();
2102 #endif
2103  }
2104  m_processedEdgePairs.clear();
2105 }
2106 
2107 // Split an edge into two pieces at the given point.
2108 // The upper piece is pushed to the end of the 'm_edges' vector.
2109 // The lower piece replaces the old edge.
2110 // Return the edge whose 'from' is 'pointIndex'.
2111 template <typename T>
2113 {
2114  const Split &split = m_splits.at(splitIndex);
2115  Edge &lowerEdge = m_edges.at(split.edge);
2116  Q_ASSERT(lowerEdge.node == 0);
2117  Q_ASSERT(lowerEdge.previous == -1 && lowerEdge.next == -1);
2118 
2119  if (lowerEdge.from == split.vertex)
2120  return split.edge;
2121  if (lowerEdge.to == split.vertex)
2122  return lowerEdge.next;
2123 
2124  // Check that angle >= 90 degrees.
2125  //Q_ASSERT(qDot(m_points.at(m_edges.at(edgeIndex).from) - m_points.at(pointIndex),
2126  // m_points.at(m_edges.at(edgeIndex).to) - m_points.at(pointIndex)) <= 0);
2127 
2128  Edge upperEdge = lowerEdge;
2129  upperEdge.mayIntersect |= !split.accurate; // The edge may have been split before at an inaccurate split point.
2130  lowerEdge.mayIntersect = !split.accurate;
2131  if (lowerEdge.pointingUp) {
2132  lowerEdge.to = upperEdge.from = split.vertex;
2133  m_edges.add(upperEdge);
2134  return m_edges.size() - 1;
2135  } else {
2136  lowerEdge.from = upperEdge.to = split.vertex;
2137  m_edges.add(upperEdge);
2138  return split.edge;
2139  }
2140 }
2141 
2142 template <typename T>
2144 {
2145  for (int i = 0; i < m_edges.size(); ++i)
2146  m_edges.at(i).mayIntersect = false;
2147  bool checkForNewIntersections = false;
2148  for (int i = 0; i < m_splits.size(); ++i) {
2149  splitEdge(i);
2150  checkForNewIntersections |= !m_splits.at(i).accurate;
2151  }
2152  for (int i = 0; i < m_edges.size(); ++i) {
2153  m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp =
2154  m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from);
2155  }
2156  m_splits.reset();
2157  return checkForNewIntersections;
2158 }
2159 
2160 template <typename T>
2162 {
2163  // Edges with zero length should not reach this part.
2164  Q_ASSERT(m_parent->m_vertices.at(m_edges.at(i).from) != m_parent->m_vertices.at(m_edges.at(i).to));
2165 
2166  // Skip edges with unwanted winding number.
2167  int windingNumber = m_edges.at(i).winding;
2168  if (m_edges.at(i).originallyPointingUp)
2169  ++windingNumber;
2170 
2171  // Make sure exactly one fill rule is specified.
2172  Q_ASSERT(((m_parent->m_hint & QVectorPath::WindingFill) != 0) != ((m_parent->m_hint & QVectorPath::OddEvenFill) != 0));
2173 
2174  if ((m_parent->m_hint & QVectorPath::WindingFill) && windingNumber != 0 && windingNumber != 1)
2175  return;
2176 
2177  // Skip cancelling edges.
2178  if (!orderedEdges.isEmpty()) {
2179  int j = orderedEdges[orderedEdges.size() - 1];
2180  // If the last edge is already connected in one end, it should not be cancelled.
2181  if (m_edges.at(j).next == -1 && m_edges.at(j).previous == -1
2182  && (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(j).to))
2183  && (m_parent->m_vertices.at(m_edges.at(i).to) == m_parent->m_vertices.at(m_edges.at(j).from))) {
2184  orderedEdges.removeLast();
2185  return;
2186  }
2187  }
2188  orderedEdges.append(i);
2189 }
2190 
2191 template <typename T>
2193 {
2194  Q_ASSERT(m_edgeList.root == 0);
2195  // Initialize priority queue.
2196  fillPriorityQueue();
2197 
2198  ShortArray orderedEdges;
2199 
2200  while (!m_events.isEmpty()) {
2201  Event event = m_events.last();
2202  int edgeIndex = event.edge;
2203 
2204  // Check that all the edges in the list crosses the current scanline
2205  //if (m_edgeList.root) {
2206  // for (QRBTree<int>::Node *node = m_edgeList.front(m_edgeList.root); node; node = m_edgeList.next(node)) {
2207  // Q_ASSERT(event.point <= m_points.at(m_edges.at(node->data).lower()));
2208  // }
2209  //}
2210 
2211  orderedEdges.clear();
2212  QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> b = outerBounds(event.point);
2213  if (m_edgeList.root) {
2214  QRBTree<int>::Node *current = (b.first ? m_edgeList.next(b.first) : m_edgeList.front(m_edgeList.root));
2215  // Process edges that are going to be removed from the edge list at the current event point.
2216  while (current != b.second) {
2217  Q_ASSERT(current);
2218  Q_ASSERT(m_edges.at(current->data).node == current);
2219  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)));
2220  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);
2221  insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
2222  current = m_edgeList.next(current);
2223  }
2224  }
2225 
2226  // Remove edges above the event point, insert edges below the event point.
2227  do {
2228  event = m_events.last();
2229  m_events.pop_back();
2230  edgeIndex = event.edge;
2231 
2232  // Edges with zero length should not reach this part.
2233  Q_ASSERT(m_parent->m_vertices.at(m_edges.at(edgeIndex).from) != m_parent->m_vertices.at(m_edges.at(edgeIndex).to));
2234 
2235  if (m_edges.at(edgeIndex).node) {
2236  Q_ASSERT(event.type == Event::Lower);
2237  Q_ASSERT(event.point == m_parent->m_vertices.at(m_edges.at(event.edge).lower()));
2238  m_edgeList.deleteNode(m_edges.at(edgeIndex).node);
2239  } else {
2240  Q_ASSERT(event.type == Event::Upper);
2241  Q_ASSERT(event.point == m_parent->m_vertices.at(m_edges.at(event.edge).upper()));
2242  QRBTree<int>::Node *left = searchEdgeLeftOf(edgeIndex, b.first);
2243  m_edgeList.attachAfter(left, m_edges.at(edgeIndex).node = m_edgeList.newNode());
2244  m_edges.at(edgeIndex).node->data = edgeIndex;
2245  }
2246  } while (!m_events.isEmpty() && m_events.last().point == event.point);
2247 
2248  if (m_edgeList.root) {
2249  QRBTree<int>::Node *current = (b.first ? m_edgeList.next(b.first) : m_edgeList.front(m_edgeList.root));
2250 
2251  // Calculate winding number and turn counter-clockwise.
2252  int currentWindingNumber = (b.first ? m_edges.at(b.first->data).winding : 0);
2253  while (current != b.second) {
2254  Q_ASSERT(current);
2255  //Q_ASSERT(b.second == 0 || m_edgeList.order(current, b.second) < 0);
2256  int i = current->data;
2257  Q_ASSERT(m_edges.at(i).node == current);
2258 
2259  // Winding number.
2260  int ccwWindingNumber = m_edges.at(i).winding = currentWindingNumber;
2261  if (m_edges.at(i).originallyPointingUp) {
2262  --m_edges.at(i).winding;
2263  } else {
2264  ++m_edges.at(i).winding;
2265  ++ccwWindingNumber;
2266  }
2267  currentWindingNumber = m_edges.at(i).winding;
2268 
2269  // Turn counter-clockwise.
2270  if ((ccwWindingNumber & 1) == 0) {
2271  Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1);
2272  qSwap(m_edges.at(i).from, m_edges.at(i).to);
2273  m_edges.at(i).pointingUp = !m_edges.at(i).pointingUp;
2274  }
2275 
2276  current = m_edgeList.next(current);
2277  }
2278 
2279  // Process edges that were inserted into the edge list at the current event point.
2280  current = (b.second ? m_edgeList.previous(b.second) : m_edgeList.back(m_edgeList.root));
2281  while (current != b.first) {
2282  Q_ASSERT(current);
2283  Q_ASSERT(m_edges.at(current->data).node == current);
2284  insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
2285  current = m_edgeList.previous(current);
2286  }
2287  }
2288  if (orderedEdges.isEmpty())
2289  continue;
2290 
2291  Q_ASSERT((orderedEdges.size() & 1) == 0);
2292 
2293  // Connect edges.
2294  // First make sure the first edge point towards the current point.
2295  int i;
2296  if (m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).from) == event.point) {
2297  i = 1;
2298  int copy = orderedEdges[0]; // Make copy in case the append() will cause a reallocation.
2299  orderedEdges.append(copy);
2300  } else {
2301  Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).to) == event.point);
2302  i = 0;
2303  }
2304 
2305  // Remove references to duplicate points. First find the point with lowest index.
2306  int pointIndex = INT_MAX;
2307  for (int j = i; j < orderedEdges.size(); j += 2) {
2308  Q_ASSERT(j + 1 < orderedEdges.size());
2309  Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[j]).to) == event.point);
2310  Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[j + 1]).from) == event.point);
2311  if (m_edges.at(orderedEdges[j]).to < pointIndex)
2312  pointIndex = m_edges.at(orderedEdges[j]).to;
2313  if (m_edges.at(orderedEdges[j + 1]).from < pointIndex)
2314  pointIndex = m_edges.at(orderedEdges[j + 1]).from;
2315  }
2316 
2317  for (; i < orderedEdges.size(); i += 2) {
2318  // Remove references to duplicate points by making all edges reference one common point.
2319  m_edges.at(orderedEdges[i]).to = m_edges.at(orderedEdges[i + 1]).from = pointIndex;
2320 
2321  Q_ASSERT(m_edges.at(orderedEdges[i]).pointingUp || m_edges.at(orderedEdges[i]).previous != -1);
2322  Q_ASSERT(!m_edges.at(orderedEdges[i + 1]).pointingUp || m_edges.at(orderedEdges[i + 1]).next != -1);
2323 
2324  m_edges.at(orderedEdges[i]).next = orderedEdges[i + 1];
2325  m_edges.at(orderedEdges[i + 1]).previous = orderedEdges[i];
2326  }
2327  } // end while
2328 }
2329 
2330 template <typename T>
2332  QBitArray used(m_parent->m_vertices.size(), false);
2333  for (int i = 0; i < m_edges.size(); ++i) {
2334  Q_ASSERT((m_edges.at(i).previous == -1) == (m_edges.at(i).next == -1));
2335  if (m_edges.at(i).next != -1)
2336  used.setBit(m_edges.at(i).from);
2337  }
2338  QDataBuffer<quint32> newMapping(m_parent->m_vertices.size());
2339  newMapping.resize(m_parent->m_vertices.size());
2340  int count = 0;
2341  for (int i = 0; i < m_parent->m_vertices.size(); ++i) {
2342  if (used.at(i)) {
2343  m_parent->m_vertices.at(count) = m_parent->m_vertices.at(i);
2344  newMapping.at(i) = count;
2345  ++count;
2346  }
2347  }
2348  m_parent->m_vertices.resize(count);
2349  for (int i = 0; i < m_edges.size(); ++i) {
2350  m_edges.at(i).from = newMapping.at(m_edges.at(i).from);
2351  m_edges.at(i).to = newMapping.at(m_edges.at(i).to);
2352  }
2353 }
2354 
2355 template <typename T>
2357 {
2358  int cmp = comparePoints(m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from),
2359  m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from));
2360  if (cmp == 0) {
2361  cmp = comparePoints(m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).to),
2362  m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).to));
2363  }
2364  return cmp > 0;
2365 }
2366 
2367 template <typename T>
2369 {
2370  if (point == other.point)
2371  return type < other.type; // 'Lower' has higher priority than 'Upper'.
2372  return other.point < point;
2373 }
2374 
2375 //============================================================================//
2376 // QTriangulator::ComplexToSimple::DebugDialog //
2377 //============================================================================//
2378 
2379 #ifdef Q_TRIANGULATOR_DEBUG
2380 template <typename T>
2382  : m_parent(parent), m_vertex(currentVertex)
2383 {
2384  QDataBuffer<QPodPoint> &vertices = m_parent->m_parent->m_vertices;
2385  if (vertices.isEmpty())
2386  return;
2387 
2388  int minX, maxX, minY, maxY;
2389  minX = maxX = vertices.at(0).x;
2390  minY = maxY = vertices.at(0).y;
2391  for (int i = 1; i < vertices.size(); ++i) {
2392  minX = qMin(minX, vertices.at(i).x);
2393  maxX = qMax(maxX, vertices.at(i).x);
2394  minY = qMin(minY, vertices.at(i).y);
2395  maxY = qMax(maxY, vertices.at(i).y);
2396  }
2397  int w = maxX - minX;
2398  int h = maxY - minY;
2399  qreal border = qMin(w, h) / 10.0;
2400  m_window = QRectF(minX - border, minY - border, (maxX - minX + 2 * border), (maxY - minY + 2 * border));
2401 }
2402 
2403 template <typename T>
2405 {
2406  QPainter p(this);
2408  p.fillRect(rect(), Qt::black);
2409  QDataBuffer<QPodPoint> &vertices = m_parent->m_parent->m_vertices;
2410  if (vertices.isEmpty())
2411  return;
2412 
2413  qreal halfPointSize = qMin(m_window.width(), m_window.height()) / 300.0;
2414  p.setWindow(m_window.toRect());
2415 
2416  p.setPen(Qt::white);
2417 
2418  QDataBuffer<Edge> &edges = m_parent->m_edges;
2419  for (int i = 0; i < edges.size(); ++i) {
2420  QPodPoint u = vertices.at(edges.at(i).from);
2421  QPodPoint v = vertices.at(edges.at(i).to);
2422  p.drawLine(u.x, u.y, v.x, v.y);
2423  }
2424 
2425  for (int i = 0; i < vertices.size(); ++i) {
2426  QPodPoint q = vertices.at(i);
2427  p.fillRect(QRectF(q.x - halfPointSize, q.y - halfPointSize, 2 * halfPointSize, 2 * halfPointSize), Qt::red);
2428  }
2429 
2431  p.setOpacity(0.5);
2432  int count = 0;
2433  if (m_parent->m_edgeList.root) {
2434  QRBTree<int>::Node *current = m_parent->m_edgeList.front(m_parent->m_edgeList.root);
2435  while (current) {
2436  p.setPen(colors[count++ % 6]);
2437  QPodPoint u = vertices.at(edges.at(current->data).from);
2438  QPodPoint v = vertices.at(edges.at(current->data).to);
2439  p.drawLine(u.x, u.y, v.x, v.y);
2440  current = m_parent->m_edgeList.next(current);
2441  }
2442  }
2443 
2444  p.setOpacity(1.0);
2445  QPodPoint q = vertices.at(m_vertex);
2446  p.fillRect(QRectF(q.x - halfPointSize, q.y - halfPointSize, 2 * halfPointSize, 2 * halfPointSize), Qt::green);
2447 
2448  p.setPen(Qt::gray);
2449  QDataBuffer<Split> &splits = m_parent->m_splits;
2450  for (int i = 0; i < splits.size(); ++i) {
2451  QPodPoint q = vertices.at(splits.at(i).vertex);
2452  QPodPoint u = vertices.at(edges.at(splits.at(i).edge).from) - q;
2453  QPodPoint v = vertices.at(edges.at(splits.at(i).edge).to) - q;
2454  qreal uLen = sqrt(qreal(qDot(u, u)));
2455  qreal vLen = sqrt(qreal(qDot(v, v)));
2456  if (uLen) {
2457  u.x *= 2 * halfPointSize / uLen;
2458  u.y *= 2 * halfPointSize / uLen;
2459  }
2460  if (vLen) {
2461  v.x *= 2 * halfPointSize / vLen;
2462  v.y *= 2 * halfPointSize / vLen;
2463  }
2464  u += q;
2465  v += q;
2466  p.drawLine(u.x, u.y, v.x, v.y);
2467  }
2468 }
2469 
2470 template <typename T>
2472 {
2473  qreal scale = exp(-0.001 * event->delta());
2474  QPointF center = m_window.center();
2475  QPointF delta = scale * (m_window.bottomRight() - center);
2476  m_window = QRectF(center - delta, center + delta);
2477  event->accept();
2478  update();
2479 }
2480 
2481 template <typename T>
2483 {
2484  if (event->buttons() & Qt::LeftButton) {
2485  QPointF delta = event->pos() - m_lastMousePos;
2486  delta.setX(delta.x() * m_window.width() / width());
2487  delta.setY(delta.y() * m_window.height() / height());
2488  m_window.translate(-delta.x(), -delta.y());
2489  m_lastMousePos = event->pos();
2490  event->accept();
2491  update();
2492  }
2493 }
2494 
2495 template <typename T>
2497 {
2498  if (event->button() == Qt::LeftButton)
2499  m_lastMousePos = event->pos();
2500  event->accept();
2501 }
2502 
2503 
2504 #endif
2505 
2506 //============================================================================//
2507 // QTriangulator::SimpleToMonotone //
2508 //============================================================================//
2509 template <typename T>
2511 {
2512  setupDataStructures();
2513  removeZeroLengthEdges();
2514  monotoneDecomposition();
2515 
2516  m_parent->m_indices.clear();
2517  QBitArray processed(m_edges.size(), false);
2518  for (int first = 0; first < m_edges.size(); ++first) {
2519  if (processed.at(first))
2520  continue;
2521  int i = first;
2522  do {
2523  Q_ASSERT(!processed.at(i));
2524  Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i);
2525  m_parent->m_indices.push_back(m_edges.at(i).from);
2526  processed.setBit(i);
2527  i = m_edges.at(i).next;
2528  } while (i != first);
2529  if (m_parent->m_indices.size() > 0 && m_parent->m_indices.back() != T(-1)) // Q_TRIANGULATE_END_OF_POLYGON
2530  m_parent->m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
2531  }
2532 }
2533 
2534 template <typename T>
2536 {
2537  int i = 0;
2538  Edge e;
2539  e.node = 0;
2540  e.twin = -1;
2541 
2542  while (i + 3 <= m_parent->m_indices.size()) {
2543  int start = m_edges.size();
2544 
2545  do {
2546  e.from = m_parent->m_indices.at(i);
2547  e.type = RegularVertex;
2548  e.next = m_edges.size() + 1;
2549  e.previous = m_edges.size() - 1;
2550  m_edges.add(e);
2551  ++i;
2552  Q_ASSERT(i < m_parent->m_indices.size());
2553  } while (m_parent->m_indices.at(i) != T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
2554 
2555  m_edges.last().next = start;
2556  m_edges.at(start).previous = m_edges.size() - 1;
2557  ++i; // Skip Q_TRIANGULATE_END_OF_POLYGON.
2558  }
2559 
2560  for (i = 0; i < m_edges.size(); ++i) {
2561  m_edges.at(i).to = m_edges.at(m_edges.at(i).next).from;
2562  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);
2563  m_edges.at(i).helper = -1; // Not initialized here.
2564  }
2565 }
2566 
2567 template <typename T>
2569 {
2570  for (int i = 0; i < m_edges.size(); ++i) {
2571  if (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(i).to)) {
2572  m_edges.at(m_edges.at(i).previous).next = m_edges.at(i).next;
2573  m_edges.at(m_edges.at(i).next).previous = m_edges.at(i).previous;
2574  m_edges.at(m_edges.at(i).next).from = m_edges.at(i).from;
2575  m_edges.at(i).next = -1; // Mark as removed.
2576  }
2577  }
2578 
2579  QDataBuffer<int> newMapping(m_edges.size());
2580  newMapping.resize(m_edges.size());
2581  int count = 0;
2582  for (int i = 0; i < m_edges.size(); ++i) {
2583  if (m_edges.at(i).next != -1) {
2584  m_edges.at(count) = m_edges.at(i);
2585  newMapping.at(i) = count;
2586  ++count;
2587  }
2588  }
2589  m_edges.resize(count);
2590  for (int i = 0; i < m_edges.size(); ++i) {
2591  m_edges.at(i).next = newMapping.at(m_edges.at(i).next);
2592  m_edges.at(i).previous = newMapping.at(m_edges.at(i).previous);
2593  }
2594 }
2595 
2596 template <typename T>
2598 {
2599  m_upperVertex.reset();
2600  m_upperVertex.reserve(m_edges.size());
2601  for (int i = 0; i < m_edges.size(); ++i)
2602  m_upperVertex.add(i);
2603  CompareVertices cmp(this);
2604  //qSort(m_upperVertex.data(), m_upperVertex.data() + m_upperVertex.size(), cmp);
2605  sort(m_upperVertex.data(), m_upperVertex.size(), cmp);
2606  //for (int i = 1; i < m_upperVertex.size(); ++i) {
2607  // Q_ASSERT(!cmp(m_upperVertex.at(i), m_upperVertex.at(i - 1)));
2608  //}
2609 }
2610 
2611 template <typename T>
2612 bool QTriangulator<T>::SimpleToMonotone::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const
2613 {
2614  const Edge &leftEdge = m_edges.at(leftEdgeIndex);
2615  const Edge &rightEdge = m_edges.at(rightEdgeIndex);
2616  const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
2617  const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
2618  qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(leftEdge.upper()), l, u);
2619  // d < 0: left, d > 0: right, d == 0: on top
2620  if (d == 0)
2621  d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(leftEdge.lower()), l, u);
2622  return d < 0;
2623 }
2624 
2625 // Returns the rightmost edge not to the right of the given edge.
2626 template <typename T>
2628 {
2629  QRBTree<int>::Node *current = m_edgeList.root;
2630  QRBTree<int>::Node *result = 0;
2631  while (current) {
2632  if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
2633  current = current->left;
2634  } else {
2635  result = current;
2636  current = current->right;
2637  }
2638  }
2639  return result;
2640 }
2641 
2642 // Returns the rightmost edge left of the given point.
2643 template <typename T>
2645 {
2646  QRBTree<int>::Node *current = m_edgeList.root;
2647  QRBTree<int>::Node *result = 0;
2648  while (current) {
2649  const QPodPoint &p1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
2650  const QPodPoint &p2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
2651  qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(pointIndex), p1, p2);
2652  if (d <= 0) {
2653  current = current->left;
2654  } else {
2655  result = current;
2656  current = current->right;
2657  }
2658  }
2659  return result;
2660 }
2661 
2662 template <typename T>
2664 {
2665  Edge &e2 = m_edges.at(i);
2666  const Edge &e1 = m_edges.at(e2.previous);
2667 
2668  bool startOrSplit = (e1.pointingUp && !e2.pointingUp);
2669  bool endOrMerge = (!e1.pointingUp && e2.pointingUp);
2670 
2671  const QPodPoint &p1 = m_parent->m_vertices.at(e1.from);
2672  const QPodPoint &p2 = m_parent->m_vertices.at(e2.from);
2673  const QPodPoint &p3 = m_parent->m_vertices.at(e2.to);
2675  Q_ASSERT(d != 0 || (!startOrSplit && !endOrMerge));
2676 
2677  e2.type = RegularVertex;
2678 
2679  if (m_clockwiseOrder) {
2680  if (startOrSplit)
2681  e2.type = (d < 0 ? SplitVertex : StartVertex);
2682  else if (endOrMerge)
2683  e2.type = (d < 0 ? MergeVertex : EndVertex);
2684  } else {
2685  if (startOrSplit)
2686  e2.type = (d > 0 ? SplitVertex : StartVertex);
2687  else if (endOrMerge)
2688  e2.type = (d > 0 ? MergeVertex : EndVertex);
2689  }
2690 }
2691 
2692 template <typename T>
2694 {
2695  for (int i = 0; i < m_edges.size(); ++i)
2696  classifyVertex(i);
2697 }
2698 
2699 template <typename T>
2701 {
2702  bool leftOfPreviousEdge = !qPointIsLeftOfLine(p, v2, v1);
2703  bool leftOfNextEdge = !qPointIsLeftOfLine(p, v3, v2);
2704 
2705  if (qPointIsLeftOfLine(v1, v2, v3))
2706  return leftOfPreviousEdge && leftOfNextEdge;
2707  else
2708  return leftOfPreviousEdge || leftOfNextEdge;
2709 }
2710 
2711 template <typename T>
2713 {
2714  const QPodPoint &center = m_parent->m_vertices.at(m_edges.at(sector).from);
2715  // Handle degenerate edges.
2716  while (m_parent->m_vertices.at(m_edges.at(vertex).from) == center)
2717  vertex = m_edges.at(vertex).next;
2718  int next = m_edges.at(sector).next;
2719  while (m_parent->m_vertices.at(m_edges.at(next).from) == center)
2720  next = m_edges.at(next).next;
2721  int previous = m_edges.at(sector).previous;
2722  while (m_parent->m_vertices.at(m_edges.at(previous).from) == center)
2723  previous = m_edges.at(previous).previous;
2724 
2725  const QPodPoint &p = m_parent->m_vertices.at(m_edges.at(vertex).from);
2726  const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(previous).from);
2727  const QPodPoint &v3 = m_parent->m_vertices.at(m_edges.at(next).from);
2728  if (m_clockwiseOrder)
2729  return pointIsInSector(p, v3, center, v1);
2730  else
2731  return pointIsInSector(p, v1, center, v3);
2732 }
2733 
2734 template <typename T>
2736 {
2737  while (!pointIsInSector(vertex, edge)) {
2738  edge = m_edges.at(m_edges.at(edge).previous).twin;
2739  Q_ASSERT(edge != -1);
2740  }
2741  return edge;
2742 }
2743 
2744 template <typename T>
2746 {
2747  lower = findSector(lower, upper);
2748  upper = findSector(upper, lower);
2749 
2750  int prevLower = m_edges.at(lower).previous;
2751  int prevUpper = m_edges.at(upper).previous;
2752 
2753  Edge e;
2754 
2755  e.twin = m_edges.size() + 1;
2756  e.next = upper;
2757  e.previous = prevLower;
2758  e.from = m_edges.at(lower).from;
2759  e.to = m_edges.at(upper).from;
2760  m_edges.at(upper).previous = m_edges.at(prevLower).next = int(m_edges.size());
2761  m_edges.add(e);
2762 
2763  e.twin = m_edges.size() - 1;
2764  e.next = lower;
2765  e.previous = prevUpper;
2766  e.from = m_edges.at(upper).from;
2767  e.to = m_edges.at(lower).from;
2768  m_edges.at(lower).previous = m_edges.at(prevUpper).next = int(m_edges.size());
2769  m_edges.add(e);
2770 }
2771 
2772 template <typename T>
2774 {
2775  if (m_edges.isEmpty())
2776  return;
2777 
2778  Q_ASSERT(!m_edgeList.root);
2779  QDataBuffer<QPair<int, int> > diagonals(m_upperVertex.size());
2780 
2781  int i = 0;
2782  for (int index = 1; index < m_edges.size(); ++index) {
2783  if (m_parent->m_vertices.at(m_edges.at(index).from) < m_parent->m_vertices.at(m_edges.at(i).from))
2784  i = index;
2785  }
2786  Q_ASSERT(i < m_edges.size());
2787  int j = m_edges.at(i).previous;
2788  Q_ASSERT(j < m_edges.size());
2789  m_clockwiseOrder = qPointIsLeftOfLine(m_parent->m_vertices.at((quint32)m_edges.at(i).from),
2790  m_parent->m_vertices.at((quint32)m_edges.at(j).from), m_parent->m_vertices.at((quint32)m_edges.at(i).to));
2791 
2792  classifyVertices();
2793  fillPriorityQueue();
2794 
2795  // debug: set helpers explicitly (shouldn't be necessary)
2796  //for (int i = 0; i < m_edges.size(); ++i)
2797  // m_edges.at(i).helper = m_edges.at(i).upper();
2798 
2799  while (!m_upperVertex.isEmpty()) {
2800  i = m_upperVertex.last();
2801  Q_ASSERT(i < m_edges.size());
2802  m_upperVertex.pop_back();
2803  j = m_edges.at(i).previous;
2804  Q_ASSERT(j < m_edges.size());
2805 
2806  QRBTree<int>::Node *leftEdgeNode = 0;
2807 
2808  switch (m_edges.at(i).type) {
2809  case RegularVertex:
2810  // If polygon interior is to the right of the vertex...
2811  if (m_edges.at(i).pointingUp == m_clockwiseOrder) {
2812  if (m_edges.at(i).node) {
2813  Q_ASSERT(!m_edges.at(j).node);
2814  if (m_edges.at(m_edges.at(i).helper).type == MergeVertex)
2815  diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
2816  m_edges.at(j).node = m_edges.at(i).node;
2817  m_edges.at(i).node = 0;
2818  m_edges.at(j).node->data = j;
2819  m_edges.at(j).helper = i;
2820  } else if (m_edges.at(j).node) {
2821  Q_ASSERT(!m_edges.at(i).node);
2822  if (m_edges.at(m_edges.at(j).helper).type == MergeVertex)
2823  diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
2824  m_edges.at(i).node = m_edges.at(j).node;
2825  m_edges.at(j).node = 0;
2826  m_edges.at(i).node->data = i;
2827  m_edges.at(i).helper = i;
2828  } else {
2829  qWarning("Inconsistent polygon. (#1)");
2830  }
2831  } else {
2832  leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
2833  if (leftEdgeNode) {
2834  if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
2835  diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
2836  m_edges.at(leftEdgeNode->data).helper = i;
2837  } else {
2838  qWarning("Inconsistent polygon. (#2)");
2839  }
2840  }
2841  break;
2842  case SplitVertex:
2843  leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
2844  if (leftEdgeNode) {
2845  diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
2846  m_edges.at(leftEdgeNode->data).helper = i;
2847  } else {
2848  qWarning("Inconsistent polygon. (#3)");
2849  }
2850  // Fall through.
2851  case StartVertex:
2852  if (m_clockwiseOrder) {
2853  leftEdgeNode = searchEdgeLeftOfEdge(j);
2854  QRBTree<int>::Node *node = m_edgeList.newNode();
2855  node->data = j;
2856  m_edges.at(j).node = node;
2857  m_edges.at(j).helper = i;
2858  m_edgeList.attachAfter(leftEdgeNode, node);
2859  Q_ASSERT(m_edgeList.validate());
2860  } else {
2861  leftEdgeNode = searchEdgeLeftOfEdge(i);
2862  QRBTree<int>::Node *node = m_edgeList.newNode();
2863  node->data = i;
2864  m_edges.at(i).node = node;
2865  m_edges.at(i).helper = i;
2866  m_edgeList.attachAfter(leftEdgeNode, node);
2867  Q_ASSERT(m_edgeList.validate());
2868  }
2869  break;
2870  case MergeVertex:
2871  leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
2872  if (leftEdgeNode) {
2873  if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
2874  diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
2875  m_edges.at(leftEdgeNode->data).helper = i;
2876  } else {
2877  qWarning("Inconsistent polygon. (#4)");
2878  }
2879  // Fall through.
2880  case EndVertex:
2881  if (m_clockwiseOrder) {
2882  if (m_edges.at(m_edges.at(i).helper).type == MergeVertex)
2883  diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
2884  if (m_edges.at(i).node) {
2885  m_edgeList.deleteNode(m_edges.at(i).node);
2886  Q_ASSERT(m_edgeList.validate());
2887  } else {
2888  qWarning("Inconsistent polygon. (#5)");
2889  }
2890  } else {
2891  if (m_edges.at(m_edges.at(j).helper).type == MergeVertex)
2892  diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
2893  if (m_edges.at(j).node) {
2894  m_edgeList.deleteNode(m_edges.at(j).node);
2895  Q_ASSERT(m_edgeList.validate());
2896  } else {
2897  qWarning("Inconsistent polygon. (#6)");
2898  }
2899  }
2900  break;
2901  }
2902  }
2903 
2904  for (int i = 0; i < diagonals.size(); ++i)
2905  createDiagonal(diagonals.at(i).first, diagonals.at(i).second);
2906 }
2907 
2908 template <typename T>
2910 {
2911  if (m_parent->m_edges.at(i).from == m_parent->m_edges.at(j).from)
2912  return m_parent->m_edges.at(i).type > m_parent->m_edges.at(j).type;
2913  return m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from) >
2914  m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from);
2915 }
2916 
2917 //============================================================================//
2918 // QTriangulator::MonotoneToTriangles //
2919 //============================================================================//
2920 template <typename T>
2922 {
2923  QVector<T> result;
2924  QDataBuffer<int> stack(m_parent->m_indices.size());
2925  m_first = 0;
2926  // Require at least three more indices.
2927  while (m_first + 3 <= m_parent->m_indices.size()) {
2928  m_length = 0;
2929  while (m_parent->m_indices.at(m_first + m_length) != T(-1)) { // Q_TRIANGULATE_END_OF_POLYGON
2930  ++m_length;
2931  Q_ASSERT(m_first + m_length < m_parent->m_indices.size());
2932  }
2933  if (m_length < 3) {
2934  m_first += m_length + 1;
2935  continue;
2936  }
2937 
2938  int minimum = 0;
2939  while (less(next(minimum), minimum))
2940  minimum = next(minimum);
2941  while (less(previous(minimum), minimum))
2942  minimum = previous(minimum);
2943 
2944  stack.reset();
2945  stack.add(minimum);
2946  int left = previous(minimum);
2947  int right = next(minimum);
2948  bool stackIsOnLeftSide;
2949  bool clockwiseOrder = leftOfEdge(minimum, left, right);
2950 
2951  if (less(left, right)) {
2952  stack.add(left);
2953  left = previous(left);
2954  stackIsOnLeftSide = true;
2955  } else {
2956  stack.add(right);
2957  right = next(right);
2958  stackIsOnLeftSide = false;
2959  }
2960 
2961  for (int count = 0; count + 2 < m_length; ++count)
2962  {
2963  Q_ASSERT(stack.size() >= 2);
2964  if (less(left, right)) {
2965  if (stackIsOnLeftSide == false) {
2966  for (int i = 0; i + 1 < stack.size(); ++i) {
2967  result.push_back(indices(stack.at(i + 1)));
2968  result.push_back(indices(left));
2969  result.push_back(indices(stack.at(i)));
2970  }
2971  stack.first() = stack.last();
2972  stack.resize(1);
2973  } else {
2974  while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(left, stack.at(stack.size() - 2), stack.last()))) {
2975  result.push_back(indices(stack.at(stack.size() - 2)));
2976  result.push_back(indices(left));
2977  result.push_back(indices(stack.last()));
2978  stack.pop_back();
2979  }
2980  }
2981  stack.add(left);
2982  left = previous(left);
2983  stackIsOnLeftSide = true;
2984  } else {
2985  if (stackIsOnLeftSide == true) {
2986  for (int i = 0; i + 1 < stack.size(); ++i) {
2987  result.push_back(indices(stack.at(i)));
2988  result.push_back(indices(right));
2989  result.push_back(indices(stack.at(i + 1)));
2990  }
2991  stack.first() = stack.last();
2992  stack.resize(1);
2993  } else {
2994  while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(right, stack.last(), stack.at(stack.size() - 2)))) {
2995  result.push_back(indices(stack.last()));
2996  result.push_back(indices(right));
2997  result.push_back(indices(stack.at(stack.size() - 2)));
2998  stack.pop_back();
2999  }
3000  }
3001  stack.add(right);
3002  right = next(right);
3003  stackIsOnLeftSide = false;
3004  }
3005  }
3006 
3007  m_first += m_length + 1;
3008  }
3009  m_parent->m_indices = result;
3010 }
3011 
3012 //============================================================================//
3013 // qTriangulate //
3014 //============================================================================//
3015 
3017  int count, uint hint, const QTransform &matrix)
3018 {
3019  QTriangleSet triangleSet;
3021  QTriangulator<quint32> triangulator;
3022  triangulator.initialize(polygon, count, hint, matrix);
3023  QVertexSet<quint32> vertexSet = triangulator.triangulate();
3024  triangleSet.vertices = vertexSet.vertices;
3025  triangleSet.indices.setDataUint(vertexSet.indices);
3026 
3027  } else {
3028  QTriangulator<quint16> triangulator;
3029  triangulator.initialize(polygon, count, hint, matrix);
3030  QVertexSet<quint16> vertexSet = triangulator.triangulate();
3031  triangleSet.vertices = vertexSet.vertices;
3032  triangleSet.indices.setDataUshort(vertexSet.indices);
3033  }
3034  return triangleSet;
3035 }
3036 
3038  const QTransform &matrix, qreal lod)
3039 {
3040  QTriangleSet triangleSet;
3042  QTriangulator<quint32> triangulator;
3043  triangulator.initialize(path, matrix, lod);
3044  QVertexSet<quint32> vertexSet = triangulator.triangulate();
3045  triangleSet.vertices = vertexSet.vertices;
3046  triangleSet.indices.setDataUint(vertexSet.indices);
3047  } else {
3048  QTriangulator<quint16> triangulator;
3049  triangulator.initialize(path, matrix, lod);
3050  QVertexSet<quint16> vertexSet = triangulator.triangulate();
3051  triangleSet.vertices = vertexSet.vertices;
3052  triangleSet.indices.setDataUshort(vertexSet.indices);
3053  }
3054  return triangleSet;
3055 }
3056 
3058  const QTransform &matrix, qreal lod)
3059 {
3060  QTriangleSet triangleSet;
3062  QTriangulator<quint32> triangulator;
3063  triangulator.initialize(path, matrix, lod);
3064  QVertexSet<quint32> vertexSet = triangulator.triangulate();
3065  triangleSet.vertices = vertexSet.vertices;
3066  triangleSet.indices.setDataUint(vertexSet.indices);
3067  } else {
3068  QTriangulator<quint16> triangulator;
3069  triangulator.initialize(path, matrix, lod);
3070  QVertexSet<quint16> vertexSet = triangulator.triangulate();
3071  triangleSet.vertices = vertexSet.vertices;
3072  triangleSet.indices.setDataUshort(vertexSet.indices);
3073  }
3074  return triangleSet;
3075 }
3076 
3078  const QTransform &matrix, qreal lod)
3079 {
3080  QPolylineSet polyLineSet;
3082  QTriangulator<quint32> triangulator;
3083  triangulator.initialize(path, matrix, lod);
3084  QVertexSet<quint32> vertexSet = triangulator.polyline();
3085  polyLineSet.vertices = vertexSet.vertices;
3086  polyLineSet.indices.setDataUint(vertexSet.indices);
3087  } else {
3088  QTriangulator<quint16> triangulator;
3089  triangulator.initialize(path, matrix, lod);
3090  QVertexSet<quint16> vertexSet = triangulator.triangulate();
3091  polyLineSet.vertices = vertexSet.vertices;
3092  polyLineSet.indices.setDataUshort(vertexSet.indices);
3093  }
3094  return polyLineSet;
3095 }
3096 
3098  const QTransform &matrix, qreal lod)
3099 {
3100  QPolylineSet polyLineSet;
3102  QTriangulator<quint32> triangulator;
3103  triangulator.initialize(path, matrix, lod);
3104  QVertexSet<quint32> vertexSet = triangulator.polyline();
3105  polyLineSet.vertices = vertexSet.vertices;
3106  polyLineSet.indices.setDataUint(vertexSet.indices);
3107  } else {
3108  QTriangulator<quint16> triangulator;
3109  triangulator.initialize(path, matrix, lod);
3110  QVertexSet<quint16> vertexSet = triangulator.triangulate();
3111  polyLineSet.vertices = vertexSet.vertices;
3112  polyLineSet.indices.setDataUshort(vertexSet.indices);
3113  }
3114  return polyLineSet;
3115 }
3116 
The QPainter class performs low-level painting on widgets and other paint devices.
Definition: qpainter.h:86
double d
Definition: qnumeric_p.h:62
bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const
ElementType
This enum describes the types of elements used to connect vertices in subpaths.
Definition: qpainterpath.h:70
void attachLeft(Node *parent, Node *child)
static const uchar prime_deltas[]
timeval operator-(const timeval &t1, const timeval &t2)
Definition: qcore_unix_p.h:133
int type
Definition: qmetatype.cpp:239
bool leftOfEdge(int i, int j, int k) const
double qreal
Definition: qglobal.h:1193
static qint64 qCross(const QPodPoint &u, const QPodPoint &v)
unsigned char c[8]
Definition: qnumeric_p.h:62
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
Definition: qglobal.h:1215
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
int qint32
Definition: qglobal.h:937
void clear()
EventRef event
Node * previous(Node *node) const
static const quint64 UNUSED
QVertexSet< T > triangulate()
int elementCount() const
QVertexIndexVector indices
Node * newNode()
void setDataUint(const QVector< quint32 > &data)
static int parent(int i)
bool operator>(const QByteArray &a1, const QByteArray &a2)
Definition: qbytearray.h:551
The QDialog class is the base class of dialog windows.
Definition: qdialog.h:56
The QPainterPath class provides a container for painting operations, enabling graphical shapes to be ...
Definition: qpainterpath.h:67
The QWheelEvent class contains parameters that describe a wheel event.
Definition: qevent.h:139
QRBTree< int >::Node * searchEdgeLeftOfEdge(int edgeIndex) const
QRBTree< int >::Node * QRBTreeIntNodePointer
void resize(int size)
int findSector(int edge, int vertex)
void setY(qreal y)
Sets the y coordinate of this point to the given y coordinate.
Definition: qpoint.h:297
QRBTree< int >::Node * searchEdgeLeftOf(int edgeIndex) const
The QPointF class defines a point in the plane using floating point precision.
Definition: qpoint.h:214
Node * next(Node *node) const
QVector< qreal > vertices
const T & top() const
bool contains(quint64 key) const
T1 first
Definition: qpair.h:65
#define Q_FIXED_POINT_SCALE
T2 second
Definition: qpair.h:66
static void clear(QVariant::Private *d)
Definition: qvariant.cpp:197
static int right(int i)
Node * root
QVertexIndexVector indices
QVector< T > m_indices
bool isEmpty() const
Definition: qdatabuffer_p.h:81
quint64 denominator
quint16 u
long ASN1_INTEGER_get ASN1_INTEGER * a
bool operator!=(QBool b1, bool b2)
Definition: qglobal.h:2026
const QVectorPath & qtVectorPathForPath(const QPainterPath &path)
void drawLine(const QLineF &line)
Draws a line defined by line.
Definition: qpainter.h:573
static quint64 gcd(quint64 x, quint64 y)
bool isEmpty() const
void insert(quint64 key)
void setDataUshort(const QVector< quint16 > &data)
QInt64Set(int capacity=64)
void attachRight(Node *parent, Node *child)
Q_DECL_CONSTEXPR T qAbs(const T &t)
Definition: qglobal.h:1201
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
static qint64 qPointDistanceFromLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
bool empty() const
This function is provided for STL compatibility.
Definition: qvector.h:285
void splitEdgeListRange(QRBTree< int >::Node *leftmost, QRBTree< int >::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint)
bool operator<(int priority, const QPair< QRunnable *, int > &p)
Definition: qthreadpool.cpp:50
void append(const T &t)
const QPainterPath::ElementType * elements() const
QRBTree< int >::Node * searchEdgeLeftOfPoint(int pointIndex) const
QVertexSet< T > polyline()
QPair< QRBTree< int >::Node *, QRBTree< int >::Node * > bounds(const QPodPoint &point) const
Q_CORE_EXPORT QTextStream & right(QTextStream &s)
bool isOnLine(const QPodPoint &u, const QPodPoint &v) const
static int primeForCount(int count)
static QIntersectionPoint qIntersectionPoint(const QPodPoint &point)
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
bool operator<=(const QByteArray &a1, const QByteArray &a2)
Definition: qbytearray.h:545
const QPoint & pos() const
Returns the position of the mouse cursor, relative to the widget that received the event...
Definition: qevent.h:95
GlobalColor
Definition: qnamespace.h:104
qreal x() const
Returns the x-coordinate of this point.
Definition: qpoint.h:282
void resize(int size)
Sets the size of the vector to size.
Definition: qvector.h:342
const T & head() const
void pop_back()
This function is provided for STL compatibility.
Definition: qvector.h:283
MonotoneToTriangles(QTriangulator< T > *parent)
QTextStream & center(QTextStream &stream)
Calls QTextStream::setFieldAlignment(QTextStream::AlignCenter) on stream and returns stream...
static QBezier fromPoints(const QPointF &p1, const QPointF &p2, const QPointF &p3, const QPointF &p4)
Definition: qbezier.cpp:71
unsigned char uchar
Definition: qglobal.h:994
bool isEmpty() const
void setRenderHint(RenderHint hint, bool on=true)
Sets the given render hint on the painter if on is true; otherwise clears the render hint...
Definition: qpainter.cpp:7620
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
The QRectF class defines a rectangle in the plane using floating point precision. ...
Definition: qrect.h:511
void push(const T &x)
SimpleToMonotone(QTriangulator< T > *parent)
bool isAccurate() const
static bool lessThan(const QChar *a, int l, const char *c)
Definition: qurl.cpp:3253
int size() const
unsigned __int64 quint64
Definition: qglobal.h:943
QVector< qreal > vertices
static void sort(T *array, int count, LessThan lessThan)
void update(Node *node)
QVarLengthArray< int, 6 > ShortArray
void insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i)
#define QT_PREPEND_NAMESPACE(name)
This macro qualifies identifier with the full namespace.
Definition: qglobal.h:87
The QPolygonF class provides a vector of points using floating point precision.
Definition: qpolygon.h:134
void reorderEdgeListRange(QRBTree< int >::Node *leftmost, QRBTree< int >::Node *rightmost)
Q_CORE_EXPORT void qWarning(const char *,...)
static int comparePoints(const QPodPoint &u, const QPodPoint &v)
QPoint map(const QPoint &p) const
Creates and returns a QPoint object that is a copy of the given point, mapped into the coordinate sys...
int blackDepth(Node *top) const
int delta() const
Returns the distance that the wheel is rotated, in eighths of a degree.
Definition: qevent.h:150
Type & at(int i)
Definition: qdatabuffer_p.h:86
unsigned int uint
Definition: qglobal.h:996
bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const
ComplexToSimple(QTriangulator< T > *parent)
static void split(QT_FT_Vector *b)
void attachAfter(Node *parent, Node *child)
bool isEmpty() const
__int64 qint64
Definition: qglobal.h:942
static int cmp(const ushort *s1, const ushort *s2, size_t len)
QVertexSet(const QVertexSet< T > &other)
const T & at(int idx) const
bool operator==(const QIntersectionPoint &other) const
void sortEdgeList(const QPodPoint eventPoint)
static int compare(quint64 a, quint64 b)
Qt::MouseButton button() const
Returns the button that caused the event.
Definition: qevent.h:101
uint hints() const
void qSwap(T &value1, T &value2)
Definition: qglobal.h:2181
void setWindow(const QRect &window)
Sets the painter&#39;s window to the given rectangle, and enables view transformations.
Definition: qpainter.cpp:7745
const T & at(int i) const
Returns the item at index position i in the vector.
Definition: qvector.h:350
The QMouseEvent class contains parameters that describe a mouse event.
Definition: qevent.h:85
Q_CORE_EXPORT QTextStream & center(QTextStream &s)
bool operator<(const QFraction &other) const
The QBitArray class provides an array of bits.
Definition: qbitarray.h:54
void swapNodes(Node *n1, Node *n2)
static bool qPointIsLeftOfLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
QVector< qreal > vertices
void deleteNode(Node *&node)
#define Q_ASSERT_X(cond, where, what)
Definition: qglobal.h:1837
void rotateLeft(Node *node)
QPolygonF toPolygon(qreal bezier_flattening_threshold=0.5) const
Definition: qbezier.cpp:89
static qint64 qDot(const QPodPoint &u, const QPodPoint &v)
Qt::MouseButtons buttons() const
Returns the button state when the event was generated.
Definition: qevent.h:102
bool validate() const
Type & last()
Definition: qdatabuffer_p.h:88
bool operator<(const QIntersectionPoint &other) const
static int qCompareFractions(quint64 a, quint64 b, quint64 c, quint64 d)
static int primeForNumBits(int numBits)
bool checkRedBlackProperty(Node *top) const
bool operator>=(const QByteArray &a1, const QByteArray &a2)
Definition: qbytearray.h:557
int key
The QPoint class defines a point in the plane using integer precision.
Definition: qpoint.h:53
void detach(Node *node)
bool empty() const
reference back()
This function is provided for STL compatibility.
Definition: qvector.h:289
unsigned int quint32
Definition: qglobal.h:938
const qreal * points() const
void rotateRight(Node *node)
bool operator==(const QFraction &other) const
void setPen(const QColor &color)
Sets the painter&#39;s pen to have style Qt::SolidLine, width 0 and the specified color.
Definition: qpainter.cpp:4047
void enqueue(const T &x)
void initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix)
QFactoryLoader * l
void push_back(const T &t)
This function is provided for STL compatibility.
Definition: qvector.h:281
static Extensions glExtensions()
Definition: qgl.cpp:5781
void setX(qreal x)
Sets the x coordinate of this point to the given x coordinate.
Definition: qpoint.h:292
QTriangleSet qTriangulate(const qreal *polygon, int count, uint hint, const QTransform &matrix)
bool reallocate(int capacity)
qreal y() const
Returns the y-coordinate of this point.
Definition: qpoint.h:287
quint16 index
quint64 numerator
QVertexSet< T > & operator=(const QVertexSet< T > &other)
bool isValid() const
bool rehash(int capacity)
bool isValid() const
bool calculateIntersection(int left, int right)
QMaxHeap< Intersection > m_topIntersection
QDataBuffer< QPodPoint > m_vertices
int x() const
Returns the x coordinate of this point.
Definition: qpoint.h:128
QPodPoint round() const
const T & dequeue()
void setOpacity(qreal opacity)
Sets the opacity of the painter to opacity.
Definition: qpainter.cpp:2139
int order(Node *left, Node *right)
QPair< QRBTree< int >::Node *, QRBTree< int >::Node * > outerBounds(const QPodPoint &point) const
#define Q_UINT64_C(c)
Definition: qglobal.h:941
bool isValid() const
timeval & operator+=(timeval &t1, const timeval &t2)
Definition: qcore_unix_p.h:120
bool pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3)
The QPaintEvent class contains event parameters for paint events.
Definition: qevent.h:298
quint64 * m_array
QDataBuffer< T > m_data
bool(* LessThan)(const QPair< QListWidgetItem *, int > &, const QPair< QListWidgetItem *, int > &)
Definition: qlistwidget.cpp:53
static QFraction qFraction(quint64 n, quint64 d)
bool operator<(const Event &other) const
Q_CORE_EXPORT QTextStream & left(QTextStream &s)
void createDiagonal(int lower, int upper)
bool operator==(QBool b1, bool b2)
Definition: qglobal.h:2023
Node * front(Node *node) const
int size() const
Returns the number of items in the vector.
Definition: qvector.h:137
Node * freeList
void attachBefore(Node *parent, Node *child)
#define INT_MAX
static int left(int i)
QVector< T > indices
Q_DECL_CONSTEXPR int qRound(qreal d)
Definition: qglobal.h:1203
void fillRect(const QRectF &, const QBrush &)
Fills the given rectangle with the brush specified.
Definition: qpainter.cpp:7420
void reset()
Definition: qdatabuffer_p.h:79
Node * back(Node *node) const
QPolylineSet qPolyline(const QVectorPath &path, const QTransform &matrix, qreal lod)
int size() const
The QTransform class specifies 2D transformations of a coordinate system.
Definition: qtransform.h:65
void rebalance(Node *node)
int size() const
Definition: qdatabuffer_p.h:83
timeval operator+(const timeval &t1, const timeval &t2)
Definition: qcore_unix_p.h:126