Qt 4.8
Classes | Public Functions | Private Functions | Properties | List of all members
QGraphicsSceneBspTree Class Reference

#include <qgraphicsscene_bsp_p.h>

Classes

struct  Node
 

Public Functions

void clear ()
 
QString debug (int index) const
 
int firstChildIndex (int index) const
 
void initialize (const QRectF &rect, int depth)
 
void insertItem (QGraphicsItem *item, const QRectF &rect)
 
QList< QGraphicsItem * > items (const QRectF &rect, bool onlyTopLevelItems=false) const
 
int leafCount () const
 
int parentIndex (int index) const
 
 QGraphicsSceneBspTree ()
 
void removeItem (QGraphicsItem *item, const QRectF &rect)
 
void removeItems (const QSet< QGraphicsItem *> &items)
 
 ~QGraphicsSceneBspTree ()
 

Private Functions

void climbTree (QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index=0) const
 
void initialize (const QRectF &rect, int depth, int index)
 
QRectF rectForIndex (int index) const
 

Properties

QGraphicsSceneFindItemBspTreeVisitorfindVisitor
 
QGraphicsSceneInsertItemBspTreeVisitorinsertVisitor
 
int leafCnt
 
QVector< QList< QGraphicsItem * > > leaves
 
QVector< Nodenodes
 
QRectF rect
 
QGraphicsSceneRemoveItemBspTreeVisitorremoveVisitor
 

Detailed Description

Definition at line 72 of file qgraphicsscene_bsp_p.h.

Constructors and Destructors

◆ QGraphicsSceneBspTree()

QGraphicsSceneBspTree::QGraphicsSceneBspTree ( )

◆ ~QGraphicsSceneBspTree()

QGraphicsSceneBspTree::~QGraphicsSceneBspTree ( )

Definition at line 97 of file qgraphicsscene_bsp.cpp.

98 {
99  delete insertVisitor;
100  delete removeVisitor;
101  delete findVisitor;
102 }
QGraphicsSceneFindItemBspTreeVisitor * findVisitor
QGraphicsSceneInsertItemBspTreeVisitor * insertVisitor
QGraphicsSceneRemoveItemBspTreeVisitor * removeVisitor

Functions

◆ clear()

void QGraphicsSceneBspTree::clear ( )

Definition at line 116 of file qgraphicsscene_bsp.cpp.

117 {
118  leafCnt = 0;
119  nodes.clear();
120  leaves.clear();
121 }
void clear()
Removes all the elements from the vector and releases the memory used by the vector.
Definition: qvector.h:347
QVector< QList< QGraphicsItem * > > leaves

◆ climbTree()

void QGraphicsSceneBspTree::climbTree ( QGraphicsSceneBspTreeVisitor visitor,
const QRectF rect,
int  index = 0 
) const
private

Definition at line 237 of file qgraphicsscene_bsp.cpp.

Referenced by insertItem(), items(), parentIndex(), and removeItem().

238 {
239  if (nodes.isEmpty())
240  return;
241 
242  const Node &node = nodes.at(index);
243  const int childIndex = firstChildIndex(index);
244 
245  switch (node.type) {
246  case Node::Leaf: {
247  visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex]));
248  break;
249  }
250  case Node::Vertical:
251  if (rect.left() < node.offset) {
252  climbTree(visitor, rect, childIndex);
253  if (rect.right() >= node.offset)
254  climbTree(visitor, rect, childIndex + 1);
255  } else {
256  climbTree(visitor, rect, childIndex + 1);
257  }
258  break;
259  case Node::Horizontal:
260  if (rect.top() < node.offset) {
261  climbTree(visitor, rect, childIndex);
262  if (rect.bottom() >= node.offset)
263  climbTree(visitor, rect, childIndex + 1);
264  } else {
265  climbTree(visitor, rect, childIndex + 1);
266  }
267  }
268 }
qreal right() const
Returns the x-coordinate of the rectangle&#39;s right edge.
Definition: qrect.h:527
qreal left() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:525
int firstChildIndex(int index) const
virtual void visit(QList< QGraphicsItem *> *items)=0
void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index=0) const
QVector< QList< QGraphicsItem * > > leaves
quint16 index
qreal top() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:526
qreal bottom() const
Returns the y-coordinate of the rectangle&#39;s bottom edge.
Definition: qrect.h:528
The QList class is a template class that provides lists.
Definition: qdatastream.h:62

◆ debug()

QString QGraphicsSceneBspTree::debug ( int  index) const

Definition at line 166 of file qgraphicsscene_bsp.cpp.

Referenced by parentIndex().

167 {
168  const Node *node = &nodes.at(index);
169 
170  QString tmp;
171  if (node->type == Node::Leaf) {
173  if (!leaves[node->leafIndex].isEmpty()) {
174  tmp += QString::fromLatin1("[%1, %2, %3, %4] contains %5 items\n")
175  .arg(rect.left()).arg(rect.top())
176  .arg(rect.width()).arg(rect.height())
177  .arg(leaves[node->leafIndex].size());
178  }
179  } else {
180  if (node->type == Node::Horizontal) {
181  tmp += debug(firstChildIndex(index));
182  tmp += debug(firstChildIndex(index) + 1);
183  } else {
184  tmp += debug(firstChildIndex(index));
185  tmp += debug(firstChildIndex(index) + 1);
186  }
187  }
188 
189  return tmp;
190 }
qreal left() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:525
int firstChildIndex(int index) const
The QString class provides a Unicode character string.
Definition: qstring.h:83
The QRectF class defines a rectangle in the plane using floating point precision. ...
Definition: qrect.h:511
qreal height() const
Returns the height of the rectangle.
Definition: qrect.h:710
qreal width() const
Returns the width of the rectangle.
Definition: qrect.h:707
QString arg(qlonglong a, int fieldwidth=0, int base=10, const QChar &fillChar=QLatin1Char(' ')) const Q_REQUIRED_RESULT
Definition: qstring.cpp:7186
static QString fromLatin1(const char *, int size=-1)
Returns a QString initialized with the first size characters of the Latin-1 string str...
Definition: qstring.cpp:4188
QString debug(int index) const
QVector< QList< QGraphicsItem * > > leaves
quint16 index
qreal top() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:526
bool isEmpty() const
Returns true if the vector has size 0; otherwise returns false.
Definition: qvector.h:139
int size() const
Returns the number of items in the vector.
Definition: qvector.h:137
QRectF rectForIndex(int index) const

◆ firstChildIndex()

int QGraphicsSceneBspTree::firstChildIndex ( int  index) const
inline

Definition at line 98 of file qgraphicsscene_bsp_p.h.

Referenced by climbTree(), debug(), and initialize().

99  { return index * 2 + 1; }
quint16 index

◆ initialize() [1/2]

void QGraphicsSceneBspTree::initialize ( const QRectF rect,
int  depth 
)

Definition at line 104 of file qgraphicsscene_bsp.cpp.

Referenced by QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex(), initialize(), and parentIndex().

105 {
106  this->rect = rect;
107  leafCnt = 0;
108  nodes.resize((1 << (depth + 1)) - 1);
109  nodes.fill(Node());
110  leaves.resize(1 << depth);
112 
113  initialize(rect, depth, 0);
114 }
QVector< T > & fill(const T &t, int size=-1)
Assigns value to all items in the vector.
Definition: qvector.h:665
void initialize(const QRectF &rect, int depth)
void resize(int size)
Sets the size of the vector to size.
Definition: qvector.h:342
QVector< QList< QGraphicsItem * > > leaves
The QList class is a template class that provides lists.
Definition: qdatastream.h:62

◆ initialize() [2/2]

void QGraphicsSceneBspTree::initialize ( const QRectF rect,
int  depth,
int  index 
)
private

Definition at line 192 of file qgraphicsscene_bsp.cpp.

193 {
194  Node *node = &nodes[index];
195  if (index == 0) {
196  node->type = Node::Horizontal;
197  node->offset = rect.center().x();
198  }
199 
200  if (depth) {
202  QRectF rect1, rect2;
203  qreal offset1, offset2;
204 
205  if (node->type == Node::Horizontal) {
206  type = Node::Vertical;
207  rect1.setRect(rect.left(), rect.top(), rect.width(), rect.height() / 2);
208  rect2.setRect(rect1.left(), rect1.bottom(), rect1.width(), rect.height() - rect1.height());
209  offset1 = rect1.center().x();
210  offset2 = rect2.center().x();
211  } else {
212  type = Node::Horizontal;
213  rect1.setRect(rect.left(), rect.top(), rect.width() / 2, rect.height());
214  rect2.setRect(rect1.right(), rect1.top(), rect.width() - rect1.width(), rect1.height());
215  offset1 = rect1.center().y();
216  offset2 = rect2.center().y();
217  }
218 
219  int childIndex = firstChildIndex(index);
220 
221  Node *child = &nodes[childIndex];
222  child->offset = offset1;
223  child->type = type;
224 
225  child = &nodes[childIndex + 1];
226  child->offset = offset2;
227  child->type = type;
228 
229  initialize(rect1, depth - 1, childIndex);
230  initialize(rect2, depth - 1, childIndex + 1);
231  } else {
232  node->type = Node::Leaf;
233  node->leafIndex = leafCnt++;
234  }
235 }
qreal right() const
Returns the x-coordinate of the rectangle&#39;s right edge.
Definition: qrect.h:527
int type
Definition: qmetatype.cpp:239
double qreal
Definition: qglobal.h:1193
qreal left() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:525
void initialize(const QRectF &rect, int depth)
int firstChildIndex(int index) const
qreal x() const
Returns the x-coordinate of this point.
Definition: qpoint.h:282
The QRectF class defines a rectangle in the plane using floating point precision. ...
Definition: qrect.h:511
qreal height() const
Returns the height of the rectangle.
Definition: qrect.h:710
qreal width() const
Returns the width of the rectangle.
Definition: qrect.h:707
void setRect(qreal x, qreal y, qreal w, qreal h)
Sets the coordinates of the rectangle&#39;s top-left corner to (x, y), and its size to the given width an...
Definition: qrect.h:754
qreal y() const
Returns the y-coordinate of this point.
Definition: qpoint.h:287
quint16 index
qreal top() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:526
qreal bottom() const
Returns the y-coordinate of the rectangle&#39;s bottom edge.
Definition: qrect.h:528
QPointF center() const
Returns the center point of the rectangle.
Definition: qrect.h:686

◆ insertItem()

void QGraphicsSceneBspTree::insertItem ( QGraphicsItem item,
const QRectF rect 
)

Definition at line 123 of file qgraphicsscene_bsp.cpp.

Referenced by QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex().

124 {
125  insertVisitor->item = item;
126  climbTree(insertVisitor, rect);
127 }
QGraphicsSceneInsertItemBspTreeVisitor * insertVisitor
void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index=0) const

◆ items()

QList< QGraphicsItem * > QGraphicsSceneBspTree::items ( const QRectF rect,
bool  onlyTopLevelItems = false 
) const

Definition at line 149 of file qgraphicsscene_bsp.cpp.

Referenced by QGraphicsSceneBspTreeIndexPrivate::estimateItems(), and QGraphicsSceneBspTreeVisitor::~QGraphicsSceneBspTreeVisitor().

150 {
152  findVisitor->foundItems = &tmp;
153  findVisitor->onlyTopLevelItems = onlyTopLevelItems;
154  climbTree(findVisitor, rect);
155  // Reset discovery bits.
156  for (int i = 0; i < tmp.size(); ++i)
157  tmp.at(i)->d_ptr->itemDiscovered = 0;
158  return tmp;
159 }
QGraphicsSceneFindItemBspTreeVisitor * findVisitor
QScopedPointer< QGraphicsItemPrivate > d_ptr
const T & at(int i) const
Returns the item at index position i in the list.
Definition: qlist.h:468
QList< QGraphicsItem * > * foundItems
void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index=0) const
int size() const
Returns the number of items in the list.
Definition: qlist.h:137
The QList class is a template class that provides lists.
Definition: qdatastream.h:62

◆ leafCount()

int QGraphicsSceneBspTree::leafCount ( ) const

Definition at line 161 of file qgraphicsscene_bsp.cpp.

Referenced by QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex().

162 {
163  return leafCnt;
164 }

◆ parentIndex()

int QGraphicsSceneBspTree::parentIndex ( int  index) const
inline

Definition at line 101 of file qgraphicsscene_bsp_p.h.

Referenced by rectForIndex().

102  { return index > 0 ? ((index & 1) ? ((index - 1) / 2) : ((index - 2) / 2)) : -1; }
quint16 index

◆ rectForIndex()

QRectF QGraphicsSceneBspTree::rectForIndex ( int  index) const
private

Definition at line 270 of file qgraphicsscene_bsp.cpp.

Referenced by debug(), and parentIndex().

271 {
272  if (index <= 0)
273  return rect;
274 
275  int parentIdx = parentIndex(index);
276  QRectF rect = rectForIndex(parentIdx);
277  const Node *parent = &nodes.at(parentIdx);
278 
279  if (parent->type == Node::Horizontal) {
280  if (index & 1)
281  rect.setRight(parent->offset);
282  else
283  rect.setLeft(parent->offset);
284  } else {
285  if (index & 1)
286  rect.setBottom(parent->offset);
287  else
288  rect.setTop(parent->offset);
289  }
290 
291  return rect;
292 }
void setLeft(qreal pos)
Sets the left edge of the rectangle to the given x coordinate.
Definition: qrect.h:670
void setTop(qreal pos)
Sets the top edge of the rectangle to the given y coordinate.
Definition: qrect.h:674
void setBottom(qreal pos)
Sets the bottom edge of the rectangle to the given y coordinate.
Definition: qrect.h:676
int parentIndex(int index) const
void setRight(qreal pos)
Sets the right edge of the rectangle to the given x coordinate.
Definition: qrect.h:672
The QRectF class defines a rectangle in the plane using floating point precision. ...
Definition: qrect.h:511
quint16 index
QRectF rectForIndex(int index) const

◆ removeItem()

void QGraphicsSceneBspTree::removeItem ( QGraphicsItem item,
const QRectF rect 
)

Definition at line 129 of file qgraphicsscene_bsp.cpp.

Referenced by QGraphicsSceneBspTreeIndexPrivate::removeItem().

130 {
131  removeVisitor->item = item;
132  climbTree(removeVisitor, rect);
133 }
QGraphicsSceneRemoveItemBspTreeVisitor * removeVisitor
void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index=0) const

◆ removeItems()

void QGraphicsSceneBspTree::removeItems ( const QSet< QGraphicsItem *> &  items)

Definition at line 135 of file qgraphicsscene_bsp.cpp.

Referenced by QGraphicsSceneBspTreeIndexPrivate::purgeRemovedItems().

136 {
137  for (int i = 0; i < leaves.size(); ++i) {
138  QList<QGraphicsItem *> newItemList;
139  const QList<QGraphicsItem *> &oldItemList = leaves[i];
140  for (int j = 0; j < oldItemList.size(); ++j) {
141  QGraphicsItem *item = oldItemList.at(j);
142  if (!items.contains(item))
143  newItemList << item;
144  }
145  leaves[i] = newItemList;
146  }
147 }
The QGraphicsItem class is the base class for all graphical items in a QGraphicsScene.
Definition: qgraphicsitem.h:89
bool contains(const T &value) const
Definition: qset.h:91
const T & at(int i) const
Returns the item at index position i in the list.
Definition: qlist.h:468
int size() const
Returns the number of items in the list.
Definition: qlist.h:137
QVector< QList< QGraphicsItem * > > leaves
int size() const
Returns the number of items in the vector.
Definition: qvector.h:137
The QList class is a template class that provides lists.
Definition: qdatastream.h:62

Properties

◆ findVisitor

QGraphicsSceneFindItemBspTreeVisitor* QGraphicsSceneBspTree::findVisitor
private

Definition at line 118 of file qgraphicsscene_bsp_p.h.

Referenced by items(), QGraphicsSceneBspTree(), and ~QGraphicsSceneBspTree().

◆ insertVisitor

QGraphicsSceneInsertItemBspTreeVisitor* QGraphicsSceneBspTree::insertVisitor
private

◆ leafCnt

int QGraphicsSceneBspTree::leafCnt
private

Definition at line 113 of file qgraphicsscene_bsp_p.h.

Referenced by clear(), initialize(), and leafCount().

◆ leaves

QVector<QList<QGraphicsItem *> > QGraphicsSceneBspTree::leaves
private

Definition at line 112 of file qgraphicsscene_bsp_p.h.

Referenced by clear(), climbTree(), debug(), initialize(), and removeItems().

◆ nodes

QVector<Node> QGraphicsSceneBspTree::nodes
private

Definition at line 111 of file qgraphicsscene_bsp_p.h.

Referenced by clear(), climbTree(), debug(), initialize(), and rectForIndex().

◆ rect

QRectF QGraphicsSceneBspTree::rect
private

Definition at line 114 of file qgraphicsscene_bsp_p.h.

Referenced by debug(), initialize(), parentIndex(), and rectForIndex().

◆ removeVisitor

QGraphicsSceneRemoveItemBspTreeVisitor* QGraphicsSceneBspTree::removeVisitor
private

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