[RQt-devel] qtpaint: performance regressions in scene indexing

[Michael Lawrence]

Hi guys,

People have been complaining about the performance of the scene indexing
(i.e., the Layer::locate method). A month or so ago we worked around the
inefficient population of the index. But now it appears that in Qt >= 4.6 (I
think) the performance of lookups has regressed. It now appears to scale
linearly, rather than logarithmically, in the number of items. Not only
that, but it's much (10X) slower than the naive approach in R of finding
points that are within a rectangle.

Not quite sure what's happening here. I could report it as a bug, but I'm
not optimistic that it would be fixed. The simple truth is that most modern
graphical user interfaces (think phones but increasingly desktops), have a
few items that are constantly moving. Not thousands of items that are
static. From my reading, most people turn off the BSP index, because it just
gets in the way.

For now, we could do the naive check in R (10X speedup), or implement our
own spatial data structure in C. Honestly, the use of the Qt index was a bit
of a hack. It involved adding a bunch of dummy items (one for every point)
to an invisible scene. A custom implementation would be much cleaner. The
last time I checked (a couple years ago) there wasn't much in the way of
open-source implementations of computational geometry algorithms. This might
have changed.

Michael
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.r-forge.r-project.org/pipermail/qtinterfaces-devel/attachments/20110506/9c5be089/attachment.htm>