QTriangulator< T >::ComplexToSimple Class Reference

Classes
class	CompareEdges
struct	Edge
struct	Event
struct	Intersection
struct	Split

Public Functions
	ComplexToSimple (QTriangulator< T > *parent)
void	decompose ()

Private Functions
QPair< QRBTree< int >::Node *, QRBTree< int >::Node * >	bounds (const QPodPoint &point) const
bool	calculateIntersection (int left, int right)
void	calculateIntersections ()
bool	edgeIsLeftOfEdge (int leftEdgeIndex, int rightEdgeIndex) const
void	fillPriorityQueue ()
void	initEdges ()
void	insertEdgeIntoVectorIfWanted (ShortArray &orderedEdges, int i)
QPair< QRBTree< int >::Node *, QRBTree< int >::Node * >	outerBounds (const QPodPoint &point) const
void	removeUnusedPoints ()
void	removeUnwantedEdgesAndConnect ()
void	reorderEdgeListRange (QRBTree< int >::Node *leftmost, QRBTree< int >::Node *rightmost)
QRBTree< int >::Node *	searchEdgeLeftOf (int edgeIndex) const
QRBTree< int >::Node *	searchEdgeLeftOf (int edgeIndex, QRBTree< int >::Node *after) const
void	sortEdgeList (const QPodPoint eventPoint)
int	splitEdge (int splitIndex)
void	splitEdgeListRange (QRBTree< int >::Node *leftmost, QRBTree< int >::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint)
bool	splitEdgesAtIntersections ()

Properties
QRBTree< int >	m_edgeList
QDataBuffer< Edge >	m_edges
QDataBuffer< Event >	m_events
int	m_initialPointCount
QTriangulator *	m_parent
QInt64Set	m_processedEdgePairs
QDataBuffer< Split >	m_splits
QMaxHeap< Intersection >	m_topIntersection

Friends
class	CompareEdges

Detailed Description

template<typename T>
class QTriangulator< T >::ComplexToSimple

Definition at line 1325 of file qtriangulator.cpp.

Constructors and Destructors

ComplexToSimple()

template<typename T>

QTriangulator< T >::ComplexToSimple::ComplexToSimple ( QTriangulator< T > *  parent )

inline

Definition at line 1328 of file qtriangulator.cpp.

                                                         : m_parent(parent),
            m_edges(0), m_events(0), m_splits(0) { }

Functions

bounds()

template<typename T >

QPair< QRBTree< int >::Node *, QRBTree< int >::Node * > QTriangulator< T >::ComplexToSimple::bounds ( const QPodPoint &  point ) const

private

Definition at line 1813 of file qtriangulator.cpp.

{
    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;
}

calculateIntersection()

template<typename T >

bool QTriangulator< T >::ComplexToSimple::calculateIntersection ( int  left, int  right  )

private

Definition at line 1727 of file qtriangulator.cpp.

{
    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;
}

calculateIntersections()

template<typename T >

void QTriangulator< T >::ComplexToSimple::calculateIntersections ( )

private

Definition at line 2046 of file qtriangulator.cpp.

{
    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();
}

decompose()

template<typename T >

void QTriangulator< T >::ComplexToSimple::decompose

(

)

Definition at line 1669 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::triangulate().

{
    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
    }
}

edgeIsLeftOfEdge()

template<typename T >

bool QTriangulator< T >::ComplexToSimple::edgeIsLeftOfEdge ( int  leftEdgeIndex, int  rightEdgeIndex  ) const

private

Definition at line 1762 of file qtriangulator.cpp.

{
    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;
}

fillPriorityQueue()

template<typename T >

void QTriangulator< T >::ComplexToSimple::fillPriorityQueue ( )

private

Definition at line 2022 of file qtriangulator.cpp.

{
    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());
}

initEdges()

template<typename T >

void QTriangulator< T >::ComplexToSimple::initEdges ( )

private

Definition at line 1700 of file qtriangulator.cpp.

{
    // 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, int(m_parent->m_indices.at(i)), int(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);
    }
}

insertEdgeIntoVectorIfWanted()

template<typename T >

void QTriangulator< T >::ComplexToSimple::insertEdgeIntoVectorIfWanted ( ShortArray &  orderedEdges, int  i  )

private

Definition at line 2161 of file qtriangulator.cpp.

{
    // 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);
}

outerBounds()

template<typename T >

QPair< QRBTree< int >::Node *, QRBTree< int >::Node * > QTriangulator< T >::ComplexToSimple::outerBounds ( const QPodPoint &  point ) const

private

Definition at line 1862 of file qtriangulator.cpp.

{
    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;
}

removeUnusedPoints()

template<typename T >

void QTriangulator< T >::ComplexToSimple::removeUnusedPoints ( )

private

Definition at line 2331 of file qtriangulator.cpp.

                                                         {
    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);
    }
}

removeUnwantedEdgesAndConnect()

template<typename T >

void QTriangulator< T >::ComplexToSimple::removeUnwantedEdgesAndConnect ( )

private

Definition at line 2192 of file qtriangulator.cpp.

{
    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
}

reorderEdgeListRange()

template<typename T >

void QTriangulator< T >::ComplexToSimple::reorderEdgeListRange ( QRBTree< int >::Node *  leftmost, QRBTree< int >::Node *  rightmost  )

private

Definition at line 1938 of file qtriangulator.cpp.

{
    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);
}

searchEdgeLeftOf() [1/2]

template<typename T >

QRBTreeIntNodePointer QTriangulator< T >::ComplexToSimple::searchEdgeLeftOf ( int  edgeIndex ) const

private

Definition at line 1781 of file qtriangulator.cpp.

{
    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;
}

searchEdgeLeftOf() [2/2]

template<typename T >

QRBTreeIntNodePointer QTriangulator< T >::ComplexToSimple::searchEdgeLeftOf ( int  edgeIndex, QRBTree< int >::Node *  after  ) const

private

Definition at line 1797 of file qtriangulator.cpp.

{
    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;
}

sortEdgeList()

template<typename T >

void QTriangulator< T >::ComplexToSimple::sortEdgeList ( const QPodPoint  eventPoint )

private

Definition at line 1966 of file qtriangulator.cpp.

{
    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

    }
}

splitEdge()

template<typename T >

int QTriangulator< T >::ComplexToSimple::splitEdge ( int  splitIndex )

private

Definition at line 2112 of file qtriangulator.cpp.

{
    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;
    }
}

splitEdgeListRange()

template<typename T >

void QTriangulator< T >::ComplexToSimple::splitEdgeListRange ( QRBTree< int >::Node *  leftmost, QRBTree< int >::Node *  rightmost, int  vertex, const QIntersectionPoint &  intersectionPoint  )

private

Definition at line 1919 of file qtriangulator.cpp.

{
    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);
    }
}

splitEdgesAtIntersections()

template<typename T >

bool QTriangulator< T >::ComplexToSimple::splitEdgesAtIntersections ( )

private

Definition at line 2143 of file qtriangulator.cpp.

{
    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;
}

Friends and Related Functions

CompareEdges

template<typename T>

friend class CompareEdges

friend

Definition at line 1347 of file qtriangulator.cpp.

Properties

m_edgeList

template<typename T>

QRBTree<int> QTriangulator< T >::ComplexToSimple::m_edgeList

private

Definition at line 1424 of file qtriangulator.cpp.

m_edges

template<typename T>

QDataBuffer<Edge> QTriangulator< T >::ComplexToSimple::m_edges

private

Definition at line 1423 of file qtriangulator.cpp.

m_events

template<typename T>

QDataBuffer<Event> QTriangulator< T >::ComplexToSimple::m_events

private

Definition at line 1425 of file qtriangulator.cpp.

m_initialPointCount

template<typename T>

int QTriangulator< T >::ComplexToSimple::m_initialPointCount

private

Definition at line 1429 of file qtriangulator.cpp.

m_parent

template<typename T>

QTriangulator* QTriangulator< T >::ComplexToSimple::m_parent

private

Definition at line 1422 of file qtriangulator.cpp.

m_processedEdgePairs

template<typename T>

QInt64Set QTriangulator< T >::ComplexToSimple::m_processedEdgePairs

private

Definition at line 1428 of file qtriangulator.cpp.

m_splits

template<typename T>

QDataBuffer<Split> QTriangulator< T >::ComplexToSimple::m_splits

private

Definition at line 1426 of file qtriangulator.cpp.

m_topIntersection

template<typename T>

QMaxHeap<Intersection> QTriangulator< T >::ComplexToSimple::m_topIntersection

private

Definition at line 1427 of file qtriangulator.cpp.

---

The documentation for this class was generated from the following file:

• /src/opengl/gl2paintengineex/qtriangulator.cpp