FCL/sf/mw/qt: comparison src/opengl/gl2paintengineex/qtriangulator.cpp

equal deleted inserted replaced

-:b72c6db6890b
+:5dc02b23752f
+/****************************************************************************
+**
+** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtOpenGL module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights.  These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+#include "qtriangulator_p.h"
+#include <QtGui/qdialog.h>
+#include <QtGui/qevent.h>
+#include <QtGui/qpainter.h>
+#include <QtGui/qpainterpath.h>
+#include <QtGui/private/qbezier_p.h>
+#include <QtGui/private/qdatabuffer_p.h>
+#include <QtCore/qbitarray.h>
+#include <QtCore/qvarlengtharray.h>
+#include <QtCore/qqueue.h>
+#include <QtCore/qglobal.h>
+#include <QtCore/qpoint.h>
+#include <QtCore/qalgorithms.h>
+#include <QtDebug>
+#include <math.h>
+QT_BEGIN_NAMESPACE
+//#define Q_TRIANGULATOR_DEBUG
+#define Q_FIXED_POINT_SCALE 32
+// Quick sort.
+template <class T, class LessThan>
+static void sort(T *array, int count, LessThan lessThan)
+{
+// If the number of elements fall below some threshold, use insertion sort.
+const int INSERTION_SORT_LIMIT = 7; // About 7 is fastest on my computer...
+if (count <= INSERTION_SORT_LIMIT) {
+for (int i = 1; i < count; ++i) {
+T temp = array[i];
+int j = i;
+while (j > 0 && lessThan(temp, array[j - 1])) {
+array[j] = array[j - 1];
+--j;
+}
+array[j] = temp;
+}
+return;
+}
+int high = count - 1;
+int low = 0;
+int mid = high / 2;
+if (lessThan(array[mid], array[low]))
+qSwap(array[mid], array[low]);
+if (lessThan(array[high], array[mid]))
+qSwap(array[high], array[mid]);
+if (lessThan(array[mid], array[low]))
+qSwap(array[mid], array[low]);
+--high;
+++low;
+qSwap(array[mid], array[high]);
+int pivot = high;
+--high;
+while (low <= high) {
+while (!lessThan(array[pivot], array[low])) {
+++low;
+if (low > high)
+goto sort_loop_end;
+}
+while (!lessThan(array[high], array[pivot])) {
+--high;
+if (low > high)
+goto sort_loop_end;
+}
+qSwap(array[low], array[high]);
+++low;
+--high;
+}
+sort_loop_end:
+if (low != pivot)
+qSwap(array[pivot], array[low]);
+sort(array, low, lessThan);
+sort(array + low + 1, count - low - 1, lessThan);
+}
+// Quick sort.
+template <class T>
+static void sort(T *array, int count)
+{
+// If the number of elements fall below some threshold, use insertion sort.
+const int INSERTION_SORT_LIMIT = 25; // About 25 is fastest on my computer...
+if (count <= INSERTION_SORT_LIMIT) {
+for (int i = 1; i < count; ++i) {
+T temp = array[i];
+int j = i;
+while (j > 0 && (temp < array[j - 1])) {
+array[j] = array[j - 1];
+--j;
+}
+array[j] = temp;
+}
+return;
+}
+int high = count - 1;
+int low = 0;
+int mid = high / 2;
+if ((array[mid] < array[low]))
+qSwap(array[mid], array[low]);
+if ((array[high] < array[mid]))
+qSwap(array[high], array[mid]);
+if ((array[mid] < array[low]))
+qSwap(array[mid], array[low]);
+--high;
+++low;
+qSwap(array[mid], array[high]);
+int pivot = high;
+--high;
+while (low <= high) {
+while (!(array[pivot] < array[low])) {
+++low;
+if (low > high)
+goto sort_loop_end;
+}
+while (!(array[high] < array[pivot])) {
+--high;
+if (low > high)
+goto sort_loop_end;
+}
+qSwap(array[low], array[high]);
+++low;
+--high;
+}
+sort_loop_end:
+if (low != pivot)
+qSwap(array[pivot], array[low]);
+sort(array, low);
+sort(array + low + 1, count - low - 1);
+}
+//============================================================================//
+//                                 QFraction                                  //
+//============================================================================//
+// Fraction must be in the range [0, 1)
+struct QFraction
+{
+// Comparison operators must not be called on invalid fractions.
+inline bool operator < (const QFraction &other) const;
+inline bool operator == (const QFraction &other) const;
+inline bool operator != (const QFraction &other) const {return !(*this == other);}
+inline bool operator > (const QFraction &other) const {return other < *this;}
+inline bool operator >= (const QFraction &other) const {return !(*this < other);}
+inline bool operator <= (const QFraction &other) const {return !(*this > other);}
+inline bool isValid() const {return denominator != 0;}
+// numerator and denominator must not have common denominators.
+quint64 numerator, denominator;
+};
+static inline quint64 gcd(quint64 x, quint64 y)
+{
+while (y != 0) {
+quint64 z = y;
+y = x % y;
+x = z;
+}
+return x;
+}
+static inline int compare(quint64 a, quint64 b)
+{
+return (a > b) - (a < b);
+}
+// Compare a/b with c/d.
+// Return negative if less, 0 if equal, positive if greater.
+// a < b, c < d
+static int qCompareFractions(quint64 a, quint64 b, quint64 c, quint64 d)
+{
+const quint64 LIMIT = Q_UINT64_C(0x100000000);
+for (;;) {
+// If the products 'ad' and 'bc' fit into 64 bits, they can be directly compared.
+if (b < LIMIT && d < LIMIT)
+return compare(a * d, b * c);
+if (a == 0 || c == 0)
+return compare(a, c);
+// a/b < c/d  <=>  d/c < b/a
+quint64 b_div_a = b / a;
+quint64 d_div_c = d / c;
+if (b_div_a != d_div_c)
+return compare(d_div_c, b_div_a);
+// floor(d/c) == floor(b/a)
+// frac(d/c) < frac(b/a) ?
+// frac(x/y) = (x%y)/y
+d -= d_div_c * c; //d %= c;
+b -= b_div_a * a; //b %= a;
+qSwap(a, d);
+qSwap(b, c);
+}
+}
+// Fraction must be in the range [0, 1)
+// Assume input is valid.
+static QFraction qFraction(quint64 n, quint64 d) {
+QFraction result;
+if (n == 0) {
+result.numerator = 0;
+result.denominator = 1;
+} else {
+quint64 g = gcd(n, d);
+result.numerator = n / g;
+result.denominator = d / g;
+}
+return result;
+}
+inline bool QFraction::operator < (const QFraction &other) const
+{
+return qCompareFractions(numerator, denominator, other.numerator, other.denominator) < 0;
+}
+inline bool QFraction::operator == (const QFraction &other) const
+{
+return numerator == other.numerator && denominator == other.denominator;
+}
+//============================================================================//
+//                                 QPodPoint                                  //
+//============================================================================//
+struct QPodPoint
+{
+inline bool operator < (const QPodPoint &other) const
+{
+if (y != other.y)
+return y < other.y;
+return x < other.x;
+}
+inline bool operator > (const QPodPoint &other) const {return other < *this;}
+inline bool operator <= (const QPodPoint &other) const {return !(*this > other);}
+inline bool operator >= (const QPodPoint &other) const {return !(*this < other);}
+inline bool operator == (const QPodPoint &other) const {return x == other.x && y == other.y;}
+inline bool operator != (const QPodPoint &other) const {return x != other.x || y != other.y;}
+inline QPodPoint &operator += (const QPodPoint &other) {x += other.x; y += other.y; return *this;}
+inline QPodPoint &operator -= (const QPodPoint &other) {x -= other.x; y -= other.y; return *this;}
+inline QPodPoint operator + (const QPodPoint &other) const {QPodPoint result = {x + other.x, y + other.y}; return result;}
+inline QPodPoint operator - (const QPodPoint &other) const {QPodPoint result = {x - other.x, y - other.y}; return result;}
+int x;
+int y;
+};
+static inline qint64 qCross(const QPodPoint &u, const QPodPoint &v)
+{
+return qint64(u.x) * qint64(v.y) - qint64(u.y) * qint64(v.x);
+}
+static inline qint64 qDot(const QPodPoint &u, const QPodPoint &v)
+{
+return qint64(u.x) * qint64(v.x) + qint64(u.y) * qint64(v.y);
+}
+// Return positive value if 'p' is to the right of the line 'v1'->'v2', negative if left of the
+// line and zero if exactly on the line.
+// The returned value is the z-component of the qCross product between 'v2-v1' and 'p-v1',
+// which is twice the signed area of the triangle 'p'->'v1'->'v2' (positive for CW order).
+static inline qint64 qPointDistanceFromLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
+{
+return qCross(v2 - v1, p - v1);
+}
+static inline bool qPointIsLeftOfLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
+{
+return qPointDistanceFromLine(p, v1, v2) < 0;
+}
+// Return:
+// -1 if u < v
+//  0 if u == v
+//  1 if u > v
+static int comparePoints(const QPodPoint &u, const QPodPoint &v)
+{
+if (u.y < v.y)
+return -1;
+if (u.y > v.y)
+return 1;
+if (u.x < v.x)
+return -1;
+if (u.x > v.x)
+return 1;
+return 0;
+}
+//============================================================================//
+//                             QIntersectionPoint                             //
+//============================================================================//
+struct QIntersectionPoint
+{
+inline bool isValid() const {return xOffset.isValid() && yOffset.isValid();}
+QPodPoint round() const;
+inline bool isAccurate() const {return xOffset.numerator == 0 && yOffset.numerator == 0;}
+bool operator < (const QIntersectionPoint &other) const;
+bool operator == (const QIntersectionPoint &other) const;
+inline bool operator != (const QIntersectionPoint &other) const {return !(*this == other);}
+inline bool operator > (const QIntersectionPoint &other) const {return other < *this;}
+inline bool operator >= (const QIntersectionPoint &other) const {return !(*this < other);}
+inline bool operator <= (const QIntersectionPoint &other) const {return !(*this > other);}
+bool isOnLine(const QPodPoint &u, const QPodPoint &v) const;
+QPodPoint upperLeft;
+QFraction xOffset;
+QFraction yOffset;
+};
+static inline QIntersectionPoint qIntersectionPoint(const QPodPoint &point)
+{
+// upperLeft = point, xOffset = 0/1, yOffset = 0/1.
+QIntersectionPoint p = {{point.x, point.y}, {0, 1}, {0, 1}};
+return p;
+}
+static inline QIntersectionPoint qIntersectionPoint(int x, int y)
+{
+// upperLeft = (x, y), xOffset = 0/1, yOffset = 0/1.
+QIntersectionPoint p = {{x, y}, {0, 1}, {0, 1}};
+return p;
+}
+static QIntersectionPoint qIntersectionPoint(const QPodPoint &u1, const QPodPoint &u2, const QPodPoint &v1, const QPodPoint &v2)
+{
+QIntersectionPoint result = {{0, 0}, {0, 0}, {0, 0}};
+QPodPoint u = u2 - u1;
+QPodPoint v = v2 - v1;
+qint64 d1 = qCross(u, v1 - u1);
+qint64 d2 = qCross(u, v2 - u1);
+qint64 det = d2 - d1;
+qint64 d3 = qCross(v, u1 - v1);
+qint64 d4 = d3 - det; //qCross(v, u2 - v1);
+// Check that the math is correct.
+Q_ASSERT(d4 == qCross(v, u2 - v1));
+// The intersection point can be expressed as:
+// v1 - v * d1/det
+// v2 - v * d2/det
+// u1 + u * d3/det
+// u2 + u * d4/det
+// I'm only interested in lines that are crossing, so ignore parallel lines even if they overlap.
+if (det == 0)
+return result;
+if (det < 0) {
+det = -det;
+d1 = -d1;
+d2 = -d2;
+d3 = -d3;
+d4 = -d4;
+}
+// I'm only interested in lines intersecting at their interior, not at their end points.
+// The lines intersect at their interior if and only if 'd1 < 0', 'd2 > 0', 'd3 < 0' and 'd4 > 0'.
+if (d1 >= 0 || d2 <= 0 || d3 <= 0 || d4 >= 0)
+return result;
+// Calculate the intersection point as follows:
+// v1 - v * d1/det | v1 <= v2 (component-wise)
+// v2 - v * d2/det | v2 < v1 (component-wise)
+// Assuming 21 bits per vector component.
+// TODO: Make code path for 31 bits per vector component.
+if (v.x >= 0) {
+result.upperLeft.x = v1.x + (-v.x * d1) / det;
+result.xOffset = qFraction(quint64(-v.x * d1) % quint64(det), quint64(det));
+} else {
+result.upperLeft.x = v2.x + (-v.x * d2) / det;
+result.xOffset = qFraction(quint64(-v.x * d2) % quint64(det), quint64(det));
+}
+if (v.y >= 0) {
+result.upperLeft.y = v1.y + (-v.y * d1) / det;
+result.yOffset = qFraction(quint64(-v.y * d1) % quint64(det), quint64(det));
+} else {
+result.upperLeft.y = v2.y + (-v.y * d2) / det;
+result.yOffset = qFraction(quint64(-v.y * d2) % quint64(det), quint64(det));
+}
+Q_ASSERT(result.xOffset.isValid());
+Q_ASSERT(result.yOffset.isValid());
+return result;
+}
+QPodPoint QIntersectionPoint::round() const
+{
+QPodPoint result = upperLeft;
+if (2 * xOffset.numerator >= xOffset.denominator)
+++result.x;
+if (2 * yOffset.numerator >= yOffset.denominator)
+++result.y;
+return result;
+}
+bool QIntersectionPoint::operator < (const QIntersectionPoint &other) const
+{
+if (upperLeft.y != other.upperLeft.y)
+return upperLeft.y < other.upperLeft.y;
+if (yOffset != other.yOffset)
+return yOffset < other.yOffset;
+if (upperLeft.x != other.upperLeft.x)
+return upperLeft.x < other.upperLeft.x;
+return xOffset < other.xOffset;
+}
+bool QIntersectionPoint::operator == (const QIntersectionPoint &other) const
+{
+return upperLeft == other.upperLeft && xOffset == other.xOffset && yOffset == other.yOffset;
+}
+// Returns true if this point is on the infinite line passing through 'u' and 'v'.
+bool QIntersectionPoint::isOnLine(const QPodPoint &u, const QPodPoint &v) const
+{
+// TODO: Make code path for coordinates with more than 21 bits.
+const QPodPoint p = upperLeft - u;
+const QPodPoint q = v - u;
+bool isHorizontal = p.y == 0 && yOffset.numerator == 0;
+bool isVertical = p.x == 0 && xOffset.numerator == 0;
+if (isHorizontal && isVertical)
+return true;
+if (isHorizontal)
+return q.y == 0;
+if (q.y == 0)
+return false;
+if (isVertical)
+return q.x == 0;
+if (q.x == 0)
+return false;
+// At this point, 'p+offset' and 'q' cannot lie on the x or y axis.
+if (((q.x < 0) == (q.y < 0)) != ((p.x < 0) == (p.y < 0)))
+return false; // 'p + offset' and 'q' pass through different quadrants.
+// Move all coordinates into the first quadrant.
+quint64 nx, ny;
+if (p.x < 0)
+nx = quint64(-p.x) * xOffset.denominator - xOffset.numerator;
+else
+nx = quint64(p.x) * xOffset.denominator + xOffset.numerator;
+if (p.y < 0)
+ny = quint64(-p.y) * yOffset.denominator - yOffset.numerator;
+else
+ny = quint64(p.y) * yOffset.denominator + yOffset.numerator;
+return qFraction(quint64(qAbs(q.x)) * xOffset.denominator, quint64(qAbs(q.y)) * yOffset.denominator) == qFraction(nx, ny);
+}
+//============================================================================//
+//                                  QMaxHeap                                  //
+//============================================================================//
+template <class T>
+class QMaxHeap
+{
+public:
+QMaxHeap() : m_data(0) {}
+inline int size() const {return m_data.size();}
+inline bool empty() const {return m_data.isEmpty();}
+inline bool isEmpty() const {return m_data.isEmpty();}
+void push(const T &x);
+T pop();
+inline const T &top() const {return m_data.first();}
+private:
+static inline int parent(int i) {return (i - 1) / 2;}
+static inline int left(int i) {return 2 * i + 1;}
+static inline int right(int i) {return 2 * i + 2;}
+QDataBuffer<T> m_data;
+};
+template <class T>
+void QMaxHeap<T>::push(const T &x)
+{
+int current = m_data.size();
+int parent = QMaxHeap::parent(current);
+m_data.add(x);
+while (current != 0 && m_data.at(parent) < x) {
+m_data.at(current) = m_data.at(parent);
+current = parent;
+parent = QMaxHeap::parent(current);
+}
+m_data.at(current) = x;
+}
+template <class T>
+T QMaxHeap<T>::pop()
+{
+T result = m_data.first();
+T back = m_data.last();
+m_data.pop_back();
+if (!m_data.isEmpty()) {
+int current = 0;
+for (;;) {
+int left = QMaxHeap::left(current);
+int right = QMaxHeap::right(current);
+if (left >= m_data.size())
+break;
+int greater = left;
+if (right < m_data.size() && m_data.at(left) < m_data.at(right))
+greater = right;
+if (m_data.at(greater) < back)
+break;
+m_data.at(current) = m_data.at(greater);
+current = greater;
+}
+m_data.at(current) = back;
+}
+return result;
+}
+//============================================================================//
+//                                  QRBTree                                   //
+//============================================================================//
+template <class T>
+struct QRBTree
+{
+struct Node
+{
+inline Node() : parent(0), left(0), right(0), red(true) { }
+inline ~Node() {if (left) delete left; if (right) delete right;}
+T data;
+Node *parent;
+Node *left;
+Node *right;
+bool red;
+};
+inline QRBTree() : root(0), freeList(0) { }
+inline ~QRBTree();
+inline void clear();
+void attachBefore(Node *parent, Node *child);
+void attachAfter(Node *parent, Node *child);
+inline Node *front(Node *node) const;
+inline Node *back(Node *node) const;
+Node *next(Node *node) const;
+Node *previous(Node *node) const;
+inline void deleteNode(Node *&node);
+inline Node *newNode();
+// Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise.
+// 'left' and 'right' cannot be null.
+int order(Node *left, Node *right);
+inline bool verify() const;
+private:
+void rotateLeft(Node *node);
+void rotateRight(Node *node);
+void update(Node *node);
+inline void attachLeft(Node *parent, Node *child);
+inline void attachRight(Node *parent, Node *child);
+int blackDepth(Node *top) const;
+bool checkRedBlackProperty(Node *top) const;
+void swapNodes(Node *n1, Node *n2);
+void detach(Node *node);
+// 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree.
+void rebalance(Node *node);
+public:
+Node *root;
+private:
+Node *freeList;
+};
+template <class T>
+inline QRBTree<T>::~QRBTree()
+{
+clear();
+while (freeList) {
+// Avoid recursively calling the destructor, as this list may become large.
+Node *next = freeList->right;
+freeList->right = 0;
+delete freeList;
+freeList = next;
+}
+}
+template <class T>
+inline void QRBTree<T>::clear()
+{
+if (root)
+delete root;
+root = 0;
+}
+template <class T>
+void QRBTree<T>::rotateLeft(Node *node)
+{
+//   |            |      //
+//   N            B      //
+//  / \          / \     //
+// A   B  --->  N   D    //
+//    / \      / \       //
+//   C   D    A   C      //
+Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
+ref = node->right;
+node->right->parent = node->parent;
+//   :        //
+//   N        //
+//  / :|      //
+// A   B      //
+//    / \     //
+//   C   D    //
+node->right = ref->left;
+if (ref->left)
+ref->left->parent = node;
+//   :   |     //
+//   N   B     //
+//  / \ : \    //
+// A   C   D   //
+ref->left = node;
+node->parent = ref;
+//     |       //
+//     B       //
+//    / \      //
+//   N   D     //
+//  / \        //
+// A   C       //
+}
+template <class T>
+void QRBTree<T>::rotateRight(Node *node)
+{
+//     |            |        //
+//     N            A        //
+//    / \          / \       //
+//   A   B  --->  C   N      //
+//  / \              / \     //
+// C   D            D   B    //
+Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
+ref = node->left;
+node->left->parent = node->parent;
+node->left = ref->right;
+if (ref->right)
+ref->right->parent = node;
+ref->right = node;
+node->parent = ref;
+}
+template <class T>
+void QRBTree<T>::update(Node *node) // call this after inserting a node
+{
+for (;;) {
+Node *parent = node->parent;
+// if the node is the root, color it black
+if (!parent) {
+node->red = false;
+return;
+}
+// if the parent is black, the node can be left red
+if (!parent->red)
+return;
+// at this point, the parent is red and cannot be the root
+Node *grandpa = parent->parent;
+Q_ASSERT(grandpa);
+Node *uncle = (parent == grandpa->left ? grandpa->right : grandpa->left);
+if (uncle && uncle->red) {
+// grandpa's black, parent and uncle are red.
+// let parent and uncle be black, grandpa red and recursively update grandpa.
+Q_ASSERT(!grandpa->red);
+parent->red = false;
+uncle->red = false;
+grandpa->red = true;
+node = grandpa;
+continue;
+}
+// at this point, uncle is black
+if (node == parent->right && parent == grandpa->left)
+rotateLeft(node = parent);
+else if (node == parent->left && parent == grandpa->right)
+rotateRight(node = parent);
+parent = node->parent;
+if (parent == grandpa->left) {
+rotateRight(grandpa);
+parent->red = false;
+grandpa->red = true;
+} else {
+rotateLeft(grandpa);
+parent->red = false;
+grandpa->red = true;
+}
+return;
+}
+}
+template <class T>
+inline void QRBTree<T>::attachLeft(Node *parent, Node *child)
+{
+Q_ASSERT(!parent->left);
+parent->left = child;
+child->parent = parent;
+update(child);
+}
+template <class T>
+inline void QRBTree<T>::attachRight(Node *parent, Node *child)
+{
+Q_ASSERT(!parent->right);
+parent->right = child;
+child->parent = parent;
+update(child);
+}
+template <class T>
+void QRBTree<T>::attachBefore(Node *parent, Node *child)
+{
+if (!root)
+update(root = child);
+else if (!parent)
+attachRight(back(root), child);
+else if (parent->left)
+attachRight(back(parent->left), child);
+else
+attachLeft(parent, child);
+}
+template <class T>
+void QRBTree<T>::attachAfter(Node *parent, Node *child)
+{
+if (!root)
+update(root = child);
+else if (!parent)
+attachLeft(front(root), child);
+else if (parent->right)
+attachLeft(front(parent->right), child);
+else
+attachRight(parent, child);
+}
+template <class T>
+void QRBTree<T>::swapNodes(Node *n1, Node *n2)
+{
+// Since iterators must not be invalidated, it is not sufficient to only swap the data.
+if (n1->parent == n2) {
+n1->parent = n2->parent;
+n2->parent = n1;
+} else if (n2->parent == n1) {
+n2->parent = n1->parent;
+n1->parent = n2;
+} else {
+qSwap(n1->parent, n2->parent);
+}
+qSwap(n1->left, n2->left);
+qSwap(n1->right, n2->right);
+qSwap(n1->red, n2->red);
+if (n1->parent) {
+if (n1->parent->left == n2)
+n1->parent->left = n1;
+else
+n1->parent->right = n1;
+} else {
+root = n1;
+}
+if (n2->parent) {
+if (n2->parent->left == n1)
+n2->parent->left = n2;
+else
+n2->parent->right = n2;
+} else {
+root = n2;
+}
+if (n1->left)
+n1->left->parent = n1;
+if (n1->right)
+n1->right->parent = n1;
+if (n2->left)
+n2->left->parent = n2;
+if (n2->right)
+n2->right->parent = n2;
+}
+template <class T>
+void QRBTree<T>::detach(Node *node) // call this before removing a node.
+{
+if (node->right)
+swapNodes(node, front(node->right));
+Node *child = (node->left ? node->left : node->right);
+if (!node->red) {
+if (child && child->red)
+child->red = false;
+else
+rebalance(node);
+}
+Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
+ref = child;
+if (child)
+child->parent = node->parent;
+node->left = node->right = node->parent = 0;
+}
+// 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree.
+template <class T>
+void QRBTree<T>::rebalance(Node *node)
+{
+Q_ASSERT(!node->red);
+for (;;) {
+if (!node->parent)
+return;
+// at this point, node is not a parent, it is black, thus it must have a sibling.
+Node *sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
+Q_ASSERT(sibling);
+if (sibling->red) {
+sibling->red = false;
+node->parent->red = true;
+if (node == node->parent->left)
+rotateLeft(node->parent);
+else
+rotateRight(node->parent);
+sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
+Q_ASSERT(sibling);
+}
+// at this point, the sibling is black.
+Q_ASSERT(!sibling->red);
+if ((!sibling->left || !sibling->left->red) && (!sibling->right || !sibling->right->red)) {
+bool parentWasRed = node->parent->red;
+sibling->red = true;
+node->parent->red = false;
+if (parentWasRed)
+return;
+node = node->parent;
+continue;
+}
+// at this point, at least one of the sibling's children is red.
+if (node == node->parent->left) {
+if (!sibling->right || !sibling->right->red) {
+Q_ASSERT(sibling->left);
+sibling->red = true;
+sibling->left->red = false;
+rotateRight(sibling);
+sibling = sibling->parent;
+Q_ASSERT(sibling);
+}
+sibling->red = node->parent->red;
+node->parent->red = false;
+Q_ASSERT(sibling->right->red);
+sibling->right->red = false;
+rotateLeft(node->parent);
+} else {
+if (!sibling->left || !sibling->left->red) {
+Q_ASSERT(sibling->right);
+sibling->red = true;
+sibling->right->red = false;
+rotateLeft(sibling);
+sibling = sibling->parent;
+Q_ASSERT(sibling);
+}
+sibling->red = node->parent->red;
+node->parent->red = false;
+Q_ASSERT(sibling->left->red);
+sibling->left->red = false;
+rotateRight(node->parent);
+}
+return;
+}
+}
+template <class T>
+inline typename QRBTree<T>::Node *QRBTree<T>::front(Node *node) const
+{
+while (node->left)
+node = node->left;
+return node;
+}
+template <class T>
+inline typename QRBTree<T>::Node *QRBTree<T>::back(Node *node) const
+{
+while (node->right)
+node = node->right;
+return node;
+}
+template <class T>
+typename QRBTree<T>::Node *QRBTree<T>::next(Node *node) const
+{
+if (node->right)
+return front(node->right);
+while (node->parent && node == node->parent->right)
+node = node->parent;
+return node->parent;
+}
+template <class T>
+typename QRBTree<T>::Node *QRBTree<T>::previous(Node *node) const
+{
+if (node->left)
+return back(node->left);
+while (node->parent && node == node->parent->left)
+node = node->parent;
+return node->parent;
+}
+template <class T>
+int QRBTree<T>::blackDepth(Node *top) const
+{
+if (!top)
+return 0;
+int leftDepth = blackDepth(top->left);
+int rightDepth = blackDepth(top->right);
+if (leftDepth != rightDepth)
+return -1;
+if (!top->red)
+++leftDepth;
+return leftDepth;
+}
+template <class T>
+bool QRBTree<T>::checkRedBlackProperty(Node *top) const
+{
+if (!top)
+return true;
+if (top->left && !checkRedBlackProperty(top->left))
+return false;
+if (top->right && !checkRedBlackProperty(top->right))
+return false;
+return !(top->red && ((top->left && top->left->red) || (top->right && top->right->red)));
+}
+template <class T>
+inline bool QRBTree<T>::verify() const
+{
+return checkRedBlackProperty(root) && blackDepth(root) != -1;
+}
+template <class T>
+inline void QRBTree<T>::deleteNode(Node *&node)
+{
+Q_ASSERT(node);
+detach(node);
+node->right = freeList;
+freeList = node;
+node = 0;
+}
+template <class T>
+inline typename QRBTree<T>::Node *QRBTree<T>::newNode()
+{
+if (freeList) {
+Node *node = freeList;
+freeList = freeList->right;
+node->parent = node->left = node->right = 0;
+node->red = true;
+return node;
+}
+return new Node;
+}
+// Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise.
+// 'left' and 'right' cannot be null.
+template <class T>
+int QRBTree<T>::order(Node *left, Node *right)
+{
+Q_ASSERT(left && right);
+if (left == right)
+return 0;
+QVector<Node *> leftAncestors;
+QVector<Node *> rightAncestors;
+while (left) {
+leftAncestors.push_back(left);
+left = left->parent;
+}
+while (right) {
+rightAncestors.push_back(right);
+right = right->parent;
+}
+Q_ASSERT(leftAncestors.back() == root && rightAncestors.back() == root);
+while (!leftAncestors.empty() && !rightAncestors.empty() && leftAncestors.back() == rightAncestors.back()) {
+leftAncestors.pop_back();
+rightAncestors.pop_back();
+}
+if (!leftAncestors.empty())
+return (leftAncestors.back() == leftAncestors.back()->parent->left ? -1 : 1);
+if (!rightAncestors.empty())
+return (rightAncestors.back() == rightAncestors.back()->parent->right ? -1 : 1);
+// The code should never reach this point.
+Q_ASSERT(!leftAncestors.empty() || !rightAncestors.empty());
+return 0;
+}
+//============================================================================//
+//                                 QInt64Hash                                 //
+//============================================================================//
+// Copied from qhash.cpp
+static const uchar prime_deltas[] = {
+0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
+1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
+};
+// Copied from qhash.cpp
+static inline int primeForNumBits(int numBits)
+{
+return (1 << numBits) + prime_deltas[numBits];
+}
+static inline int primeForCount(int count)
+{
+int low = 0;
+int high = 32;
+for (int i = 0; i < 5; ++i) {
+int mid = (high + low) / 2;
+if (count >= 1 << mid)
+low = mid;
+else
+high = mid;
+}
+return primeForNumBits(high);
+}
+// Hash set of quint64s. Elements cannot be removed without clearing the
+// entire set. A value of -1 is used to mark unused entries.
+class QInt64Set
+{
+public:
+inline QInt64Set(int capacity = 64);
+inline ~QInt64Set() {if (m_array) delete[] m_array;}
+inline bool isValid() const {return m_array;}
+void insert(quint64 key);
+bool contains(quint64 key) const;
+inline void clear();
+private:
+bool rehash(int capacity);
+static const quint64 UNUSED;
+quint64 *m_array;
+int m_capacity;
+int m_count;
+};
+const quint64 QInt64Set::UNUSED = quint64(-1);
+inline QInt64Set::QInt64Set(int capacity)
+{
+m_capacity = primeForCount(capacity);
+m_array = new quint64[m_capacity];
+if (m_array)
+clear();
+else
+m_capacity = 0;
+}
+bool QInt64Set::rehash(int capacity)
+{
+quint64 *oldArray = m_array;
+int oldCapacity = m_capacity;
+m_capacity = capacity;
+m_array = new quint64[m_capacity];
+if (m_array) {
+clear();
+if (oldArray) {
+for (int i = 0; i < oldCapacity; ++i) {
+if (oldArray[i] != UNUSED)
+insert(oldArray[i]);
+}
+delete[] oldArray;
+}
+return true;
+} else {
+m_capacity = oldCapacity;
+m_array = oldArray;
+return false;
+}
+}
+void QInt64Set::insert(quint64 key)
+{
+if (m_count > 3 * m_capacity / 4)
+rehash(primeForCount(2 * m_capacity));
+Q_ASSERT_X(m_array, "QInt64Hash<T>::insert", "Hash set not allocated.");
+int index = int(key % m_capacity);
+for (int i = 0; i < m_capacity; ++i) {
+index += i;
+if (index >= m_capacity)
+index -= m_capacity;
+if (m_array[index] == key)
+return;
+if (m_array[index] == UNUSED) {
+++m_count;
+m_array[index] = key;
+return;
+}
+}
+Q_ASSERT_X(0, "QInt64Hash<T>::insert", "Hash set full.");
+}
+bool QInt64Set::contains(quint64 key) const
+{
+Q_ASSERT_X(m_array, "QInt64Hash<T>::contains", "Hash set not allocated.");
+int index = int(key % m_capacity);
+for (int i = 0; i < m_capacity; ++i) {
+index += i;
+if (index >= m_capacity)
+index -= m_capacity;
+if (m_array[index] == key)
+return true;
+if (m_array[index] == UNUSED)
+return false;
+}
+return false;
+}
+inline void QInt64Set::clear()
+{
+Q_ASSERT_X(m_array, "QInt64Hash<T>::clear", "Hash set not allocated.");
+for (int i = 0; i < m_capacity; ++i)
+m_array[i] = UNUSED;
+m_count = 0;
+}
+//============================================================================//
+//                                QRingBuffer                                 //
+//============================================================================//
+// T must be POD.
+template <class T>
+class QRingBuffer
+{
+public:
+inline QRingBuffer() : m_array(0), m_head(0), m_size(0), m_capacity(0) { }
+inline ~QRingBuffer() {if (m_array) delete[] m_array;}
+bool reallocate(int capacity);
+inline const T &head() const {Q_ASSERT(m_size > 0); return m_array[m_head];}
+inline const T &dequeue();
+inline void enqueue(const T &x);
+inline bool isEmpty() const {return m_size == 0;}
+private:
+T *m_array;
+int m_head;
+int m_size;
+int m_capacity;
+};
+template <class T>
+bool QRingBuffer<T>::reallocate(int capacity)
+{
+T *oldArray = m_array;
+m_array = new T[capacity];
+if (m_array) {
+if (oldArray) {
+if (m_head + m_size > m_capacity) {
+memcpy(m_array, oldArray + m_head, (m_capacity - m_head) * sizeof(T));
+memcpy(m_array + (m_capacity - m_head), oldArray, (m_head + m_size - m_capacity) * sizeof(T));
+} else {
+memcpy(m_array, oldArray + m_head, m_size * sizeof(T));
+}
+delete[] oldArray;
+}
+m_capacity = capacity;
+m_head = 0;
+return true;
+} else {
+m_array = oldArray;
+return false;
+}
+}
+template <class T>
+inline const T &QRingBuffer<T>::dequeue()
+{
+Q_ASSERT(m_size > 0);
+Q_ASSERT(m_array);
+Q_ASSERT(m_capacity >= m_size);
+int index = m_head;
+if (++m_head >= m_capacity)
+m_head -= m_capacity;
+--m_size;
+return m_array[index];
+}
+template <class T>
+inline void QRingBuffer<T>::enqueue(const T &x)
+{
+if (m_size == m_capacity)
+reallocate(qMax(2 * m_capacity, 64));
+int index = m_head + m_size;
+if (index >= m_capacity)
+index -= m_capacity;
+m_array[index] = x;
+++m_size;
+}
+//============================================================================//
+//                               QTriangulator                                //
+//============================================================================//
+class QTriangulator
+{
+public:
+typedef QVarLengthArray<int, 6> ShortArray;
+//================================//
+// QTriangulator::ComplexToSimple //
+//================================//
+friend class ComplexToSimple;
+class ComplexToSimple
+{
+public:
+inline ComplexToSimple(QTriangulator *parent) : m_parent(parent),
+m_edges(0), m_events(0), m_splits(0) { }
+void decompose();
+private:
+struct Edge
+{
+inline int &upper() {return pointingUp ? to : from;}
+inline int &lower() {return pointingUp ? from : to;}
+inline int upper() const {return pointingUp ? to : from;}
+inline int lower() const {return pointingUp ? from : to;}
+QRBTree<int>::Node *node;
+int from, to; // vertex
+int next, previous; // edge
+int winding;
+bool mayIntersect;
+bool pointingUp, originallyPointingUp;
+};
+friend class CompareEdges;
+class CompareEdges
+{
+public:
+inline CompareEdges(ComplexToSimple *parent) : m_parent(parent) { }
+bool operator () (int i, int j) const;
+private:
+ComplexToSimple *m_parent;
+};
+struct Intersection
+{
+bool operator < (const Intersection &other) const {return other.intersectionPoint < intersectionPoint;}
+QIntersectionPoint intersectionPoint;
+int vertex;
+int leftEdge;
+int rightEdge;
+};
+struct Split
+{
+int vertex;
+int edge;
+bool accurate;
+};
+struct Event
+{
+enum Type {Upper, Lower};
+inline bool operator < (const Event &other) const;
+QPodPoint point;
+Type type;
+int edge;
+};
+#ifdef Q_TRIANGULATOR_DEBUG
+friend class DebugDialog;
+friend class QTriangulator;
+class DebugDialog : public QDialog
+{
+public:
+DebugDialog(ComplexToSimple *parent, int currentVertex);
+protected:
+void paintEvent(QPaintEvent *);
+void wheelEvent(QWheelEvent *);
+void mouseMoveEvent(QMouseEvent *);
+void mousePressEvent(QMouseEvent *);
+private:
+ComplexToSimple *m_parent;
+QRectF m_window;
+QPoint m_lastMousePos;
+int m_vertex;
+};
+#endif
+void initEdges();
+bool calculateIntersection(int left, int right);
+bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const;
+QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex) const;
+QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const;
+QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> bounds(const QPodPoint &point) const;
+QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> outerBounds(const QPodPoint &point) const;
+void splitEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint);
+void reorderEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost);
+void sortEdgeList(const QPodPoint eventPoint);
+void fillPriorityQueue();
+void calculateIntersections();
+int splitEdge(int splitIndex);
+bool splitEdgesAtIntersections();
+void insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i);
+void removeUnwantedEdgesAndConnect();
+void removeUnusedPoints();
+QTriangulator *m_parent;
+QDataBuffer<Edge> m_edges;
+QRBTree<int> m_edgeList;
+QDataBuffer<Event> m_events;
+QDataBuffer<Split> m_splits;
+QMaxHeap<Intersection> m_topIntersection;
+QInt64Set m_processedEdgePairs;
+int m_initialPointCount;
+};
+#ifdef Q_TRIANGULATOR_DEBUG
+friend class ComplexToSimple::DebugDialog;
+#endif
+//=================================//
+// QTriangulator::SimpleToMonotone //
+//=================================//
+friend class SimpleToMonotone;
+class SimpleToMonotone
+{
+public:
+inline SimpleToMonotone(QTriangulator *parent) : m_parent(parent), m_edges(0), m_upperVertex(0) { }
+void decompose();
+private:
+enum VertexType {MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex};
+struct Edge
+{
+QRBTree<int>::Node *node;
+int helper, twin, next, previous;
+quint32 from, to;
+VertexType type;
+bool pointingUp;
+int upper() const {return (pointingUp ? to : from);}
+int lower() const {return (pointingUp ? from : to);}
+};
+friend class CompareVertices;
+class CompareVertices
+{
+public:
+CompareVertices(SimpleToMonotone *parent) : m_parent(parent) { }
+bool operator () (int i, int j) const;
+private:
+SimpleToMonotone *m_parent;
+};
+void setupDataStructures();
+void removeZeroLengthEdges();
+void fillPriorityQueue();
+bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const;
+// Returns the rightmost edge not to the right of the given edge.
+QRBTree<int>::Node *searchEdgeLeftOfEdge(int edgeIndex) const;
+// Returns the rightmost edge left of the given point.
+QRBTree<int>::Node *searchEdgeLeftOfPoint(int pointIndex) const;
+void classifyVertex(int i);
+void classifyVertices();
+bool pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3);
+bool pointIsInSector(int vertex, int sector);
+int findSector(int edge, int vertex);
+void createDiagonal(int lower, int upper);
+void monotoneDecomposition();
+QTriangulator *m_parent;
+QRBTree<int> m_edgeList;
+QDataBuffer<Edge> m_edges;
+QDataBuffer<int> m_upperVertex;
+bool m_clockwiseOrder;
+};
+//====================================//
+// QTriangulator::MonotoneToTriangles //
+//====================================//
+friend class MonotoneToTriangles;
+class MonotoneToTriangles
+{
+public:
+inline MonotoneToTriangles(QTriangulator *parent) : m_parent(parent) { }
+void decompose();
+private:
+inline quint32 indices(int index) const {return m_parent->m_indices.at(index + m_first);}
+inline int next(int index) const {return (index + 1) % m_length;}
+inline int previous(int index) const {return (index + m_length - 1) % m_length;}
+inline bool less(int i, int j) const {return m_parent->m_vertices.at(indices(i)) < m_parent->m_vertices.at(indices(j));}
+inline bool leftOfEdge(int i, int j, int k) const
+{
+return qPointIsLeftOfLine(m_parent->m_vertices.at(indices(i)),
+m_parent->m_vertices.at(indices(j)), m_parent->m_vertices.at(indices(k)));
+}
+QTriangulator *m_parent;
+int m_first;
+int m_length;
+};
+inline QTriangulator() : m_vertices(0) { }
+// Call this only once.
+void initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix);
+// Call this only once.
+void initialize(const QVectorPath &path, const QTransform &matrix, qreal lod);
+// Call this only once.
+void initialize(const QPainterPath &path, const QTransform &matrix, qreal lod);
+// Call either triangulate() or polyline() only once.
+QTriangleSet triangulate();
+QPolylineSet polyline();
+private:
+QDataBuffer<QPodPoint> m_vertices;
+QVector<quint32> m_indices;
+uint m_hint;
+};
+//============================================================================//
+//                               QTriangulator                                //
+//============================================================================//
+QTriangleSet QTriangulator::triangulate()
+{
+for (int i = 0; i < m_vertices.size(); ++i) {
+Q_ASSERT(qAbs(m_vertices.at(i).x) < (1 << 21));
+Q_ASSERT(qAbs(m_vertices.at(i).y) < (1 << 21));
+}
+if (!(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill)))
+m_hint |= QVectorPath::OddEvenFill;
+if (m_hint & QVectorPath::NonConvexShapeMask) {
+ComplexToSimple c2s(this);
+c2s.decompose();
+SimpleToMonotone s2m(this);
+s2m.decompose();
+}
+MonotoneToTriangles m2t(this);
+m2t.decompose();
+QTriangleSet result;
+result.indices = m_indices;
+result.vertices.resize(2 * m_vertices.size());
+for (int i = 0; i < m_vertices.size(); ++i) {
+result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / Q_FIXED_POINT_SCALE;
+result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / Q_FIXED_POINT_SCALE;
+}
+return result;
+}
+QPolylineSet QTriangulator::polyline()
+{
+QPolylineSet result;
+result.indices = m_indices;
+result.vertices.resize(2 * m_vertices.size());
+for (int i = 0; i < m_vertices.size(); ++i) {
+result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / Q_FIXED_POINT_SCALE;
+result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / Q_FIXED_POINT_SCALE;
+}
+return result;
+}
+void QTriangulator::initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix)
+{
+m_hint = hint;
+m_vertices.resize(count);
+m_indices.resize(count + 1);
+for (int i = 0; i < count; ++i) {
+qreal x, y;
+matrix.map(polygon[2 * i + 0], polygon[2 * i + 1], &x, &y);
+m_vertices.at(i).x = qRound(x * Q_FIXED_POINT_SCALE);
+m_vertices.at(i).y = qRound(y * Q_FIXED_POINT_SCALE);
+m_indices[i] = i;
+}
+m_indices[count] = Q_TRIANGULATE_END_OF_POLYGON;
+}
+void QTriangulator::initialize(const QVectorPath &path, const QTransform &matrix, qreal lod)
+{
+m_hint = path.hints();
+// Curved paths will be converted to complex polygons.
+m_hint &= ~QVectorPath::CurvedShapeMask;
+const qreal *p = path.points();
+const QPainterPath::ElementType *e = path.elements();
+if (e) {
+for (int i = 0; i < path.elementCount(); ++i, ++e, p += 2) {
+switch (*e) {
+case QPainterPath::MoveToElement:
+if (!m_indices.isEmpty())
+m_indices.push_back(Q_TRIANGULATE_END_OF_POLYGON);
+// Fall through.
+case QPainterPath::LineToElement:
+m_indices.push_back(quint32(m_vertices.size()));
+m_vertices.resize(m_vertices.size() + 1);
+qreal x, y;
+matrix.map(p[0], p[1], &x, &y);
+m_vertices.last().x = qRound(x * Q_FIXED_POINT_SCALE);
+m_vertices.last().y = qRound(y * Q_FIXED_POINT_SCALE);
+break;
+case QPainterPath::CurveToElement:
+{
+qreal pts[8];
+for (int i = 0; i < 4; ++i)
+matrix.map(p[2 * i - 2], p[2 * i - 1], &pts[2 * i + 0], &pts[2 * i + 1]);
+for (int i = 0; i < 8; ++i)
+pts[i] *= lod;
+QBezier bezier = QBezier::fromPoints(QPointF(pts[0], pts[1]), QPointF(pts[2], pts[3]), QPointF(pts[4], pts[5]), QPointF(pts[6], pts[7]));
+QPolygonF poly = bezier.toPolygon();
+// Skip first point, it already exists in 'm_vertices'.
+for (int j = 1; j < poly.size(); ++j) {
+m_indices.push_back(quint32(m_vertices.size()));
+m_vertices.resize(m_vertices.size() + 1);
+m_vertices.last().x = qRound(poly.at(j).x() * Q_FIXED_POINT_SCALE / lod);
+m_vertices.last().y = qRound(poly.at(j).y() * Q_FIXED_POINT_SCALE / lod);
+}
+}
+i += 2;
+e += 2;
+p += 4;
+break;
+default:
+Q_ASSERT_X(0, "QTriangulator::triangulate", "Unexpected element type.");
+break;
+}
+}
+} else {
+for (int i = 0; i < path.elementCount(); ++i, p += 2) {
+m_indices.push_back(quint32(m_vertices.size()));
+m_vertices.resize(m_vertices.size() + 1);
+qreal x, y;
+matrix.map(p[0], p[1], &x, &y);
+m_vertices.last().x = qRound(x * Q_FIXED_POINT_SCALE);
+m_vertices.last().y = qRound(y * Q_FIXED_POINT_SCALE);
+}
+}
+m_indices.push_back(Q_TRIANGULATE_END_OF_POLYGON);
+}
+void QTriangulator::initialize(const QPainterPath &path, const QTransform &matrix, qreal lod)
+{
+initialize(qtVectorPathForPath(path), matrix, lod);
+}
+//============================================================================//
+//                       QTriangulator::ComplexToSimple                       //
+//============================================================================//
+void QTriangulator::ComplexToSimple::decompose()
+{
+m_initialPointCount = m_parent->m_vertices.size();
+initEdges();
+do {
+calculateIntersections();
+} while (splitEdgesAtIntersections());
+removeUnwantedEdgesAndConnect();
+removeUnusedPoints();
+m_parent->m_indices.clear();
+QBitArray processed(m_edges.size(), false);
+for (int first = 0; first < m_edges.size(); ++first) {
+// If already processed, or if unused path, skip.
+if (processed.at(first) || m_edges.at(first).next == -1)
+continue;
+int i = first;
+do {
+Q_ASSERT(!processed.at(i));
+Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i);
+m_parent->m_indices.push_back(m_edges.at(i).from);
+processed.setBit(i);
+i = m_edges.at(i).next; // CCW order
+} while (i != first);
+m_parent->m_indices.push_back(Q_TRIANGULATE_END_OF_POLYGON);
+}
+}
+void QTriangulator::ComplexToSimple::initEdges()
+{
+// Initialize edge structure.
+// 'next' and 'previous' are not being initialized at this point.
+int first = 0;
+for (int i = 0; i < m_parent->m_indices.size(); ++i) {
+if (m_parent->m_indices.at(i) == Q_TRIANGULATE_END_OF_POLYGON) {
+if (m_edges.size() != first)
+m_edges.last().to = m_edges.at(first).from;
+first = m_edges.size();
+} else {
+Q_ASSERT(i + 1 < m_parent->m_indices.size());
+// {node, from, to, next, previous, winding, mayIntersect, pointingUp, originallyPointingUp}
+Edge edge = {0, m_parent->m_indices.at(i), m_parent->m_indices.at(i + 1), -1, -1, 0, true, false, false};
+m_edges.add(edge);
+}
+}
+if (first != m_edges.size())
+m_edges.last().to = m_edges.at(first).from;
+for (int i = 0; i < m_edges.size(); ++i) {
+m_edges.at(i).originallyPointingUp = 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);
+}
+}
+// Return true if new intersection was found
+bool QTriangulator::ComplexToSimple::calculateIntersection(int left, int right)
+{
+const Edge &e1 = m_edges.at(left);
+const Edge &e2 = m_edges.at(right);
+const QPodPoint &u1 = m_parent->m_vertices.at(e1.from);
+const QPodPoint &u2 = m_parent->m_vertices.at(e1.to);
+const QPodPoint &v1 = m_parent->m_vertices.at(e2.from);
+const QPodPoint &v2 = m_parent->m_vertices.at(e2.to);
+if (qMax(u1.x, u2.x) <= qMin(v1.x, v2.x))
+return false;
+quint64 key = (left > right ? (quint64(right) << 32) | quint64(left) : (quint64(left) << 32) | quint64(right));
+if (m_processedEdgePairs.contains(key))
+return false;
+m_processedEdgePairs.insert(key);
+Intersection intersection;
+intersection.leftEdge = left;
+intersection.rightEdge = right;
+intersection.intersectionPoint = qIntersectionPoint(u1, u2, v1, v2);
+if (!intersection.intersectionPoint.isValid())
+return false;
+Q_ASSERT(intersection.intersectionPoint.isOnLine(u1, u2));
+Q_ASSERT(intersection.intersectionPoint.isOnLine(v1, v2));
+intersection.vertex = m_parent->m_vertices.size();
+m_topIntersection.push(intersection);
+m_parent->m_vertices.add(intersection.intersectionPoint.round());
+return true;
+}
+bool QTriangulator::ComplexToSimple::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const
+{
+const Edge &leftEdge = m_edges.at(leftEdgeIndex);
+const Edge &rightEdge = m_edges.at(rightEdgeIndex);
+const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
+const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
+const QPodPoint &upper = m_parent->m_vertices.at(leftEdge.upper());
+if (upper.x < qMin(l.x, u.x))
+return true;
+if (upper.x > qMax(l.x, u.x))
+return false;
+qint64 d = qPointDistanceFromLine(upper, l, u);
+// d < 0: left, d > 0: right, d == 0: on top
+if (d == 0)
+d = qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.lower()), l, u);
+return d < 0;
+}
+QRBTree<int>::Node *QTriangulator::ComplexToSimple::searchEdgeLeftOf(int edgeIndex) const
+{
+QRBTree<int>::Node *current = m_edgeList.root;
+QRBTree<int>::Node *result = 0;
+while (current) {
+if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
+current = current->left;
+} else {
+result = current;
+current = current->right;
+}
+}
+return result;
+}
+QRBTree<int>::Node *QTriangulator::ComplexToSimple::searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const
+{
+if (!m_edgeList.root)
+return after;
+QRBTree<int>::Node *result = after;
+QRBTree<int>::Node *current = (after ? m_edgeList.next(after) : m_edgeList.front(m_edgeList.root));
+while (current) {
+if (edgeIsLeftOfEdge(edgeIndex, current->data))
+return result;
+result = current;
+current = m_edgeList.next(current);
+}
+return result;
+}
+QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator::ComplexToSimple::bounds(const QPodPoint &point) const
+{
+QRBTree<int>::Node *current = m_edgeList.root;
+QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0);
+while (current) {
+const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+qint64 d = qPointDistanceFromLine(point, v1, v2);
+if (d == 0) {
+result.first = result.second = current;
+break;
+}
+current = (d < 0 ? current->left : current->right);
+}
+if (current == 0)
+return result;
+current = result.first->left;
+while (current) {
+const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+qint64 d = qPointDistanceFromLine(point, v1, v2);
+Q_ASSERT(d >= 0);
+if (d == 0) {
+result.first = current;
+current = current->left;
+} else {
+current = current->right;
+}
+}
+current = result.second->right;
+while (current) {
+const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+qint64 d = qPointDistanceFromLine(point, v1, v2);
+Q_ASSERT(d <= 0);
+if (d == 0) {
+result.second = current;
+current = current->right;
+} else {
+current = current->left;
+}
+}
+return result;
+}
+QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator::ComplexToSimple::outerBounds(const QPodPoint &point) const
+{
+QRBTree<int>::Node *current = m_edgeList.root;
+QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0);
+while (current) {
+const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+qint64 d = qPointDistanceFromLine(point, v1, v2);
+if (d == 0)
+break;
+if (d < 0) {
+result.second = current;
+current = current->left;
+} else {
+result.first = current;
+current = current->right;
+}
+}
+if (!current)
+return result;
+QRBTree<int>::Node *mid = current;
+current = mid->left;
+while (current) {
+const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+qint64 d = qPointDistanceFromLine(point, v1, v2);
+Q_ASSERT(d >= 0);
+if (d == 0) {
+current = current->left;
+} else {
+result.first = current;
+current = current->right;
+}
+}
+current = mid->right;
+while (current) {
+const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+qint64 d = qPointDistanceFromLine(point, v1, v2);
+Q_ASSERT(d <= 0);
+if (d == 0) {
+current = current->right;
+} else {
+result.second = current;
+current = current->left;
+}
+}
+return result;
+}
+void QTriangulator::ComplexToSimple::splitEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint)
+{
+Q_ASSERT(leftmost && rightmost);
+// Split.
+for (;;) {
+const QPodPoint &u = m_parent->m_vertices.at(m_edges.at(leftmost->data).from);
+const QPodPoint &v = m_parent->m_vertices.at(m_edges.at(leftmost->data).to);
+Q_ASSERT(intersectionPoint.isOnLine(u, v));
+const Split split = {vertex, leftmost->data, intersectionPoint.isAccurate()};
+if (intersectionPoint.xOffset.numerator != 0 || intersectionPoint.yOffset.numerator != 0 || (intersectionPoint.upperLeft != u && intersectionPoint.upperLeft != v))
+m_splits.add(split);
+if (leftmost == rightmost)
+break;
+leftmost = m_edgeList.next(leftmost);
+}
+}
+void QTriangulator::ComplexToSimple::reorderEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost)
+{
+Q_ASSERT(leftmost && rightmost);
+QRBTree<int>::Node *storeLeftmost = leftmost;
+QRBTree<int>::Node *storeRightmost = rightmost;
+// Reorder.
+while (leftmost != rightmost) {
+Edge &left = m_edges.at(leftmost->data);
+Edge &right = m_edges.at(rightmost->data);
+qSwap(left.node, right.node);
+qSwap(leftmost->data, rightmost->data);
+leftmost = m_edgeList.next(leftmost);
+if (leftmost == rightmost)
+break;
+rightmost = m_edgeList.previous(rightmost);
+}
+rightmost = m_edgeList.next(storeRightmost);
+leftmost = m_edgeList.previous(storeLeftmost);
+if (leftmost)
+calculateIntersection(leftmost->data, storeLeftmost->data);
+if (rightmost)
+calculateIntersection(storeRightmost->data, rightmost->data);
+}
+void QTriangulator::ComplexToSimple::sortEdgeList(const QPodPoint eventPoint)
+{
+QIntersectionPoint eventPoint2 = qIntersectionPoint(eventPoint);
+while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint < eventPoint2) {
+Intersection intersection = m_topIntersection.pop();
+QIntersectionPoint currentIntersectionPoint = intersection.intersectionPoint;
+int currentVertex = intersection.vertex;
+QRBTree<int>::Node *leftmost = m_edges.at(intersection.leftEdge).node;
+QRBTree<int>::Node *rightmost = m_edges.at(intersection.rightEdge).node;
+for (;;) {
+QRBTree<int>::Node *previous = m_edgeList.previous(leftmost);
+if (!previous)
+break;
+const Edge &edge = m_edges.at(previous->data);
+const QPodPoint &u = m_parent->m_vertices.at(edge.from);
+const QPodPoint &v = m_parent->m_vertices.at(edge.to);
+if (!currentIntersectionPoint.isOnLine(u, v)) {
+Q_ASSERT(!currentIntersectionPoint.isAccurate() || qCross(currentIntersectionPoint.upperLeft - u, v - u) != 0);
+break;
+}
+leftmost = previous;
+}
+for (;;) {
+QRBTree<int>::Node *next = m_edgeList.next(rightmost);
+if (!next)
+break;
+const Edge &edge = m_edges.at(next->data);
+const QPodPoint &u = m_parent->m_vertices.at(edge.from);
+const QPodPoint &v = m_parent->m_vertices.at(edge.to);
+if (!currentIntersectionPoint.isOnLine(u, v)) {
+Q_ASSERT(!currentIntersectionPoint.isAccurate() || qCross(currentIntersectionPoint.upperLeft - u, v - u) != 0);
+break;
+}
+rightmost = next;
+}
+Q_ASSERT(leftmost && rightmost);
+splitEdgeListRange(leftmost, rightmost, currentVertex, currentIntersectionPoint);
+reorderEdgeListRange(leftmost, rightmost);
+while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= currentIntersectionPoint)
+m_topIntersection.pop();
+#ifdef Q_TRIANGULATOR_DEBUG
+DebugDialog dialog(this, intersection.vertex);
+dialog.exec();
+#endif
+}
+}
+void QTriangulator::ComplexToSimple::fillPriorityQueue()
+{
+m_events.reset();
+m_events.reserve(m_edges.size() * 2);
+for (int i = 0; i < m_edges.size(); ++i) {
+Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1);
+Q_ASSERT(m_edges.at(i).node == 0);
+Q_ASSERT(m_edges.at(i).pointingUp == m_edges.at(i).originallyPointingUp);
+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)));
+// Ignore zero-length edges.
+if (m_parent->m_vertices.at(m_edges.at(i).to) != m_parent->m_vertices.at(m_edges.at(i).from)) {
+QPodPoint upper = m_parent->m_vertices.at(m_edges.at(i).upper());
+QPodPoint lower = m_parent->m_vertices.at(m_edges.at(i).lower());
+Event upperEvent = {{upper.x, upper.y}, Event::Upper, i};
+Event lowerEvent = {{lower.x, lower.y}, Event::Lower, i};
+m_events.add(upperEvent);
+m_events.add(lowerEvent);
+}
+}
+//qSort(m_events.data(), m_events.data() + m_events.size());
+sort(m_events.data(), m_events.size());
+}
+void QTriangulator::ComplexToSimple::calculateIntersections()
+{
+fillPriorityQueue();
+Q_ASSERT(m_topIntersection.empty());
+Q_ASSERT(m_edgeList.root == 0);
+// Find all intersection points.
+while (!m_events.isEmpty()) {
+Event event = m_events.last();
+sortEdgeList(event.point);
+// Find all edges in the edge list that contain the current vertex and mark them to be split later.
+QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> range = bounds(event.point);
+QRBTree<int>::Node *leftNode = range.first ? m_edgeList.previous(range.first) : 0;
+int vertex = (event.type == Event::Upper ? m_edges.at(event.edge).upper() : m_edges.at(event.edge).lower());
+QIntersectionPoint eventPoint = qIntersectionPoint(event.point);
+if (range.first != 0) {
+splitEdgeListRange(range.first, range.second, vertex, eventPoint);
+reorderEdgeListRange(range.first, range.second);
+}
+// Handle the edges with start or end point in the current vertex.
+while (!m_events.isEmpty() && m_events.last().point == event.point) {
+event = m_events.last();
+m_events.pop_back();
+int i = event.edge;
+if (m_edges.at(i).node) {
+// Remove edge from edge list.
+Q_ASSERT(event.type == Event::Lower);
+QRBTree<int>::Node *left = m_edgeList.previous(m_edges.at(i).node);
+QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node);
+m_edgeList.deleteNode(m_edges.at(i).node);
+if (!left || !right)
+continue;
+calculateIntersection(left->data, right->data);
+} else {
+// Insert edge into edge list.
+Q_ASSERT(event.type == Event::Upper);
+QRBTree<int>::Node *left = searchEdgeLeftOf(i, leftNode);
+m_edgeList.attachAfter(left, m_edges.at(i).node = m_edgeList.newNode());
+m_edges.at(i).node->data = i;
+QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node);
+if (left)
+calculateIntersection(left->data, i);
+if (right)
+calculateIntersection(i, right->data);
+}
+}
+while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= eventPoint)
+m_topIntersection.pop();
+#ifdef Q_TRIANGULATOR_DEBUG
+DebugDialog dialog(this, vertex);
+dialog.exec();
+#endif
+}
+m_processedEdgePairs.clear();
+}
+// Split an edge into two pieces at the given point.
+// The upper piece is pushed to the end of the 'm_edges' vector.
+// The lower piece replaces the old edge.
+// Return the edge whose 'from' is 'pointIndex'.
+int QTriangulator::ComplexToSimple::splitEdge(int splitIndex)
+{
+const Split &split = m_splits.at(splitIndex);
+Edge &lowerEdge = m_edges.at(split.edge);
+Q_ASSERT(lowerEdge.node == 0);
+Q_ASSERT(lowerEdge.previous == -1 && lowerEdge.next == -1);
+if (lowerEdge.from == split.vertex)
+return split.edge;
+if (lowerEdge.to == split.vertex)
+return lowerEdge.next;
+// Check that angle >= 90 degrees.
+//Q_ASSERT(qDot(m_points.at(m_edges.at(edgeIndex).from) - m_points.at(pointIndex),
+//    m_points.at(m_edges.at(edgeIndex).to) - m_points.at(pointIndex)) <= 0);
+Edge upperEdge = lowerEdge;
+upperEdge.mayIntersect |= !split.accurate; // The edge may have been split before at an inaccurate split point.
+lowerEdge.mayIntersect = !split.accurate;
+if (lowerEdge.pointingUp) {
+lowerEdge.to = upperEdge.from = split.vertex;
+m_edges.add(upperEdge);
+return m_edges.size() - 1;
+} else {
+lowerEdge.from = upperEdge.to = split.vertex;
+m_edges.add(upperEdge);
+return split.edge;
+}
+}
+bool QTriangulator::ComplexToSimple::splitEdgesAtIntersections()
+{
+for (int i = 0; i < m_edges.size(); ++i)
+m_edges.at(i).mayIntersect = false;
+bool checkForNewIntersections = false;
+for (int i = 0; i < m_splits.size(); ++i) {
+splitEdge(i);
+checkForNewIntersections |= !m_splits.at(i).accurate;
+}
+for (int i = 0; i < m_edges.size(); ++i) {
+m_edges.at(i).originallyPointingUp = 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);
+}
+m_splits.reset();
+return checkForNewIntersections;
+}
+void QTriangulator::ComplexToSimple::insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i)
+{
+// Edges with zero length should not reach this part.
+Q_ASSERT(m_parent->m_vertices.at(m_edges.at(i).from) != m_parent->m_vertices.at(m_edges.at(i).to));
+// Skip edges with unwanted winding number.
+int windingNumber = m_edges.at(i).winding;
+if (m_edges.at(i).originallyPointingUp)
+++windingNumber;
+// Make sure exactly one fill rule is specified.
+Q_ASSERT(((m_parent->m_hint & QVectorPath::WindingFill) != 0) != ((m_parent->m_hint & QVectorPath::OddEvenFill) != 0));
+if ((m_parent->m_hint & QVectorPath::WindingFill) && windingNumber != 0 && windingNumber != 1)
+return;
+// Skip cancelling edges.
+if (!orderedEdges.isEmpty()) {
+int j = orderedEdges[orderedEdges.size() - 1];
+// If the last edge is already connected in one end, it should not be cancelled.
+if (m_edges.at(j).next == -1 && m_edges.at(j).previous == -1
+&& (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(j).to))
+&& (m_parent->m_vertices.at(m_edges.at(i).to) == m_parent->m_vertices.at(m_edges.at(j).from))) {
+orderedEdges.removeLast();
+return;
+}
+}
+orderedEdges.append(i);
+}
+void QTriangulator::ComplexToSimple::removeUnwantedEdgesAndConnect()
+{
+Q_ASSERT(m_edgeList.root == 0);
+// Initialize priority queue.
+fillPriorityQueue();
+ShortArray orderedEdges;
+while (!m_events.isEmpty()) {
+Event event = m_events.last();
+int edgeIndex = event.edge;
+// Check that all the edges in the list crosses the current scanline
+//if (m_edgeList.root) {
+//    for (QRBTree<int>::Node *node = m_edgeList.front(m_edgeList.root); node; node = m_edgeList.next(node)) {
+//        Q_ASSERT(event.point <= m_points.at(m_edges.at(node->data).lower()));
+//    }
+//}
+orderedEdges.clear();
+QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> b = outerBounds(event.point);
+if (m_edgeList.root) {
+QRBTree<int>::Node *current = (b.first ? m_edgeList.next(b.first) : m_edgeList.front(m_edgeList.root));
+// Process edges that are going to be removed from the edge list at the current event point.
+while (current != b.second) {
+Q_ASSERT(current);
+Q_ASSERT(m_edges.at(current->data).node == current);
+Q_ASSERT(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)));
+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);
+insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
+current = m_edgeList.next(current);
+}
+}
+// Remove edges above the event point, insert edges below the event point.
+do {
+event = m_events.last();
+m_events.pop_back();
+edgeIndex = event.edge;
+// Edges with zero length should not reach this part.
+Q_ASSERT(m_parent->m_vertices.at(m_edges.at(edgeIndex).from) != m_parent->m_vertices.at(m_edges.at(edgeIndex).to));
+if (m_edges.at(edgeIndex).node) {
+Q_ASSERT(event.type == Event::Lower);
+Q_ASSERT(event.point == m_parent->m_vertices.at(m_edges.at(event.edge).lower()));
+m_edgeList.deleteNode(m_edges.at(edgeIndex).node);
+} else {
+Q_ASSERT(event.type == Event::Upper);
+Q_ASSERT(event.point == m_parent->m_vertices.at(m_edges.at(event.edge).upper()));
+QRBTree<int>::Node *left = searchEdgeLeftOf(edgeIndex, b.first);
+m_edgeList.attachAfter(left, m_edges.at(edgeIndex).node = m_edgeList.newNode());
+m_edges.at(edgeIndex).node->data = edgeIndex;
+}
+} while (!m_events.isEmpty() && m_events.last().point == event.point);
+if (m_edgeList.root) {
+QRBTree<int>::Node *current = (b.first ? m_edgeList.next(b.first) : m_edgeList.front(m_edgeList.root));
+// Calculate winding number and turn counter-clockwise.
+int currentWindingNumber = (b.first ? m_edges.at(b.first->data).winding : 0);
+while (current != b.second) {
+Q_ASSERT(current);
+//Q_ASSERT(b.second == 0 || m_edgeList.order(current, b.second) < 0);
+int i = current->data;
+Q_ASSERT(m_edges.at(i).node == current);
+// Winding number.
+int ccwWindingNumber = m_edges.at(i).winding = currentWindingNumber;
+if (m_edges.at(i).originallyPointingUp) {
+--m_edges.at(i).winding;
+} else {
+++m_edges.at(i).winding;
+++ccwWindingNumber;
+}
+currentWindingNumber = m_edges.at(i).winding;
+// Turn counter-clockwise.
+if ((ccwWindingNumber & 1) == 0) {
+Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1);
+qSwap(m_edges.at(i).from, m_edges.at(i).to);
+m_edges.at(i).pointingUp = !m_edges.at(i).pointingUp;
+}
+current = m_edgeList.next(current);
+}
+// Process edges that were inserted into the edge list at the current event point.
+current = (b.second ? m_edgeList.previous(b.second) : m_edgeList.back(m_edgeList.root));
+while (current != b.first) {
+Q_ASSERT(current);
+Q_ASSERT(m_edges.at(current->data).node == current);
+insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
+current = m_edgeList.previous(current);
+}
+}
+if (orderedEdges.isEmpty())
+continue;
+Q_ASSERT((orderedEdges.size() & 1) == 0);
+// Connect edges.
+// First make sure the first edge point towards the current point.
+int i;
+if (m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).from) == event.point) {
+i = 1;
+int copy = orderedEdges[0]; // Make copy in case the append() will cause a reallocation.
+orderedEdges.append(copy);
+} else {
+Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).to) == event.point);
+i = 0;
+}
+// Remove references to duplicate points. First find the point with lowest index.
+int pointIndex = INT_MAX;
+for (int j = i; j < orderedEdges.size(); j += 2) {
+Q_ASSERT(j + 1 < orderedEdges.size());
+Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[j]).to) == event.point);
+Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[j + 1]).from) == event.point);
+if (m_edges.at(orderedEdges[j]).to < pointIndex)
+pointIndex = m_edges.at(orderedEdges[j]).to;
+if (m_edges.at(orderedEdges[j + 1]).from < pointIndex)
+pointIndex = m_edges.at(orderedEdges[j + 1]).from;
+}
+for (; i < orderedEdges.size(); i += 2) {
+// Remove references to duplicate points by making all edges reference one common point.
+m_edges.at(orderedEdges[i]).to = m_edges.at(orderedEdges[i + 1]).from = pointIndex;
+Q_ASSERT(m_edges.at(orderedEdges[i]).pointingUp || m_edges.at(orderedEdges[i]).previous != -1);
+Q_ASSERT(!m_edges.at(orderedEdges[i + 1]).pointingUp || m_edges.at(orderedEdges[i + 1]).next != -1);
+m_edges.at(orderedEdges[i]).next = orderedEdges[i + 1];
+m_edges.at(orderedEdges[i + 1]).previous = orderedEdges[i];
+}
+} // end while
+}
+void QTriangulator::ComplexToSimple::removeUnusedPoints() {
+QBitArray used(m_parent->m_vertices.size(), false);
+for (int i = 0; i < m_edges.size(); ++i) {
+Q_ASSERT((m_edges.at(i).previous == -1) == (m_edges.at(i).next == -1));
+if (m_edges.at(i).next != -1)
+used.setBit(m_edges.at(i).from);
+}
+QDataBuffer<quint32> newMapping(m_parent->m_vertices.size());
+newMapping.resize(m_parent->m_vertices.size());
+int count = 0;
+for (int i = 0; i < m_parent->m_vertices.size(); ++i) {
+if (used.at(i)) {
+m_parent->m_vertices.at(count) = m_parent->m_vertices.at(i);
+newMapping.at(i) = count;
+++count;
+}
+}
+m_parent->m_vertices.resize(count);
+for (int i = 0; i < m_edges.size(); ++i) {
+m_edges.at(i).from = newMapping.at(m_edges.at(i).from);
+m_edges.at(i).to = newMapping.at(m_edges.at(i).to);
+}
+}
+bool QTriangulator::ComplexToSimple::CompareEdges::operator () (int i, int j) const
+{
+int cmp = comparePoints(m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from),
+m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from));
+if (cmp == 0) {
+cmp = comparePoints(m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).to),
+m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).to));
+}
+return cmp > 0;
+}
+inline bool QTriangulator::ComplexToSimple::Event::operator < (const Event &other) const
+{
+if (point == other.point)
+return type < other.type; // 'Lower' has higher priority than 'Upper'.
+return other.point < point;
+}
+//============================================================================//
+//                QTriangulator::ComplexToSimple::DebugDialog                 //
+//============================================================================//
+#ifdef Q_TRIANGULATOR_DEBUG
+QTriangulator::ComplexToSimple::DebugDialog::DebugDialog(ComplexToSimple *parent, int currentVertex)
+: m_parent(parent), m_vertex(currentVertex)
+{
+QDataBuffer<QPodPoint> &vertices = m_parent->m_parent->m_vertices;
+if (vertices.isEmpty())
+return;
+int minX, maxX, minY, maxY;
+minX = maxX = vertices.at(0).x;
+minY = maxY = vertices.at(0).y;
+for (int i = 1; i < vertices.size(); ++i) {
+minX = qMin(minX, vertices.at(i).x);
+maxX = qMax(maxX, vertices.at(i).x);
+minY = qMin(minY, vertices.at(i).y);
+maxY = qMax(maxY, vertices.at(i).y);
+}
+int w = maxX - minX;
+int h = maxY - minY;
+qreal border = qMin(w, h) / 10.0;
+m_window = QRectF(minX - border, minY - border, (maxX - minX + 2 * border), (maxY - minY + 2 * border));
+}
+void QTriangulator::ComplexToSimple::DebugDialog::paintEvent(QPaintEvent *)
+{
+QPainter p(this);
+p.setRenderHint(QPainter::Antialiasing, true);
+p.fillRect(rect(), Qt::black);
+QDataBuffer<QPodPoint> &vertices = m_parent->m_parent->m_vertices;
+if (vertices.isEmpty())
+return;
+qreal halfPointSize = qMin(m_window.width(), m_window.height()) / 300.0;
+p.setWindow(m_window.toRect());
+p.setPen(Qt::white);
+QDataBuffer<Edge> &edges = m_parent->m_edges;
+for (int i = 0; i < edges.size(); ++i) {
+QPodPoint u = vertices.at(edges.at(i).from);
+QPodPoint v = vertices.at(edges.at(i).to);
+p.drawLine(u.x, u.y, v.x, v.y);
+}
+for (int i = 0; i < vertices.size(); ++i) {
+QPodPoint q = vertices.at(i);
+p.fillRect(QRectF(q.x - halfPointSize, q.y - halfPointSize, 2 * halfPointSize, 2 * halfPointSize), Qt::red);
+}
+Qt::GlobalColor colors[6] = {Qt::red, Qt::green, Qt::blue, Qt::cyan, Qt::magenta, Qt::yellow};
+p.setOpacity(0.5);
+int count = 0;
+if (m_parent->m_edgeList.root) {
+QRBTree<int>::Node *current = m_parent->m_edgeList.front(m_parent->m_edgeList.root);
+while (current) {
+p.setPen(colors[count++ % 6]);
+QPodPoint u = vertices.at(edges.at(current->data).from);
+QPodPoint v = vertices.at(edges.at(current->data).to);
+p.drawLine(u.x, u.y, v.x, v.y);
+current = m_parent->m_edgeList.next(current);
+}
+}
+p.setOpacity(1.0);
+QPodPoint q = vertices.at(m_vertex);
+p.fillRect(QRectF(q.x - halfPointSize, q.y - halfPointSize, 2 * halfPointSize, 2 * halfPointSize), Qt::green);
+p.setPen(Qt::gray);
+QDataBuffer<Split> &splits = m_parent->m_splits;
+for (int i = 0; i < splits.size(); ++i) {
+QPodPoint q = vertices.at(splits.at(i).vertex);
+QPodPoint u = vertices.at(edges.at(splits.at(i).edge).from) - q;
+QPodPoint v = vertices.at(edges.at(splits.at(i).edge).to) - q;
+qreal uLen = sqrt(qreal(qDot(u, u)));
+qreal vLen = sqrt(qreal(qDot(v, v)));
+if (uLen) {
+u.x *= 2 * halfPointSize / uLen;
+u.y *= 2 * halfPointSize / uLen;
+}
+if (vLen) {
+v.x *= 2 * halfPointSize / vLen;
+v.y *= 2 * halfPointSize / vLen;
+}
+u += q;
+v += q;
+p.drawLine(u.x, u.y, v.x, v.y);
+}
+}
+void QTriangulator::ComplexToSimple::DebugDialog::wheelEvent(QWheelEvent *event)
+{
+qreal scale = exp(-0.001 * event->delta());
+QPointF center = m_window.center();
+QPointF delta = scale * (m_window.bottomRight() - center);
+m_window = QRectF(center - delta, center + delta);
+event->accept();
+update();
+}
+void QTriangulator::ComplexToSimple::DebugDialog::mouseMoveEvent(QMouseEvent *event)
+{
+if (event->buttons() & Qt::LeftButton) {
+QPointF delta = event->pos() - m_lastMousePos;
+delta.setX(delta.x() * m_window.width() / width());
+delta.setY(delta.y() * m_window.height() / height());
+m_window.translate(-delta.x(), -delta.y());
+m_lastMousePos = event->pos();
+event->accept();
+update();
+}
+}
+void QTriangulator::ComplexToSimple::DebugDialog::mousePressEvent(QMouseEvent *event)
+{
+if (event->button() == Qt::LeftButton)
+m_lastMousePos = event->pos();
+event->accept();
+}
+#endif
+//============================================================================//
+//                      QTriangulator::SimpleToMonotone                       //
+//============================================================================//
+void QTriangulator::SimpleToMonotone::decompose()
+{
+setupDataStructures();
+removeZeroLengthEdges();
+monotoneDecomposition();
+m_parent->m_indices.clear();
+QBitArray processed(m_edges.size(), false);
+for (int first = 0; first < m_edges.size(); ++first) {
+if (processed.at(first))
+continue;
+int i = first;
+do {
+Q_ASSERT(!processed.at(i));
+Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i);
+m_parent->m_indices.push_back(m_edges.at(i).from);
+processed.setBit(i);
+i = m_edges.at(i).next;
+} while (i != first);
+if (m_parent->m_indices.size() > 0 && m_parent->m_indices.back() != Q_TRIANGULATE_END_OF_POLYGON)
+m_parent->m_indices.push_back(Q_TRIANGULATE_END_OF_POLYGON);
+}
+}
+void QTriangulator::SimpleToMonotone::setupDataStructures()
+{
+int i = 0;
+Edge e;
+e.node = 0;
+e.twin = -1;
+while (i + 3 <= m_parent->m_indices.size()) {
+int start = m_edges.size();
+do {
+e.from = m_parent->m_indices.at(i);
+e.type = RegularVertex;
+e.next = m_edges.size() + 1;
+e.previous = m_edges.size() - 1;
+m_edges.add(e);
+++i;
+Q_ASSERT(i < m_parent->m_indices.size());
+} while (m_parent->m_indices.at(i) != Q_TRIANGULATE_END_OF_POLYGON);
+m_edges.last().next = start;
+m_edges.at(start).previous = m_edges.size() - 1;
+++i; // Skip Q_TRIANGULATE_END_OF_POLYGON.
+}
+for (i = 0; i < m_edges.size(); ++i) {
+m_edges.at(i).to = m_edges.at(m_edges.at(i).next).from;
+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);
+m_edges.at(i).helper = -1; // Not initialized here.
+}
+}
+void QTriangulator::SimpleToMonotone::removeZeroLengthEdges()
+{
+for (int i = 0; i < m_edges.size(); ++i) {
+if (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(i).to)) {
+m_edges.at(m_edges.at(i).previous).next = m_edges.at(i).next;
+m_edges.at(m_edges.at(i).next).previous = m_edges.at(i).previous;
+m_edges.at(m_edges.at(i).next).from = m_edges.at(i).from;
+m_edges.at(i).next = -1; // Mark as removed.
+}
+}
+QDataBuffer<int> newMapping(m_edges.size());
+newMapping.resize(m_edges.size());
+int count = 0;
+for (int i = 0; i < m_edges.size(); ++i) {
+if (m_edges.at(i).next != -1) {
+m_edges.at(count) = m_edges.at(i);
+newMapping.at(i) = count;
+++count;
+}
+}
+m_edges.resize(count);
+for (int i = 0; i < m_edges.size(); ++i) {
+m_edges.at(i).next = newMapping.at(m_edges.at(i).next);
+m_edges.at(i).previous = newMapping.at(m_edges.at(i).previous);
+}
+}
+void QTriangulator::SimpleToMonotone::fillPriorityQueue()
+{
+m_upperVertex.reset();
+m_upperVertex.reserve(m_edges.size());
+for (int i = 0; i < m_edges.size(); ++i)
+m_upperVertex.add(i);
+CompareVertices cmp(this);
+//qSort(m_upperVertex.data(), m_upperVertex.data() + m_upperVertex.size(), cmp);
+sort(m_upperVertex.data(), m_upperVertex.size(), cmp);
+//for (int i = 1; i < m_upperVertex.size(); ++i) {
+//    Q_ASSERT(!cmp(m_upperVertex.at(i), m_upperVertex.at(i - 1)));
+//}
+}
+bool QTriangulator::SimpleToMonotone::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const
+{
+const Edge &leftEdge = m_edges.at(leftEdgeIndex);
+const Edge &rightEdge = m_edges.at(rightEdgeIndex);
+const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
+const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
+qint64 d = qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.upper()), l, u);
+// d < 0: left, d > 0: right, d == 0: on top
+if (d == 0)
+d = qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.lower()), l, u);
+return d < 0;
+}
+// Returns the rightmost edge not to the right of the given edge.
+QRBTree<int>::Node *QTriangulator::SimpleToMonotone::searchEdgeLeftOfEdge(int edgeIndex) const
+{
+QRBTree<int>::Node *current = m_edgeList.root;
+QRBTree<int>::Node *result = 0;
+while (current) {
+if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
+current = current->left;
+} else {
+result = current;
+current = current->right;
+}
+}
+return result;
+}
+// Returns the rightmost edge left of the given point.
+QRBTree<int>::Node *QTriangulator::SimpleToMonotone::searchEdgeLeftOfPoint(int pointIndex) const
+{
+QRBTree<int>::Node *current = m_edgeList.root;
+QRBTree<int>::Node *result = 0;
+while (current) {
+const QPodPoint &p1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+const QPodPoint &p2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+qint64 d = qPointDistanceFromLine(m_parent->m_vertices.at(pointIndex), p1, p2);
+if (d <= 0) {
+current = current->left;
+} else {
+result = current;
+current = current->right;
+}
+}
+return result;
+}
+void QTriangulator::SimpleToMonotone::classifyVertex(int i)
+{
+Edge &e2 = m_edges.at(i);
+const Edge &e1 = m_edges.at(e2.previous);
+bool startOrSplit = (e1.pointingUp && !e2.pointingUp);
+bool endOrMerge = (!e1.pointingUp && e2.pointingUp);
+const QPodPoint &p1 = m_parent->m_vertices.at(e1.from);
+const QPodPoint &p2 = m_parent->m_vertices.at(e2.from);
+const QPodPoint &p3 = m_parent->m_vertices.at(e2.to);
+qint64 d = qPointDistanceFromLine(p1, p2, p3);
+Q_ASSERT(d != 0 || (!startOrSplit && !endOrMerge));
+e2.type = RegularVertex;
+if (m_clockwiseOrder) {
+if (startOrSplit)
+e2.type = (d < 0 ? SplitVertex : StartVertex);
+else if (endOrMerge)
+e2.type = (d < 0 ? MergeVertex : EndVertex);
+} else {
+if (startOrSplit)
+e2.type = (d > 0 ? SplitVertex : StartVertex);
+else if (endOrMerge)
+e2.type = (d > 0 ? MergeVertex : EndVertex);
+}
+}
+void QTriangulator::SimpleToMonotone::classifyVertices()
+{
+for (int i = 0; i < m_edges.size(); ++i)
+classifyVertex(i);
+}
+bool QTriangulator::SimpleToMonotone::pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3)
+{
+bool leftOfPreviousEdge = !qPointIsLeftOfLine(p, v2, v1);
+bool leftOfNextEdge = !qPointIsLeftOfLine(p, v3, v2);
+if (qPointIsLeftOfLine(v1, v2, v3))
+return leftOfPreviousEdge && leftOfNextEdge;
+else
+return leftOfPreviousEdge || leftOfNextEdge;
+}
+bool QTriangulator::SimpleToMonotone::pointIsInSector(int vertex, int sector)
+{
+const QPodPoint &center = m_parent->m_vertices.at(m_edges.at(sector).from);
+// Handle degenerate edges.
+while (m_parent->m_vertices.at(m_edges.at(vertex).from) == center)
+vertex = m_edges.at(vertex).next;
+int next = m_edges.at(sector).next;
+while (m_parent->m_vertices.at(m_edges.at(next).from) == center)
+next = m_edges.at(next).next;
+int previous = m_edges.at(sector).previous;
+while (m_parent->m_vertices.at(m_edges.at(previous).from) == center)
+previous = m_edges.at(previous).previous;
+const QPodPoint &p = m_parent->m_vertices.at(m_edges.at(vertex).from);
+const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(previous).from);
+const QPodPoint &v3 = m_parent->m_vertices.at(m_edges.at(next).from);
+if (m_clockwiseOrder)
+return pointIsInSector(p, v3, center, v1);
+else
+return pointIsInSector(p, v1, center, v3);
+}
+int QTriangulator::SimpleToMonotone::findSector(int edge, int vertex)
+{
+while (!pointIsInSector(vertex, edge)) {
+edge = m_edges.at(m_edges.at(edge).previous).twin;
+Q_ASSERT(edge != -1);
+}
+return edge;
+}
+void QTriangulator::SimpleToMonotone::createDiagonal(int lower, int upper)
+{
+lower = findSector(lower, upper);
+upper = findSector(upper, lower);
+int prevLower = m_edges.at(lower).previous;
+int prevUpper = m_edges.at(upper).previous;
+Edge e;
+e.twin = m_edges.size() + 1;
+e.next = upper;
+e.previous = prevLower;
+e.from = m_edges.at(lower).from;
+e.to = m_edges.at(upper).from;
+m_edges.at(upper).previous = m_edges.at(prevLower).next = int(m_edges.size());
+m_edges.add(e);
+e.twin = m_edges.size() - 1;
+e.next = lower;
+e.previous = prevUpper;
+e.from = m_edges.at(upper).from;
+e.to = m_edges.at(lower).from;
+m_edges.at(lower).previous = m_edges.at(prevUpper).next = int(m_edges.size());
+m_edges.add(e);
+}
+void QTriangulator::SimpleToMonotone::monotoneDecomposition()
+{
+if (m_edges.isEmpty())
+return;
+Q_ASSERT(!m_edgeList.root);
+QDataBuffer<QPair<int, int> > diagonals(m_upperVertex.size());
+int i = 0;
+for (int index = 1; index < m_edges.size(); ++index) {
+if (m_parent->m_vertices.at(m_edges.at(index).from) < m_parent->m_vertices.at(m_edges.at(i).from))
+i = index;
+}
+Q_ASSERT(i < m_edges.size());
+int j = m_edges.at(i).previous;
+Q_ASSERT(j < m_edges.size());
+m_clockwiseOrder = qPointIsLeftOfLine(m_parent->m_vertices.at(m_edges.at(i).from),
+m_parent->m_vertices.at(m_edges.at(j).from), m_parent->m_vertices.at(m_edges.at(i).to));
+classifyVertices();
+fillPriorityQueue();
+// debug: set helpers explicitly (shouldn't be necessary)
+//for (int i = 0; i < m_edges.size(); ++i)
+//    m_edges.at(i).helper = m_edges.at(i).upper();
+while (!m_upperVertex.isEmpty()) {
+i = m_upperVertex.last();
+Q_ASSERT(i < m_edges.size());
+m_upperVertex.pop_back();
+j = m_edges.at(i).previous;
+Q_ASSERT(j < m_edges.size());
+QRBTree<int>::Node *leftEdgeNode = 0;
+switch (m_edges.at(i).type) {
+case RegularVertex:
+// If polygon interior is to the right of the vertex...
+if (m_edges.at(i).pointingUp == m_clockwiseOrder) {
+if (m_edges.at(i).node) {
+Q_ASSERT(!m_edges.at(j).node);
+if (m_edges.at(m_edges.at(i).helper).type == MergeVertex)
+diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
+m_edges.at(j).node = m_edges.at(i).node;
+m_edges.at(i).node = 0;
+m_edges.at(j).node->data = j;
+m_edges.at(j).helper = i;
+} else if (m_edges.at(j).node) {
+Q_ASSERT(!m_edges.at(i).node);
+if (m_edges.at(m_edges.at(j).helper).type == MergeVertex)
+diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
+m_edges.at(i).node = m_edges.at(j).node;
+m_edges.at(j).node = 0;
+m_edges.at(i).node->data = i;
+m_edges.at(i).helper = i;
+} else {
+qWarning("Inconsistent polygon. (#1)");
+}
+} else {
+leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
+if (leftEdgeNode) {
+if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
+diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
+m_edges.at(leftEdgeNode->data).helper = i;
+} else {
+qWarning("Inconsistent polygon. (#2)");
+}
+}
+break;
+case SplitVertex:
+leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
+if (leftEdgeNode) {
+diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
+m_edges.at(leftEdgeNode->data).helper = i;
+} else {
+qWarning("Inconsistent polygon. (#3)");
+}
+// Fall through.
+case StartVertex:
+if (m_clockwiseOrder) {
+leftEdgeNode = searchEdgeLeftOfEdge(j);
+QRBTree<int>::Node *node = m_edgeList.newNode();
+node->data = j;
+m_edges.at(j).node = node;
+m_edges.at(j).helper = i;
+m_edgeList.attachAfter(leftEdgeNode, node);
+Q_ASSERT(m_edgeList.verify());
+} else  {
+leftEdgeNode = searchEdgeLeftOfEdge(i);
+QRBTree<int>::Node *node = m_edgeList.newNode();
+node->data = i;
+m_edges.at(i).node = node;
+m_edges.at(i).helper = i;
+m_edgeList.attachAfter(leftEdgeNode, node);
+Q_ASSERT(m_edgeList.verify());
+}
+break;
+case MergeVertex:
+leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
+if (leftEdgeNode) {
+if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
+diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
+m_edges.at(leftEdgeNode->data).helper = i;
+} else {
+qWarning("Inconsistent polygon. (#4)");
+}
+// Fall through.
+case EndVertex:
+if (m_clockwiseOrder) {
+if (m_edges.at(m_edges.at(i).helper).type == MergeVertex)
+diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
+if (m_edges.at(i).node) {
+m_edgeList.deleteNode(m_edges.at(i).node);
+Q_ASSERT(m_edgeList.verify());
+} else {
+qWarning("Inconsistent polygon. (#5)");
+}
+} else {
+if (m_edges.at(m_edges.at(j).helper).type == MergeVertex)
+diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
+if (m_edges.at(j).node) {
+m_edgeList.deleteNode(m_edges.at(j).node);
+Q_ASSERT(m_edgeList.verify());
+} else {
+qWarning("Inconsistent polygon. (#6)");
+}
+}
+break;
+}
+}
+for (int i = 0; i < diagonals.size(); ++i)
+createDiagonal(diagonals.at(i).first, diagonals.at(i).second);
+}
+bool QTriangulator::SimpleToMonotone::CompareVertices::operator () (int i, int j) const
+{
+if (m_parent->m_edges.at(i).from == m_parent->m_edges.at(j).from)
+return m_parent->m_edges.at(i).type > m_parent->m_edges.at(j).type;
+return m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from) >
+m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from);
+}
+//============================================================================//
+//                     QTriangulator::MonotoneToTriangles                     //
+//============================================================================//
+void QTriangulator::MonotoneToTriangles::decompose()
+{
+QVector<quint32> result;
+QDataBuffer<int> stack(m_parent->m_indices.size());
+m_first = 0;
+// Require at least three more indices.
+while (m_first + 3 <= m_parent->m_indices.size()) {
+m_length = 0;
+while (m_parent->m_indices.at(m_first + m_length) != Q_TRIANGULATE_END_OF_POLYGON) {
+++m_length;
+Q_ASSERT(m_first + m_length < m_parent->m_indices.size());
+}
+if (m_length < 3) {
+m_first += m_length + 1;
+continue;
+}
+int minimum = 0;
+while (less(next(minimum), minimum))
+minimum = next(minimum);
+while (less(previous(minimum), minimum))
+minimum = previous(minimum);
+stack.reset();
+stack.add(minimum);
+int left = previous(minimum);
+int right = next(minimum);
+bool stackIsOnLeftSide;
+bool clockwiseOrder = leftOfEdge(minimum, left, right);
+if (less(left, right)) {
+stack.add(left);
+left = previous(left);
+stackIsOnLeftSide = true;
+} else {
+stack.add(right);
+right = next(right);
+stackIsOnLeftSide = false;
+}
+for (int count = 0; count + 2 < m_length; ++count)
+{
+Q_ASSERT(stack.size() >= 2);
+if (less(left, right)) {
+if (stackIsOnLeftSide == false) {
+for (int i = 0; i + 1 < stack.size(); ++i) {
+result.push_back(indices(stack.at(i + 1)));
+result.push_back(indices(left));
+result.push_back(indices(stack.at(i)));
+}
+stack.first() = stack.last();
+stack.resize(1);
+} else {
+while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(left, stack.at(stack.size() - 2), stack.last()))) {
+result.push_back(indices(stack.at(stack.size() - 2)));
+result.push_back(indices(left));
+result.push_back(indices(stack.last()));
+stack.pop_back();
+}
+}
+stack.add(left);
+left = previous(left);
+stackIsOnLeftSide = true;
+} else {
+if (stackIsOnLeftSide == true) {
+for (int i = 0; i + 1 < stack.size(); ++i) {
+result.push_back(indices(stack.at(i)));
+result.push_back(indices(right));
+result.push_back(indices(stack.at(i + 1)));
+}
+stack.first() = stack.last();
+stack.resize(1);
+} else {
+while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(right, stack.last(), stack.at(stack.size() - 2)))) {
+result.push_back(indices(stack.last()));
+result.push_back(indices(right));
+result.push_back(indices(stack.at(stack.size() - 2)));
+stack.pop_back();
+}
+}
+stack.add(right);
+right = next(right);
+stackIsOnLeftSide = false;
+}
+}
+m_first += m_length + 1;
+}
+m_parent->m_indices = result;
+}
+//============================================================================//
+//                                qTriangulate                                //
+//============================================================================//
+QTriangleSet qTriangulate(const qreal *polygon, int count, uint hint, const QTransform &matrix)
+{
+QTriangulator triangulator;
+triangulator.initialize(polygon, count, hint, matrix);
+return triangulator.triangulate();
+}
+QTriangleSet qTriangulate(const QVectorPath &path, const QTransform &matrix, qreal lod)
+{
+QTriangulator triangulator;
+triangulator.initialize(path, matrix, lod);
+return triangulator.triangulate();
+}
+QTriangleSet qTriangulate(const QPainterPath &path, const QTransform &matrix, qreal lod)
+{
+QTriangulator triangulator;
+triangulator.initialize(path, matrix, lod);
+return triangulator.triangulate();
+}
+QPolylineSet qPolyline(const QVectorPath &path, const QTransform &matrix, qreal lod)
+{
+QTriangulator triangulator;
+triangulator.initialize(path, matrix, lod);
+return triangulator.polyline();
+}
+QPolylineSet qPolyline(const QPainterPath &path, const QTransform &matrix, qreal lod)
+{
+QTriangulator triangulator;
+triangulator.initialize(path, matrix, lod);
+return triangulator.polyline();
+}
+QT_END_NAMESPACE

changeset 30	5dc02b23752f
child 37	758a864f9613