Qt 4.8
qgraphicsscene_bsp.cpp
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 #include "qgraphicsscene_bsp_p.h"
43 
44 #ifndef QT_NO_GRAPHICSVIEW
45 
46 #include <QtCore/qstring.h>
47 #include <private/qgraphicsitem_p.h>
48 
50 
52 {
53 public:
55 
57  { items->prepend(item); }
58 };
59 
61 {
62 public:
64 
66  { items->removeAll(item); }
67 };
68 
70 {
71 public:
74 
76  {
77  for (int i = 0; i < items->size(); ++i) {
78  QGraphicsItem *item = items->at(i);
79  if (onlyTopLevelItems && item->d_ptr->parent)
80  item = item->topLevelItem();
81  if (!item->d_func()->itemDiscovered && item->d_ptr->visible) {
82  item->d_func()->itemDiscovered = 1;
83  foundItems->prepend(item);
84  }
85  }
86  }
87 };
88 
90  : leafCnt(0)
91 {
95 }
96 
98 {
99  delete insertVisitor;
100  delete removeVisitor;
101  delete findVisitor;
102 }
103 
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 }
115 
117 {
118  leafCnt = 0;
119  nodes.clear();
120  leaves.clear();
121 }
122 
124 {
125  insertVisitor->item = item;
126  climbTree(insertVisitor, rect);
127 }
128 
130 {
131  removeVisitor->item = item;
132  climbTree(removeVisitor, rect);
133 }
134 
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 }
148 
149 QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect, bool onlyTopLevelItems) const
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 }
160 
162 {
163  return leafCnt;
164 }
165 
167 {
168  const Node *node = &nodes.at(index);
169 
170  QString tmp;
171  if (node->type == Node::Leaf) {
172  QRectF rect = rectForIndex(index);
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 }
191 
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 }
236 
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 }
269 
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 }
293 
295 
296 #endif // QT_NO_GRAPHICSVIEW
QGraphicsItem * parent
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
QGraphicsSceneFindItemBspTreeVisitor * findVisitor
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
QScopedPointer< QGraphicsItemPrivate > d_ptr
void setLeft(qreal pos)
Sets the left edge of the rectangle to the given x coordinate.
Definition: qrect.h:670
QVector< T > & fill(const T &t, int size=-1)
Assigns value to all items in the vector.
Definition: qvector.h:665
void visit(QList< QGraphicsItem *> *items)
void visit(QList< QGraphicsItem *> *items)
The QGraphicsItem class is the base class for all graphical items in a QGraphicsScene.
Definition: qgraphicsitem.h:89
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)
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 firstChildIndex(int index) const
QList< QGraphicsItem * > items(const QRectF &rect, bool onlyTopLevelItems=false) const
The QString class provides a Unicode character string.
Definition: qstring.h:83
virtual void visit(QList< QGraphicsItem *> *items)=0
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
qreal x() const
Returns the x-coordinate of this point.
Definition: qpoint.h:282
void resize(int size)
Sets the size of the vector to size.
Definition: qvector.h:342
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
The QRectF class defines a rectangle in the plane using floating point precision. ...
Definition: qrect.h:511
void clear()
Removes all the elements from the vector and releases the memory used by the vector.
Definition: qvector.h:347
bool contains(const T &value) const
Definition: qset.h:91
qreal height() const
Returns the height of the rectangle.
Definition: qrect.h:710
void prepend(const T &t)
Inserts value at the beginning of the list.
Definition: qlist.h:541
const T & at(int i) const
Returns the item at index position i in the list.
Definition: qlist.h:468
QList< QGraphicsItem * > * foundItems
void visit(QList< QGraphicsItem *> *items)
QGraphicsSceneInsertItemBspTreeVisitor * insertVisitor
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
QGraphicsItem * topLevelItem() const
Returns this item&#39;s top-level item.
QGraphicsSceneRemoveItemBspTreeVisitor * removeVisitor
void insertItem(QGraphicsItem *item, const QRectF &rect)
void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index=0) const
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
int size() const
Returns the number of items in the list.
Definition: qlist.h:137
QString debug(int index) const
QVector< QList< QGraphicsItem * > > leaves
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
bool isEmpty() const
Returns true if the vector has size 0; otherwise returns false.
Definition: qvector.h:139
qreal bottom() const
Returns the y-coordinate of the rectangle&#39;s bottom edge.
Definition: qrect.h:528
void removeItems(const QSet< QGraphicsItem *> &items)
QPointF center() const
Returns the center point of the rectangle.
Definition: qrect.h:686
int size() const
Returns the number of items in the vector.
Definition: qvector.h:137
void removeItem(QGraphicsItem *item, const QRectF &rect)
The QList class is a template class that provides lists.
Definition: qdatastream.h:62
QRectF rectForIndex(int index) const
int removeAll(const T &t)
Removes all occurrences of value in the list and returns the number of entries removed.
Definition: qlist.h:770