Qt 4.8
qbsptree_p.h
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtGui module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 
42 #ifndef QBSPTREE_P_H
43 #define QBSPTREE_P_H
44 
45 //
46 // W A R N I N G
47 // -------------
48 //
49 // This file is not part of the Qt API. It exists for the convenience
50 // of other Qt classes. This header file may change from version to
51 // version without notice, or even be removed.
52 //
53 // We mean it.
54 //
55 
56 #include <qvector.h>
57 #include <qrect.h>
58 
60 
61 class QBspTree
62 {
63 public:
64 
65  struct Node
66  {
67  enum Type { None = 0, VerticalPlane = 1, HorizontalPlane = 2, Both = 3 };
68  inline Node() : pos(0), type(None) {}
69  int pos;
71  };
73 
74  struct Data
75  {
76  Data(void *p) : ptr(p) {}
77  Data(int n) : i(n) {}
78  union {
79  void *ptr;
80  int i;
81  };
82  };
84  typedef void callback(QVector<int> &leaf, const QRect &area, uint visited, QBspTreeData data);
85 
86  QBspTree();
87 
88  void create(int n, int d = -1);
89  void destroy();
90 
91  inline void init(const QRect &area, NodeType type) { init(area, depth, type, 0); }
92 
93  void climbTree(const QRect &rect, callback *function, QBspTreeData data);
94 
95  inline int leafCount() const { return leaves.count(); }
96  inline QVector<int> &leaf(int i) { return leaves[i]; }
97  inline void insertLeaf(const QRect &r, int i) { climbTree(r, &insert, i, 0); }
98  inline void removeLeaf(const QRect &r, int i) { climbTree(r, &remove, i, 0); }
99 
100 protected:
101  void init(const QRect &area, int depth, NodeType type, int index);
102  void climbTree(const QRect &rect, callback *function, QBspTreeData data, int index);
103 
104  inline int parentIndex(int i) const { return (i & 1) ? ((i - 1) / 2) : ((i - 2) / 2); }
105  inline int firstChildIndex(int i) const { return ((i * 2) + 1); }
106 
107  static void insert(QVector<int> &leaf, const QRect &area, uint visited, QBspTreeData data);
108  static void remove(QVector<int> &leaf, const QRect &area, uint visited, QBspTreeData data);
109 
110 private:
112  mutable uint visited;
114  mutable QVector< QVector<int> > leaves; // the leaves are just indices into the items
115 };
116 
118 
119 #endif // QBSPTREE_P_H
void insertLeaf(const QRect &r, int i)
Definition: qbsptree_p.h:97
double d
Definition: qnumeric_p.h:62
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
QVector< int > & leaf(int i)
Definition: qbsptree_p.h:96
int count(const T &t) const
Returns the number of occurrences of value in the vector.
Definition: qvector.h:742
void init(const QRect &area, NodeType type)
Definition: qbsptree_p.h:91
QVector< QVector< int > > leaves
Definition: qbsptree_p.h:114
int firstChildIndex(int i) const
Definition: qbsptree_p.h:105
QBspTree()
Definition: qbsptree.cpp:46
Node::Type NodeType
Definition: qbsptree_p.h:72
void callback(QVector< int > &leaf, const QRect &area, uint visited, QBspTreeData data)
Definition: qbsptree_p.h:84
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
uint depth
Definition: qbsptree_p.h:111
static const char * data(const QByteArray &arr)
unsigned int uint
Definition: qglobal.h:996
static void insert(QVector< int > &leaf, const QRect &area, uint visited, QBspTreeData data)
Definition: qbsptree.cpp:133
const T * ptr(const T &t)
void climbTree(const QRect &rect, callback *function, QBspTreeData data)
Definition: qbsptree.cpp:71
void destroy()
Definition: qbsptree.cpp:65
QVector< Node > nodes
Definition: qbsptree_p.h:113
uint visited
Definition: qbsptree_p.h:112
int leafCount() const
Definition: qbsptree_p.h:95
Data(void *p)
Definition: qbsptree_p.h:76
The QRect class defines a rectangle in the plane using integer precision.
Definition: qrect.h:58
quint16 index
QBspTree::Data QBspTreeData
Definition: qbsptree_p.h:83
int parentIndex(int i) const
Definition: qbsptree_p.h:104
void removeLeaf(const QRect &r, int i)
Definition: qbsptree_p.h:98
static int area(const QSize &s)
Definition: qicon.cpp:155
void create(int n, int d=-1)
Definition: qbsptree.cpp:48