1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3/*!
4 \class QGraphicsSceneIndex
5 \brief The QGraphicsSceneIndex class provides a base class to implement
6 a custom indexing algorithm for discovering items in QGraphicsScene.
7 \since 4.6
8 \ingroup graphicsview-api
9
10 \internal
11
12 The QGraphicsSceneIndex class provides a base class to implement
13 a custom indexing algorithm for discovering items in QGraphicsScene. You
14 need to subclass it and reimplement addItem, removeItem, estimateItems
15 and items in order to have an functional indexing.
16
17 \sa QGraphicsScene, QGraphicsView
18*/
19
20#include "qdebug.h"
21#include "qgraphicsscene.h"
22#include "qgraphicsitem_p.h"
23#include "qgraphicsscene_p.h"
24#include "qgraphicswidget.h"
25#include "qgraphicssceneindex_p.h"
26#include "qgraphicsscenebsptreeindex_p.h"
27#include <QtGui/qpainterpath.h>
28
29QT_BEGIN_NAMESPACE
30
31namespace QtPrivate { // just to keep indentation of the following functions at the same level
32
33 static bool intersect_rect(const QGraphicsItem *item, const QRectF &exposeRect, Qt::ItemSelectionMode mode,
34 const QTransform &deviceTransform, const void *intersectData)
35 {
36 const QRectF sceneRect = *static_cast<const QRectF *>(intersectData);
37
38 QRectF brect = item->boundingRect();
39 _q_adjustRect(rect: &brect);
40
41 // ### Add test for this (without making things slower?)
42 Q_UNUSED(exposeRect);
43
44 bool keep = true;
45 const QGraphicsItemPrivate *itemd = QGraphicsItemPrivate::get(item);
46 if (itemd->itemIsUntransformable()) {
47 // Untransformable items; map the scene rect to item coordinates.
48 const QTransform transform = item->deviceTransform(viewportTransform: deviceTransform);
49 QRectF itemRect = (deviceTransform * transform.inverted()).mapRect(sceneRect);
50 if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect)
51 keep = itemRect.contains(r: brect) && itemRect != brect;
52 else
53 keep = itemRect.intersects(r: brect);
54 if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) {
55 QPainterPath itemPath;
56 itemPath.addRect(rect: itemRect);
57 keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, path: itemPath, mode);
58 }
59 } else {
60 Q_ASSERT(!itemd->dirtySceneTransform);
61 const QRectF itemSceneBoundingRect = itemd->sceneTransformTranslateOnly
62 ? brect.translated(dx: itemd->sceneTransform.dx(),
63 dy: itemd->sceneTransform.dy())
64 : itemd->sceneTransform.mapRect(brect);
65 if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect)
66 keep = sceneRect != brect && sceneRect.contains(r: itemSceneBoundingRect);
67 else
68 keep = sceneRect.intersects(r: itemSceneBoundingRect);
69 if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) {
70 QPainterPath rectPath;
71 rectPath.addRect(rect: sceneRect);
72 if (itemd->sceneTransformTranslateOnly)
73 rectPath.translate(dx: -itemd->sceneTransform.dx(), dy: -itemd->sceneTransform.dy());
74 else
75 rectPath = itemd->sceneTransform.inverted().map(p: rectPath);
76 keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, path: rectPath, mode);
77 }
78 }
79 return keep;
80 }
81
82 static bool intersect_point(const QGraphicsItem *item, const QRectF &exposeRect, Qt::ItemSelectionMode mode,
83 const QTransform &deviceTransform, const void *intersectData)
84 {
85 const QPointF scenePoint = *static_cast<const QPointF *>(intersectData);
86
87 QRectF brect = item->boundingRect();
88 _q_adjustRect(rect: &brect);
89
90 // ### Add test for this (without making things slower?)
91 Q_UNUSED(exposeRect);
92
93 bool keep = false;
94 const QGraphicsItemPrivate *itemd = QGraphicsItemPrivate::get(item);
95 if (itemd->itemIsUntransformable()) {
96 // Untransformable items; map the scene point to item coordinates.
97 const QTransform transform = item->deviceTransform(viewportTransform: deviceTransform);
98 QPointF itemPoint = (deviceTransform * transform.inverted()).map(p: scenePoint);
99 keep = brect.contains(p: itemPoint);
100 if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) {
101 QPainterPath pointPath;
102 pointPath.addRect(rect: QRectF(itemPoint, QSizeF(1, 1)));
103 keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, path: pointPath, mode);
104 }
105 } else {
106 Q_ASSERT(!itemd->dirtySceneTransform);
107 QRectF sceneBoundingRect = itemd->sceneTransformTranslateOnly
108 ? brect.translated(dx: itemd->sceneTransform.dx(),
109 dy: itemd->sceneTransform.dy())
110 : itemd->sceneTransform.mapRect(brect);
111 keep = sceneBoundingRect.intersects(r: QRectF(scenePoint, QSizeF(1, 1)));
112 if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) {
113 QPointF p = itemd->sceneTransformTranslateOnly
114 ? QPointF(scenePoint.x() - itemd->sceneTransform.dx(),
115 scenePoint.y() - itemd->sceneTransform.dy())
116 : itemd->sceneTransform.inverted().map(p: scenePoint);
117 keep = item->contains(point: p);
118 }
119 }
120
121 return keep;
122 }
123
124 static bool intersect_path(const QGraphicsItem *item, const QRectF &exposeRect, Qt::ItemSelectionMode mode,
125 const QTransform &deviceTransform, const void *intersectData)
126 {
127 const QPainterPath scenePath = *static_cast<const QPainterPath *>(intersectData);
128
129 QRectF brect = item->boundingRect();
130 _q_adjustRect(rect: &brect);
131
132 // ### Add test for this (without making things slower?)
133 Q_UNUSED(exposeRect);
134
135 bool keep = true;
136 const QGraphicsItemPrivate *itemd = QGraphicsItemPrivate::get(item);
137 if (itemd->itemIsUntransformable()) {
138 // Untransformable items; map the scene rect to item coordinates.
139 const QTransform transform = item->deviceTransform(viewportTransform: deviceTransform);
140 QPainterPath itemPath = (deviceTransform * transform.inverted()).map(p: scenePath);
141 if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect)
142 keep = itemPath.contains(rect: brect);
143 else
144 keep = itemPath.intersects(rect: brect);
145 if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape))
146 keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, path: itemPath, mode);
147 } else {
148 Q_ASSERT(!itemd->dirtySceneTransform);
149 const QRectF itemSceneBoundingRect = itemd->sceneTransformTranslateOnly
150 ? brect.translated(dx: itemd->sceneTransform.dx(),
151 dy: itemd->sceneTransform.dy())
152 : itemd->sceneTransform.mapRect(brect);
153 if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect)
154 keep = scenePath.contains(rect: itemSceneBoundingRect);
155 else
156 keep = scenePath.intersects(rect: itemSceneBoundingRect);
157 if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) {
158 QPainterPath itemPath = itemd->sceneTransformTranslateOnly
159 ? scenePath.translated(dx: -itemd->sceneTransform.dx(),
160 dy: -itemd->sceneTransform.dy())
161 : itemd->sceneTransform.inverted().map(p: scenePath);
162 keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, path: itemPath, mode);
163 }
164 }
165 return keep;
166 }
167
168} // namespace QtPrivate
169
170/*!
171 Constructs a private scene index.
172*/
173QGraphicsSceneIndexPrivate::QGraphicsSceneIndexPrivate(QGraphicsScene *scene) : scene(scene)
174{
175}
176
177/*!
178 Destructor of private scene index.
179*/
180QGraphicsSceneIndexPrivate::~QGraphicsSceneIndexPrivate()
181{
182}
183
184/*!
185 \internal
186
187 Checks if item collides with the path and mode, but also checks that if it
188 doesn't collide, maybe its frame rect will.
189*/
190bool QGraphicsSceneIndexPrivate::itemCollidesWithPath(const QGraphicsItem *item,
191 const QPainterPath &path,
192 Qt::ItemSelectionMode mode)
193{
194 if (item->collidesWithPath(path, mode))
195 return true;
196 if (item->isWidget()) {
197 // Check if this is a window, and if its frame rect collides.
198 const QGraphicsWidget *widget = static_cast<const QGraphicsWidget *>(item);
199 if (widget->isWindow()) {
200 QRectF frameRect = widget->windowFrameRect();
201 QPainterPath framePath;
202 framePath.addRect(rect: frameRect);
203 bool intersects = path.intersects(rect: frameRect);
204 if (mode == Qt::IntersectsItemShape || mode == Qt::IntersectsItemBoundingRect)
205 return intersects || path.contains(pt: frameRect.topLeft())
206 || framePath.contains(pt: path.elementAt(i: 0));
207 return !intersects && path.contains(pt: frameRect.topLeft());
208 }
209 }
210 return false;
211}
212
213/*!
214 \internal
215 This function returns the items in ascending order.
216*/
217void QGraphicsSceneIndexPrivate::recursive_items_helper(QGraphicsItem *item, QRectF exposeRect,
218 QGraphicsSceneIndexIntersector intersect,
219 QList<QGraphicsItem *> *items,
220 const QTransform &viewTransform,
221 Qt::ItemSelectionMode mode,
222 qreal parentOpacity, const void *intersectData) const
223{
224 Q_ASSERT(item);
225 if (!item->d_ptr->visible)
226 return;
227
228 const qreal opacity = item->d_ptr->combineOpacityFromParent(parentOpacity);
229 const bool itemIsFullyTransparent = QGraphicsItemPrivate::isOpacityNull(opacity);
230 const bool itemHasChildren = !item->d_ptr->children.isEmpty();
231 if (itemIsFullyTransparent && (!itemHasChildren || item->d_ptr->childrenCombineOpacity()))
232 return;
233
234 // Update the item's scene transform if dirty.
235 const bool itemIsUntransformable = item->d_ptr->itemIsUntransformable();
236 const bool wasDirtyParentSceneTransform = item->d_ptr->dirtySceneTransform && !itemIsUntransformable;
237 if (wasDirtyParentSceneTransform) {
238 item->d_ptr->updateSceneTransformFromParent();
239 Q_ASSERT(!item->d_ptr->dirtySceneTransform);
240 }
241
242 const bool itemClipsChildrenToShape = (item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape
243 || item->d_ptr->flags & QGraphicsItem::ItemContainsChildrenInShape);
244 bool processItem = !itemIsFullyTransparent;
245 if (processItem) {
246 processItem = intersect(item, exposeRect, mode, viewTransform, intersectData);
247 if (!processItem && (!itemHasChildren || itemClipsChildrenToShape)) {
248 if (wasDirtyParentSceneTransform)
249 item->d_ptr->invalidateChildrenSceneTransform();
250 return;
251 }
252 } // else we know for sure this item has children we must process.
253
254 int i = 0;
255 if (itemHasChildren) {
256 // Sort children.
257 item->d_ptr->ensureSortedChildren();
258
259 // Clip to shape.
260 if (itemClipsChildrenToShape && !itemIsUntransformable) {
261 QPainterPath mappedShape = item->d_ptr->sceneTransformTranslateOnly
262 ? item->shape().translated(dx: item->d_ptr->sceneTransform.dx(),
263 dy: item->d_ptr->sceneTransform.dy())
264 : item->d_ptr->sceneTransform.map(p: item->shape());
265 exposeRect &= mappedShape.controlPointRect();
266 }
267
268 // Process children behind
269 for (i = 0; i < item->d_ptr->children.size(); ++i) {
270 QGraphicsItem *child = item->d_ptr->children.at(i);
271 if (wasDirtyParentSceneTransform)
272 child->d_ptr->dirtySceneTransform = 1;
273 if (!(child->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent))
274 break;
275 if (itemIsFullyTransparent && !(child->d_ptr->flags & QGraphicsItem::ItemIgnoresParentOpacity))
276 continue;
277 recursive_items_helper(item: child, exposeRect, intersect, items, viewTransform,
278 mode, parentOpacity: opacity, intersectData);
279 }
280 }
281
282 // Process item
283 if (processItem)
284 items->append(t: item);
285
286 // Process children in front
287 if (itemHasChildren) {
288 for (; i < item->d_ptr->children.size(); ++i) {
289 QGraphicsItem *child = item->d_ptr->children.at(i);
290 if (wasDirtyParentSceneTransform)
291 child->d_ptr->dirtySceneTransform = 1;
292 if (itemIsFullyTransparent && !(child->d_ptr->flags & QGraphicsItem::ItemIgnoresParentOpacity))
293 continue;
294 recursive_items_helper(item: child, exposeRect, intersect, items, viewTransform,
295 mode, parentOpacity: opacity, intersectData);
296 }
297 }
298}
299
300void QGraphicsSceneIndexPrivate::init()
301{
302 if (!scene)
303 return;
304
305 QObject::connect(sender: scene, SIGNAL(sceneRectChanged(QRectF)),
306 receiver: q_func(), SLOT(updateSceneRect(QRectF)));
307}
308
309/*!
310 Constructs an abstract scene index for a given \a scene.
311*/
312QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsScene *scene)
313: QObject(*new QGraphicsSceneIndexPrivate(scene), scene)
314{
315 d_func()->init();
316}
317
318/*!
319 \internal
320*/
321QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsSceneIndexPrivate &dd, QGraphicsScene *scene)
322 : QObject(dd, scene)
323{
324 d_func()->init();
325}
326
327/*!
328 Destroys the scene index.
329*/
330QGraphicsSceneIndex::~QGraphicsSceneIndex()
331{
332
333}
334
335/*!
336 Returns the scene of this index.
337*/
338QGraphicsScene* QGraphicsSceneIndex::scene() const
339{
340 Q_D(const QGraphicsSceneIndex);
341 return d->scene;
342}
343
344/*!
345 \fn QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPointF &pos,
346 Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform
347 &deviceTransform) const
348
349 Returns all visible items that, depending on \a mode, are at the specified
350 \a pos and return a list sorted using \a order.
351
352 The default value for \a mode is Qt::IntersectsItemShape; all items whose
353 exact shape intersects with \a pos are returned.
354
355 \a deviceTransform is the transformation apply to the view.
356
357 This method use the estimation of the index (estimateItems) and refine the
358 list to get an exact result. If you want to implement your own refinement
359 algorithm you can reimplement this method.
360
361 \sa estimateItems()
362
363*/
364QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPointF &pos, Qt::ItemSelectionMode mode,
365 Qt::SortOrder order, const QTransform &deviceTransform) const
366{
367
368 Q_D(const QGraphicsSceneIndex);
369 QList<QGraphicsItem *> itemList;
370 d->items_helper(rect: QRectF(pos, QSizeF(1, 1)), intersect: &QtPrivate::intersect_point, items: &itemList, viewTransform: deviceTransform, mode, order, intersectData: &pos);
371 return itemList;
372}
373
374/*!
375 \fn QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QRectF &rect,
376 Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform
377 &deviceTransform) const
378
379 \overload
380
381 Returns all visible items that, depending on \a mode, are either inside or
382 intersect with the specified \a rect and return a list sorted using \a order.
383
384 The default value for \a mode is Qt::IntersectsItemShape; all items whose
385 exact shape intersects with or is contained by \a rect are returned.
386
387 \a deviceTransform is the transformation apply to the view.
388
389 This method use the estimation of the index (estimateItems) and refine
390 the list to get an exact result. If you want to implement your own
391 refinement algorithm you can reimplement this method.
392
393 \sa estimateItems()
394
395*/
396QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QRectF &rect, Qt::ItemSelectionMode mode,
397 Qt::SortOrder order, const QTransform &deviceTransform) const
398{
399 Q_D(const QGraphicsSceneIndex);
400 QRectF exposeRect = rect;
401 _q_adjustRect(rect: &exposeRect);
402 QList<QGraphicsItem *> itemList;
403 d->items_helper(rect: exposeRect, intersect: &QtPrivate::intersect_rect, items: &itemList, viewTransform: deviceTransform, mode, order, intersectData: &rect);
404 return itemList;
405}
406
407/*!
408 \fn QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPolygonF
409 &polygon, Qt::ItemSelectionMode mode, Qt::SortOrder order, const
410 QTransform &deviceTransform) const
411
412 \overload
413
414 Returns all visible items that, depending on \a mode, are either inside or
415 intersect with the specified \a polygon and return a list sorted using \a order.
416
417 The default value for \a mode is Qt::IntersectsItemShape; all items whose
418 exact shape intersects with or is contained by \a polygon are returned.
419
420 \a deviceTransform is the transformation apply to the view.
421
422 This method use the estimation of the index (estimateItems) and refine
423 the list to get an exact result. If you want to implement your own
424 refinement algorithm you can reimplement this method.
425
426 \sa estimateItems()
427
428*/
429QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPolygonF &polygon, Qt::ItemSelectionMode mode,
430 Qt::SortOrder order, const QTransform &deviceTransform) const
431{
432 Q_D(const QGraphicsSceneIndex);
433 QList<QGraphicsItem *> itemList;
434 QRectF exposeRect = polygon.boundingRect();
435 _q_adjustRect(rect: &exposeRect);
436 QPainterPath path;
437 path.addPolygon(polygon);
438 d->items_helper(rect: exposeRect, intersect: &QtPrivate::intersect_path, items: &itemList, viewTransform: deviceTransform, mode, order, intersectData: &path);
439 return itemList;
440}
441
442/*!
443 \fn QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath
444 &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform
445 &deviceTransform) const
446
447 \overload
448
449 Returns all visible items that, depending on \a mode, are either inside or
450 intersect with the specified \a path and return a list sorted using \a order.
451
452 The default value for \a mode is Qt::IntersectsItemShape; all items whose
453 exact shape intersects with or is contained by \a path are returned.
454
455 \a deviceTransform is the transformation apply to the view.
456
457 This method use the estimation of the index (estimateItems) and refine
458 the list to get an exact result. If you want to implement your own
459 refinement algorithm you can reimplement this method.
460
461 \sa estimateItems()
462
463*/
464QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath &path, Qt::ItemSelectionMode mode,
465 Qt::SortOrder order, const QTransform &deviceTransform) const
466{
467 Q_D(const QGraphicsSceneIndex);
468 QList<QGraphicsItem *> itemList;
469 QRectF exposeRect = path.controlPointRect();
470 _q_adjustRect(rect: &exposeRect);
471 d->items_helper(rect: exposeRect, intersect: &QtPrivate::intersect_path, items: &itemList, viewTransform: deviceTransform, mode, order, intersectData: &path);
472 return itemList;
473}
474
475/*!
476 This virtual function return an estimation of items at position \a point.
477 This method return a list sorted using \a order.
478*/
479QList<QGraphicsItem *> QGraphicsSceneIndex::estimateItems(const QPointF &point, Qt::SortOrder order) const
480{
481 return estimateItems(rect: QRectF(point, QSize(1, 1)), order);
482}
483
484QList<QGraphicsItem *> QGraphicsSceneIndex::estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const
485{
486 Q_D(const QGraphicsSceneIndex);
487 Q_UNUSED(rect);
488 QGraphicsScenePrivate *scened = d->scene->d_func();
489 scened->ensureSortedTopLevelItems();
490 if (order == Qt::DescendingOrder) {
491 QList<QGraphicsItem *> sorted;
492 const int numTopLevelItems = scened->topLevelItems.size();
493 sorted.reserve(asize: numTopLevelItems);
494 for (int i = numTopLevelItems - 1; i >= 0; --i)
495 sorted << scened->topLevelItems.at(i);
496 return sorted;
497 }
498 return scened->topLevelItems;
499}
500
501/*!
502 \fn QList<QGraphicsItem *> QGraphicsSceneIndex::items(Qt::SortOrder order = Qt::DescendingOrder) const
503
504 This pure virtual function all items in the index and sort them using
505 \a order.
506*/
507
508
509/*!
510 Notifies the index that the scene's scene rect has changed. \a rect
511 is thew new scene rect.
512
513 \sa QGraphicsScene::sceneRect()
514*/
515void QGraphicsSceneIndex::updateSceneRect(const QRectF &rect)
516{
517 Q_UNUSED(rect);
518}
519
520/*!
521 This virtual function removes all items in the scene index.
522*/
523void QGraphicsSceneIndex::clear()
524{
525 const QList<QGraphicsItem *> allItems = items();
526 for (int i = 0 ; i < allItems.size(); ++i)
527 removeItem(item: allItems.at(i));
528}
529
530/*!
531 \fn virtual void QGraphicsSceneIndex::addItem(QGraphicsItem *item) = 0
532
533 This pure virtual function inserts an \a item to the scene index.
534
535 \sa removeItem(), deleteItem()
536*/
537
538/*!
539 \fn virtual void QGraphicsSceneIndex::removeItem(QGraphicsItem *item) = 0
540
541 This pure virtual function removes an \a item to the scene index.
542
543 \sa addItem(), deleteItem()
544*/
545
546/*!
547 This method is called when an \a item has been deleted.
548 The default implementation calls removeItem. Be careful,
549 if your implementation of removeItem use pure virtual method
550 of QGraphicsItem like boundingRect(), then you should reimplement
551 this method.
552
553 \sa addItem(), removeItem()
554*/
555void QGraphicsSceneIndex::deleteItem(QGraphicsItem *item)
556{
557 removeItem(item);
558}
559
560/*!
561 This virtual function is called by QGraphicsItem to notify the index
562 that some part of the \a item 's state changes. By reimplementing this
563 function, your can react to a change, and in some cases, (depending on \a
564 change,) adjustments in the index can be made.
565
566 \a change is the parameter of the item that is changing. \a value is the
567 value that changed; the type of the value depends on \a change.
568
569 The default implementation does nothing.
570
571 \sa QGraphicsItem::GraphicsItemChange
572*/
573void QGraphicsSceneIndex::itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const void *const value)
574{
575 Q_UNUSED(item);
576 Q_UNUSED(change);
577 Q_UNUSED(value);
578}
579
580/*!
581 Notify the index for a geometry change of an \a item.
582
583 \sa QGraphicsItem::prepareGeometryChange()
584*/
585void QGraphicsSceneIndex::prepareBoundingRectChange(const QGraphicsItem *item)
586{
587 Q_UNUSED(item);
588}
589
590QT_END_NAMESPACE
591
592#include "moc_qgraphicssceneindex_p.cpp"
593

source code of qtbase/src/widgets/graphicsview/qgraphicssceneindex.cpp