[josm-dev] JOSM Mappaint - major improvements

[Sascha Silbe]

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.
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

-- 
http://sascha.silbe.org/
http://www.infra-silbe.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 481 bytes
Desc: Digital signature
URL: <http://lists.openstreetmap.org/pipermail/josm-dev/attachments/20090113/795697d8/attachment.pgp>