/****************************************************************************
**
** Copyright (C) 2011 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$
** GNU Lesser General Public License Usage
** 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.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU General
** Public License version 3.0 as published by the Free Software Foundation
** and appearing in the file LICENSE.GPL included in the packaging of this
** file. Please review the following information to ensure the GNU General
** Public License version 3.0 requirements will be met:
** http://www.gnu.org/copyleft/gpl.html.
**
** Other Usage
** Alternatively, this file may be used in accordance with the terms and
** conditions contained in a signed written agreement between you and Nokia.
**
**
**
**
**
** $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>

#include <private/qgl_p.h>

QT_BEGIN_NAMESPACE

//#define Q_TRIANGULATOR_DEBUG

#define Q_FIXED_POINT_SCALE 32

// Quick sort.
template <class T, class LessThan>
#ifdef Q_CC_RVCT // RVCT 2.2 doesn't see recursive _static_ template function
void sort(T *array, int count, LessThan lessThan)
#else
static void sort(T *array, int count, LessThan lessThan)
#endif
{
    // 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>
#ifdef Q_CC_RVCT
void sort(T *array, int count) // RVCT 2.2 doesn't see recursive _static_ template function
#else
static void sort(T *array, int count)
#endif
{
    // 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);
}

template<typename T>
struct QVertexSet
{
    inline QVertexSet() { }
    inline QVertexSet(const QVertexSet<T> &other) : vertices(other.vertices), indices(other.indices) { }
    QVertexSet<T> &operator = (const QVertexSet<T> &other) {vertices = other.vertices; indices = other.indices; return *this;}

    // 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, ...
    QVector<qreal> vertices; // [x[0], y[0], x[1], y[1], x[2], ...]
    QVector<T> indices; // [i[0], j[0], k[0], i[1], j[1], k[1], i[2], ...]
};

//============================================================================//
//                                 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 QT_PREPEND_NAMESPACE(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 validate() 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>::validate() 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                                //
//============================================================================//

typedef QRBTree<int>::Node *QRBTreeIntNodePointer;

template<typename T>
class QTriangulator
{
public:
    typedef QVarLengthArray<int, 6> ShortArray;

    //================================//
    // QTriangulator::ComplexToSimple //
    //================================//
    friend class ComplexToSimple;
    class ComplexToSimple
    {
    public:
        inline ComplexToSimple(QTriangulator<T> *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<T> *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;
            T 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<T> *parent) : m_parent(parent) { }
        void decompose();
    private:
        inline T 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((qint32)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((qint32)indices(i)),
                m_parent->m_vertices.at((qint32)indices(j)), m_parent->m_vertices.at((qint32)indices(k)));
        }

        QTriangulator<T> *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.
    QVertexSet<T> triangulate();
    QVertexSet<T> polyline();
private:
    QDataBuffer<QPodPoint> m_vertices;
    QVector<T> m_indices;
    uint m_hint;
};

//============================================================================//
//                               QTriangulator                                //
//============================================================================//

template <typename T>
QVertexSet<T> QTriangulator<T>::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();

    QVertexSet<T> 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;
}

template <typename T>
QVertexSet<T> QTriangulator<T>::polyline()
{
    QVertexSet<T> 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;
}

template <typename T>
void QTriangulator<T>::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] = T(-1); //Q_TRIANGULATE_END_OF_POLYGON
}

template <typename T>
void QTriangulator<T>::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(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
                // Fall through.
            case QPainterPath::LineToElement:
                m_indices.push_back(T(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(T(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(T(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(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
}

template <typename T>
void QTriangulator<T>::initialize(const QPainterPath &path, const QTransform &matrix, qreal lod)
{
    initialize(qtVectorPathForPath(path), matrix, lod);
}

//============================================================================//
//                       QTriangulator::ComplexToSimple                       //
//============================================================================//
template <typename T>
void QTriangulator<T>::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(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
    }
}

template <typename T>
void QTriangulator<T>::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) == T(-1)) { // 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
template <typename T>
bool QTriangulator<T>::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((qint32)e1.from);
    const QPodPoint &u2 = m_parent->m_vertices.at((qint32)e1.to);
    const QPodPoint &v1 = m_parent->m_vertices.at((qint32)e2.from);
    const QPodPoint &v2 = m_parent->m_vertices.at((qint32)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 = QT_PREPEND_NAMESPACE(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;
}

template <typename T>
bool QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(upper, l, u);
    // d < 0: left, d > 0: right, d == 0: on top
    if (d == 0)
        d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(leftEdge.lower()), l, u);
    return d < 0;
}

template <typename T>
QRBTreeIntNodePointer QTriangulator<T>::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;
}

template <typename T>
QRBTreeIntNodePointer QTriangulator<T>::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;
}

template <typename T>
QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(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 = QT_PREPEND_NAMESPACE(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 = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(point, v1, v2);
        Q_ASSERT(d <= 0);
        if (d == 0) {
            result.second = current;
            current = current->right;
        } else {
            current = current->left;
        }
    }

    return result;
}

template <typename T>
QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(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 = QT_PREPEND_NAMESPACE(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 = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(point, v1, v2);
        Q_ASSERT(d <= 0);
        if (d == 0) {
            current = current->right;
        } else {
            result.second = current;
            current = current->left;
        }
    }

    return result;
}

template <typename T>
void QTriangulator<T>::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);
    }
}

template <typename T>
void QTriangulator<T>::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);
}

template <typename T>
void QTriangulator<T>::ComplexToSimple::sortEdgeList(const QPodPoint eventPoint)
{
    QIntersectionPoint eventPoint2 = QT_PREPEND_NAMESPACE(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((qint32)edge.from);
            const QPodPoint &v = m_parent->m_vertices.at((qint32)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((qint32)edge.from);
            const QPodPoint &v = m_parent->m_vertices.at((qint32)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

    }
}

template <typename T>
void QTriangulator<T>::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());
}

template <typename T>
void QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(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'.
template <typename T>
int QTriangulator<T>::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;
    }
}

template <typename T>
bool QTriangulator<T>::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;
}

template <typename T>
void QTriangulator<T>::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);
}

template <typename T>
void QTriangulator<T>::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(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)));
                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
}

template <typename T>
void QTriangulator<T>::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);
    }
}

template <typename T>
bool QTriangulator<T>::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;
}

template <typename T>
inline bool QTriangulator<T>::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
template <typename T>
QTriangulator<T>::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));
}

template <typename T>
void QTriangulator<T>::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);        
    }
}

template <typename T>
void QTriangulator<T>::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();
}

template <typename T>
void QTriangulator<T>::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();
    }
}

template <typename T>
void QTriangulator<T>::ComplexToSimple::DebugDialog::mousePressEvent(QMouseEvent *event)
{
    if (event->button() == Qt::LeftButton)
        m_lastMousePos = event->pos();
    event->accept();
}


#endif

//============================================================================//
//                      QTriangulator::SimpleToMonotone                       //
//============================================================================//
template <typename T>
void QTriangulator<T>::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() != T(-1)) // Q_TRIANGULATE_END_OF_POLYGON
            m_parent->m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
    }
}

template <typename T>
void QTriangulator<T>::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) != T(-1)); // 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.
    }
}

template <typename T>
void QTriangulator<T>::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);
    }
}

template <typename T>
void QTriangulator<T>::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)));
    //}
}

template <typename T>
bool QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(leftEdge.upper()), l, u);
    // d < 0: left, d > 0: right, d == 0: on top
    if (d == 0)
        d = QT_PREPEND_NAMESPACE(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.
template <typename T>
QRBTree<int>::Node *QTriangulator<T>::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.
template <typename T>
QRBTree<int>::Node *QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(pointIndex), p1, p2);
        if (d <= 0) {
            current = current->left;
        } else {
            result = current;
            current = current->right;
        }
    }
    return result;
}

template <typename T>
void QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(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);
    }
}

template <typename T>
void QTriangulator<T>::SimpleToMonotone::classifyVertices()
{
    for (int i = 0; i < m_edges.size(); ++i)
        classifyVertex(i);
}

template <typename T>
bool QTriangulator<T>::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;
}

template <typename T>
bool QTriangulator<T>::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);
}

template <typename T>
int QTriangulator<T>::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;
}

template <typename T>
void QTriangulator<T>::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);
}

template <typename T>
void QTriangulator<T>::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((quint32)m_edges.at(i).from),
        m_parent->m_vertices.at((quint32)m_edges.at(j).from), m_parent->m_vertices.at((quint32)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.validate());
            } 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.validate());
            }
            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.validate());
                } 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.validate());
                } else {
                    qWarning("Inconsistent polygon. (#6)");
                }
            }
            break;
        }
    }

    for (int i = 0; i < diagonals.size(); ++i)
        createDiagonal(diagonals.at(i).first, diagonals.at(i).second);
}

template <typename T>
bool QTriangulator<T>::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                     //
//============================================================================//
template <typename T>
void QTriangulator<T>::MonotoneToTriangles::decompose()
{
    QVector<T> 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) != T(-1)) { // 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)
{
    QTriangleSet triangleSet;
    if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
        QTriangulator<quint32> triangulator;
        triangulator.initialize(polygon, count, hint, matrix);
        QVertexSet<quint32> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUint(vertexSet.indices);

    } else {
        QTriangulator<quint16> triangulator;
        triangulator.initialize(polygon, count, hint, matrix);
        QVertexSet<quint16> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUshort(vertexSet.indices);
    }
    return triangleSet;
}

QTriangleSet qTriangulate(const QVectorPath &path,
                          const QTransform &matrix, qreal lod)
{
    QTriangleSet triangleSet;
    if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
        QTriangulator<quint32> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint32> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUint(vertexSet.indices);
    } else {
        QTriangulator<quint16> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint16> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUshort(vertexSet.indices);
    }
    return triangleSet;
}

QTriangleSet qTriangulate(const QPainterPath &path,
                          const QTransform &matrix, qreal lod)
{
    QTriangleSet triangleSet;
    if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
        QTriangulator<quint32> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint32> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUint(vertexSet.indices);
    } else {
        QTriangulator<quint16> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint16> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUshort(vertexSet.indices);
    }
    return triangleSet;
}

QPolylineSet qPolyline(const QVectorPath &path,
                       const QTransform &matrix, qreal lod)
{
    QPolylineSet polyLineSet;
    if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
        QTriangulator<quint32> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint32> vertexSet = triangulator.polyline();
        polyLineSet.vertices = vertexSet.vertices;
        polyLineSet.indices.setDataUint(vertexSet.indices);
    } else {
        QTriangulator<quint16> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint16> vertexSet = triangulator.triangulate();
        polyLineSet.vertices = vertexSet.vertices;
        polyLineSet.indices.setDataUshort(vertexSet.indices);
    }
    return polyLineSet;
}

QPolylineSet qPolyline(const QPainterPath &path,
                       const QTransform &matrix, qreal lod)
{
    QPolylineSet polyLineSet;
    if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
        QTriangulator<quint32> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint32> vertexSet = triangulator.polyline();
        polyLineSet.vertices = vertexSet.vertices;
        polyLineSet.indices.setDataUint(vertexSet.indices);
    } else {
        QTriangulator<quint16> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint16> vertexSet = triangulator.triangulate();
        polyLineSet.vertices = vertexSet.vertices;
        polyLineSet.indices.setDataUshort(vertexSet.indices);
    }
    return polyLineSet;
}

QT_END_NAMESPACE