From 30d01c387179160c8c418ecedfb4506a55d282e8 Mon Sep 17 00:00:00 2001 From: Lars Knoll Date: Fri, 27 Mar 2009 22:17:10 +0100 Subject: Optimise QGraphicsScene/View::items(const QPointF &pos) Implement specialized (and more efficient versions) of item_helper() and child_helper() that test for QPointF in the scene. --- src/gui/graphicsview/qgraphicsscene.cpp | 94 ++++++++++++++++++++++++++++----- src/gui/graphicsview/qgraphicsscene_p.h | 4 ++ src/gui/graphicsview/qgraphicsview.cpp | 4 +- 3 files changed, 88 insertions(+), 14 deletions(-) diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp index e13a767..b4dc62c 100644 --- a/src/gui/graphicsview/qgraphicsscene.cpp +++ b/src/gui/graphicsview/qgraphicsscene.cpp @@ -1358,6 +1358,48 @@ QGraphicsWidget *QGraphicsScenePrivate::windowForItem(const QGraphicsItem *item) return 0; } + +QList QGraphicsScenePrivate::items_helper(const QPointF &pos) const +{ + QList items; + + // The index returns a rough estimate of what items are inside the rect. + // Refine it by iterating through all returned items. + QRectF adjustedRect = QRectF(pos, QSize(1,1)); + foreach (QGraphicsItem *item, estimateItemsInRect(adjustedRect)) { + // Find the item's scene transform in a clever way. + QTransform x = item->sceneTransform(); + bool keep = false; + + // ### _q_adjustedRect is only needed because QRectF::intersects, + // QRectF::contains and QTransform::map() and friends don't work with + // flat rectangles. + QRectF br = _q_adjustedRect(item->boundingRect()); + // Rect intersects/contains item's shape + if (QRectF_intersects(adjustedRect, x.mapRect(br))) { + bool ok; + QTransform xinv = x.inverted(&ok); + if (ok) { + if (item->contains(xinv.map(pos))) { + items << item; + keep = true; + } + } + } + + if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) { + // Recurse into children that clip children. + bool ok; + QTransform xinv = x.inverted(&ok); + if (ok) + childItems_helper(&items, item, xinv.map(pos)); + } + } + + sortItems(&items, Qt::AscendingOrder, sortCacheEnabled); + return items; +} + QList QGraphicsScenePrivate::items_helper(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order) const @@ -1392,7 +1434,7 @@ QList QGraphicsScenePrivate::items_helper(const QRectF &rect, bool ok; QTransform xinv = x.inverted(&ok); if (ok) { - if (path == QPainterPath()) + if (path.isEmpty()) path.addRect(rect); if (itemCollidesWithPath(item, xinv.map(path), mode)) { items << item; @@ -1536,6 +1578,42 @@ QList QGraphicsScenePrivate::items_helper(const QPainterPath &p void QGraphicsScenePrivate::childItems_helper(QList *items, const QGraphicsItem *parent, + const QPointF &pos) const +{ + bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape); + if (parentClip && parent->d_ptr->isClippedAway()) + return; + // ### is this needed? + if (parentClip && !parent->boundingRect().contains(pos)) + return; + + QList &children = parent->d_ptr->children; + for (int i = 0; i < children.size(); ++i) { + QGraphicsItem *item = children.at(i); + if (item->d_ptr->hasTransform && !item->transform().isInvertible()) + continue; + + // Skip invisible items and all their children. + if (item->d_ptr->isInvisible()) + continue; + + bool keep = false; + if (!item->d_ptr->isClippedAway()) { + if (item->contains(item->mapFromParent(pos))) { + items->append(item); + keep = true; + } + } + + if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) + // Recurse into children. + childItems_helper(items, item, item->mapFromParent(pos)); + } +} + + +void QGraphicsScenePrivate::childItems_helper(QList *items, + const QGraphicsItem *parent, const QRectF &rect, Qt::ItemSelectionMode mode) const { @@ -1597,6 +1675,7 @@ void QGraphicsScenePrivate::childItems_helper(QList *items, } } + void QGraphicsScenePrivate::childItems_helper(QList *items, const QGraphicsItem *parent, const QPolygonF &polygon, @@ -2380,17 +2459,8 @@ QList QGraphicsScene::items() const */ QList QGraphicsScene::items(const QPointF &pos) const { - QList itemsAtPoint; - - // Find all items within a 1x1 rect area starting at pos. This can be - // inefficient for scenes that use small coordinates (like unity - // coordinates), or for detailed graphs. ### The index should support - // fetching items at a pos to avoid this limitation. - foreach (QGraphicsItem *item, items(QRectF(pos, QSizeF(1, 1)), Qt::IntersectsItemBoundingRect)) { - if (item->contains(item->mapFromScene(pos))) - itemsAtPoint << item; - } - return itemsAtPoint; + Q_D(const QGraphicsScene); + return d->items_helper(pos); } diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h index 9c165d1..befbbd8 100644 --- a/src/gui/graphicsview/qgraphicsscene_p.h +++ b/src/gui/graphicsview/qgraphicsscene_p.h @@ -197,6 +197,7 @@ public: void mousePressEventHandler(QGraphicsSceneMouseEvent *mouseEvent); QGraphicsWidget *windowForItem(const QGraphicsItem *item) const; + QList items_helper(const QPointF &pos) const; QList items_helper(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order) const; @@ -208,6 +209,9 @@ public: Qt::SortOrder order) const; void childItems_helper(QList *items, const QGraphicsItem *parent, + const QPointF &pos) const; + void childItems_helper(QList *items, + const QGraphicsItem *parent, const QRectF &rect, Qt::ItemSelectionMode mode) const; void childItems_helper(QList *items, diff --git a/src/gui/graphicsview/qgraphicsview.cpp b/src/gui/graphicsview/qgraphicsview.cpp index f0d360a..ba9cdbf 100644 --- a/src/gui/graphicsview/qgraphicsview.cpp +++ b/src/gui/graphicsview/qgraphicsview.cpp @@ -2251,9 +2251,9 @@ QList QGraphicsView::items(const QPoint &pos) const if (d->scene->d_func()->largestUntransformableItem.isNull()) { if ((d->identityMatrix || d->matrix.type() <= QTransform::TxScale)) { QTransform xinv = viewportTransform().inverted(); - return d->scene->items(xinv.mapRect(QRectF(pos.x(), pos.y(), 1, 1))); + return d->scene->items(xinv.map(pos)); } - return d->scene->items(mapToScene(pos.x(), pos.y(), 2, 2)); + return d->scene->items(mapToScene(pos)); } QPainterPath path; -- cgit v0.12