I am thinking about two options here:

1)
As you suggested, represent all items as paths and find proper intersection to determine the fill area.
(Although I'm not exactly sure how to find a closed intersected path around a given point if one exists, or to determine the case when one doesn't exist)

2)
Override the paint() method in an extended QGraphicsItem, and use a QImage inside this item. So all painting basically happens on this QImage.

Also, remember that the user can create free hand lines. Assuming they try to sketch drawings, there might be a large number of tiny paths on the scene.

Considering these, which of the above two options do you think is more efficient for floodfill?