QTriangulator< T >::SimpleToMonotone Class Reference

Classes
class	CompareVertices
struct	Edge

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

Private Types
enum	VertexType {   MergeVertex, EndVertex, RegularVertex, StartVertex,   SplitVertex }

Private Functions
void	classifyVertex (int i)
void	classifyVertices ()
void	createDiagonal (int lower, int upper)
bool	edgeIsLeftOfEdge (int leftEdgeIndex, int rightEdgeIndex) const
void	fillPriorityQueue ()
int	findSector (int edge, int vertex)
void	monotoneDecomposition ()
bool	pointIsInSector (const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3)
bool	pointIsInSector (int vertex, int sector)
void	removeZeroLengthEdges ()
QRBTree< int >::Node *	searchEdgeLeftOfEdge (int edgeIndex) const
QRBTree< int >::Node *	searchEdgeLeftOfPoint (int pointIndex) const
void	setupDataStructures ()

Properties
bool	m_clockwiseOrder
QRBTree< int >	m_edgeList
QDataBuffer< Edge >	m_edges
QTriangulator *	m_parent
QDataBuffer< int >	m_upperVertex

Friends
class	CompareVertices

Detailed Description

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

Definition at line 1439 of file qtriangulator.cpp.

Enumerations

VertexType

template<typename T>

enum QTriangulator::SimpleToMonotone::VertexType

private

Enumerator
MergeVertex
EndVertex
RegularVertex
StartVertex
SplitVertex

Definition at line 1445 of file qtriangulator.cpp.

{MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex};

Constructors and Destructors

SimpleToMonotone()

template<typename T>

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

inline

Definition at line 1442 of file qtriangulator.cpp.

: m_parent(parent), m_edges(0), m_upperVertex(0) { }

Functions

classifyVertex()

template<typename T >

void QTriangulator< T >::SimpleToMonotone::classifyVertex ( int  i )

private

Definition at line 2663 of file qtriangulator.cpp.

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

classifyVertices()

template<typename T >

void QTriangulator< T >::SimpleToMonotone::classifyVertices ( )

private

Definition at line 2693 of file qtriangulator.cpp.

{
    for (int i = 0; i < m_edges.size(); ++i)
        classifyVertex(i);
}

createDiagonal()

template<typename T >

void QTriangulator< T >::SimpleToMonotone::createDiagonal ( int  lower, int  upper  )

private

Definition at line 2745 of file qtriangulator.cpp.

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

decompose()

template<typename T >

void QTriangulator< T >::SimpleToMonotone::decompose

(

)

Definition at line 2510 of file qtriangulator.cpp.

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

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

edgeIsLeftOfEdge()

template<typename T >

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

private

Definition at line 2612 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());
    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;
}

fillPriorityQueue()

template<typename T >

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

private

Definition at line 2597 of file qtriangulator.cpp.

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

findSector()

template<typename T >

int QTriangulator< T >::SimpleToMonotone::findSector ( int  edge, int  vertex  )

private

Definition at line 2735 of file qtriangulator.cpp.

{
    while (!pointIsInSector(vertex, edge)) {
        edge = m_edges.at(m_edges.at(edge).previous).twin;
        Q_ASSERT(edge != -1);
    }
    return edge;
}

monotoneDecomposition()

template<typename T >

void QTriangulator< T >::SimpleToMonotone::monotoneDecomposition ( )

private

Definition at line 2773 of file qtriangulator.cpp.

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

pointIsInSector() [1/2]

template<typename T >

bool QTriangulator< T >::SimpleToMonotone::pointIsInSector ( const QPodPoint &  p, const QPodPoint &  v1, const QPodPoint &  v2, const QPodPoint &  v3  )

private

Definition at line 2700 of file qtriangulator.cpp.

{
    bool leftOfPreviousEdge = !qPointIsLeftOfLine(p, v2, v1);
    bool leftOfNextEdge = !qPointIsLeftOfLine(p, v3, v2);

    if (qPointIsLeftOfLine(v1, v2, v3))
        return leftOfPreviousEdge && leftOfNextEdge;
    else
        return leftOfPreviousEdge || leftOfNextEdge;
}

pointIsInSector() [2/2]

template<typename T >

bool QTriangulator< T >::SimpleToMonotone::pointIsInSector ( int  vertex, int  sector  )

private

Definition at line 2712 of file qtriangulator.cpp.

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

removeZeroLengthEdges()

template<typename T >

void QTriangulator< T >::SimpleToMonotone::removeZeroLengthEdges ( )

private

Definition at line 2568 of file qtriangulator.cpp.

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

searchEdgeLeftOfEdge()

template<typename T >

QRBTree< int >::Node * QTriangulator< T >::SimpleToMonotone::searchEdgeLeftOfEdge ( int  edgeIndex ) const

private

Definition at line 2627 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;
}

searchEdgeLeftOfPoint()

template<typename T >

QRBTree< int >::Node * QTriangulator< T >::SimpleToMonotone::searchEdgeLeftOfPoint ( int  pointIndex ) const

private

Definition at line 2644 of file qtriangulator.cpp.

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

setupDataStructures()

template<typename T >

void QTriangulator< T >::SimpleToMonotone::setupDataStructures ( )

private

Definition at line 2535 of file qtriangulator.cpp.

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

Friends and Related Functions

CompareVertices

template<typename T>

friend class CompareVertices

friend

Definition at line 1458 of file qtriangulator.cpp.

Properties

m_clockwiseOrder

template<typename T>

bool QTriangulator< T >::SimpleToMonotone::m_clockwiseOrder

private

Definition at line 1488 of file qtriangulator.cpp.

m_edgeList

template<typename T>

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

private

Definition at line 1485 of file qtriangulator.cpp.

m_edges

template<typename T>

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

private

Definition at line 1486 of file qtriangulator.cpp.

m_parent

template<typename T>

QTriangulator* QTriangulator< T >::SimpleToMonotone::m_parent

private

Definition at line 1484 of file qtriangulator.cpp.

m_upperVertex

template<typename T>

QDataBuffer<int> QTriangulator< T >::SimpleToMonotone::m_upperVertex

private

Definition at line 1487 of file qtriangulator.cpp.

---

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

• /src/opengl/gl2paintengineex/qtriangulator.cpp