[josm-dev] JOSM Mappaint - major improvements

[Dirk Stöcker]

On Tue, 13 Jan 2009, Raphaël Jacquot 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

That is not so easy, because JOSM has no encapsulated data structures.

But when we get the O() reduced a lot, then it will get a lot faster as 
well. When optimizing not only the argument to O(), but the function 
itself is also important (This is what Ulf has successfully done and which 
has still some potential).

Ciao
-- 
http://www.dstoecker.eu/ (PGP key available)