QGraphicsScene and dynamic addition of QGraphicsItems

[El Bazza]

Hi All,

I'm pretty new to Qt, so I apologise in advance if there's an obvious way to do this that I've overlooked...

I'm using Qt Creator 1.3.1 and Qt 4.6.2 on a Linux (Ubuntu) machine, and the application I'm writing has a QGraphicsScene and associated view. I've made a Custom QGraphicsItem, derived from QGraphicsRectItem.

One or more of these Custom GraphicsItems can be added to the View/Scene - and the problem I'm having is that they will be added in the same place by default, and I can't see an obvious and simple way of arranging them so that they will not collide with each other when the view is redrawn.

I thought about trying to apply a Grid Layout style to the scene or view, but I can't figure out how to do that, and the only other way I can think of forcing the objects to not collide is to attempt to add at a given location, and use the colliding items list to determine whether or not I can add at the given location, and keep trying until I find a free location.

I'm sure there's an easier way to do this, but I can't quite see it, as mentioned before, I'm very new to Qt (Most of my previous work has been done using MFC but that's not an option here due to the constraints on system, OS etc.)

So, if anyone can help, I'd greatly appreciate it

[tuli]

Someone else in my environment will be working on something like that soon, too, and from what i have heard Qt does not deliver graphing algorithms.
AFAIK, we are now settling with using a hybrid of using an external graphin algorithm library in conjunction with Qt for visualizing. (Again, i am not directly involved so i dont know.)
I`ll ask them for details tomorrow, but i think they`d be thankful, too, for one or two hints regarding such problems...

[d_stranz]

One or more of these Custom GraphicsItems can be added to the View/Scene - and the problem I'm having is that they will be added in the same place by default, and I can't see an obvious and simple way of arranging them so that they will not collide with each other when the view is redrawn.

Who is doing the adding? If it is being done in response to a button click or whatever, put some state information into the class managing the scene that "knows" about the next available grid location and move the object after it is added to the scene, or even better just add it at the right location. Resorting to some type of graphing algorithm library for something as simple as laying out rectangles in a grid seems like overkill to me.

"Next available grid location" could be as simple as:

// pseudocode
void myClass::addNewItemAtNextLocation()
{
  // itemIndex is a member variable, initialized to zero in constructor
  // itemsPerRow could be fixed or might depend on view size
  // horzGap and vertGap is the empty space between rects so their edges don't coincide
 
  int rowNumber = int( itemIndex / itemsPerRow );  
  int colNumber  = int( itemIndex % itemsPerRow );
 
  QPointF itemPos = QPointF( colNumber * (itemWidth + horzGap), rowNumber * (itemHeight + vertGap) );
  QSizeF  itemSize = QSizeF( itemWidth, itemHeight );
 
  CustomItem * item = new CustomItem( QRectF( itemPos, itemSize ) );
  scene.addItem( item );
 
  itemIndex++;
}

// pseudocode
void myClass::addNewItemAtNextLocation()
{
  // itemIndex is a member variable, initialized to zero in constructor
  // itemsPerRow could be fixed or might depend on view size
  // horzGap and vertGap is the empty space between rects so their edges don't coincide

  int rowNumber = int( itemIndex / itemsPerRow );  
  int colNumber  = int( itemIndex % itemsPerRow );

  QPointF itemPos = QPointF( colNumber * (itemWidth + horzGap), rowNumber * (itemHeight + vertGap) );
  QSizeF  itemSize = QSizeF( itemWidth, itemHeight );

  CustomItem * item = new CustomItem( QRectF( itemPos, itemSize ) );
  scene.addItem( item );

  itemIndex++;
}

To copy to clipboard, switch view to plain text mode 

This will add new items across then down. If the items can be dynamically added and removed or moved from cell-to-cell, then you'd need a more sophisticated way to keep track of which cells are empty, or if it is acceptable in your GUI, removing an item could simply shift everything above it down by one index location.

[El Bazza]

Thanks for the answer. Something like this should be do-able, although the QGraphicsItems themselves will be movable, which makes things a little trickier.If, as you say, I keep Position information for each of the outermost bounding rects for my class, I should be able to locate an empty space fairly quickly?

EDIT: Thinking a little further, I may keep a list of the bounding rects of the outermost QGraphicsRectItem in my custom class, one bounding rect for each instance. I'll then be able to interrogate the list when I create a new one, and be able to work out a position that will be empty (the outer rect is currently a fixed size, if I implement re-sizing, that may change). More thought required on how to keep the list updated with correct positions now...

[d_stranz]

More thought required on how to keep the list updated with correct positions now...

Perhaps a quadtree data structure would work. You will only need to subdivide your space down to the size of the bounding rects of your items, and can check in O(log N) time for empty spots. As the user moves items (or new items are placed) you can restrict their final positions to the free spaces in the grid, as determined by searching the quadtree. Depending on how many items you have, you can either update the quadtree dynamically as items are added or moved, or simply re-create it on the fly from the the list of child items in your scene.

[wysota]

A trivial solution is to use QGraphicsScene::itemsBoundingRect() and add a new item always on the right of the bounding rect and use QGraphicsItem::itemChange() to prevent items from colliding when they are being moved.

[d_stranz]

add a new item always on the right of the bounding rect

Wouldn't that result in just a horizontal row of items? Or is that why you call it "trivial"? The OP first wanted to use a grid layout, so I assumed a rectangular array was what was needed. On the other hand, I have no idea if the OP will later want to impose some relationships among his custom items so maybe none of these suggestions will prove useful in the end. Blind men and an elephant, as usual.

[wysota]

Wouldn't that result in just a horizontal row of items? Or is that why you call it "trivial"?

Yes, trivial Since the user is able to move elements arounds (at least that was my impression when reading the thread), she/he can position them as required. One can use some heuristics like when no items have been moved after last addition, add the item below the last added item (then again on the right, etc.). In effect one gets a grid-like behaviour.