QKdPointTree Class Reference

Classes
struct	Node

Public Types
enum	Traversal { TraverseBoth, TraverseLeft, TraverseRight, TraverseNone }

Public Functions
int	build (int begin, int end, int depth=0)
int	nextId ()
	QKdPointTree (const QPathSegments &segments)
Node *	rootNode ()

Properties
int	m_id
QDataBuffer< Node >	m_nodes
int	m_rootNode
const QPathSegments *	m_segments

Detailed Description

Definition at line 602 of file qpathclipper.cpp.

Enumerations

Traversal

enum QKdPointTree::Traversal

Enumerator
TraverseBoth
TraverseLeft
TraverseRight
TraverseNone

Definition at line 605 of file qpathclipper.cpp.

                   {
        TraverseBoth,
        TraverseLeft,
        TraverseRight,
        TraverseNone
    };

Constructors and Destructors

QKdPointTree()

QKdPointTree::QKdPointTree ( const QPathSegments &  segments )

inline

Definition at line 620 of file qpathclipper.cpp.

        : m_segments(&segments)
        , m_nodes(m_segments->points())
        , m_id(0)
    {
        m_nodes.resize(m_segments->points());

        for (int i = 0; i < m_nodes.size(); ++i) {
            m_nodes.at(i).point = i;
            m_nodes.at(i).id = -1;
        }

        m_rootNode = build(0, m_nodes.size());
    }

Functions

build()

int QKdPointTree::build	(	int	begin,
		int	end,
		int	depth = 0
	)

Definition at line 677 of file qpathclipper.cpp.

{
    Q_ASSERT(end > begin);

    const qreal pivot = component(m_segments->pointAt(m_nodes.at(begin).point), depth & 1);

    int first = begin + 1;
    int last = end - 1;

    while (first <= last) {
        const qreal value = component(m_segments->pointAt(m_nodes.at(first).point), depth & 1);

        if (value < pivot)
            ++first;
        else {
            qSwap(m_nodes.at(first), m_nodes.at(last));
            --last;
        }
    }

    qSwap(m_nodes.at(last), m_nodes.at(begin));

    if (last > begin)
        m_nodes.at(last).left = &m_nodes.at(build(begin, last, depth + 1));
    else
        m_nodes.at(last).left = 0;

    if (last + 1 < end)
        m_nodes.at(last).right = &m_nodes.at(build(last + 1, end, depth + 1));
    else
        m_nodes.at(last).right = 0;

    return last;
}

nextId()

int QKdPointTree::nextId ( )

inline

Definition at line 642 of file qpathclipper.cpp.

    {
        return m_id++;
    }

rootNode()

Node* QKdPointTree::rootNode ( )

inline

Definition at line 637 of file qpathclipper.cpp.

Referenced by QPathSegments::mergePoints().

    {
        return &m_nodes.at(m_rootNode);
    }

Properties

m_id

int QKdPointTree::m_id

private

Definition at line 652 of file qpathclipper.cpp.

m_nodes

QDataBuffer<Node> QKdPointTree::m_nodes

private

Definition at line 649 of file qpathclipper.cpp.

m_rootNode

int QKdPointTree::m_rootNode

private

Definition at line 651 of file qpathclipper.cpp.

m_segments

const QPathSegments* QKdPointTree::m_segments

private

Definition at line 648 of file qpathclipper.cpp.

---

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

• /src/gui/painting/qpathclipper.cpp