[josm-dev] JOSM Mappaint - major improvements

[Raphaël Jacquot]

Sascha Silbe wrote:
> On Tue, Jan 13, 2009 at 12:58:38PM +0100, Rolf Bode-Meyer wrote:
> 
>> What I don't understand - with your change and before - is that paint
>> speed seems to depend on the amount of data in the layer even if it's
>> outside the view.
> That's to be expected. Even with a spatial index (AFAIK josm still 
> doesn't use one yet), looking up the objects inside a give bounding box 
> ("the view") is dependant on the total number of objects. For example, a 
> 2D-PR-Tree lookup is about O(sqrt(n)) [1], with n being the total number 
> of objects stored in the tree.

imho, we should use one, as O(sqrt(n)) is still much better than the 
linear O(n) that josm currently requires to go through the entire set of 
things that are available to be drawn

> If some genius invents a spatial index with lookup in O(1), I'm sure 
> we'll hear about it. :)
> 
> 
> [1] http://www.cse.ust.hk/~yike/prtree/pr.pdf
> 
> CU Sascha
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> josm-dev mailing list
> josm-dev at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/josm-dev