Hi guys,<br><br>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 &gt;= 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&#39;s much (10X) slower than the naive approach in R of finding points that are within a rectangle. <br>
<br>Not quite sure what&#39;s happening here. I could report it as a bug, but I&#39;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.<br>
<br>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&#39;t much in the way of open-source implementations of computational geometry algorithms. This might have changed.<br>
<br>Michael<br><br><br><br><br>