[josm-dev] Path to spatial index [long][Was: Refactoring of the JOSM architecture vs. Plugins]

[Petr Nejedly]

jh napsal(a):
> Petr Nejedly schrieb:
>> Right. You do some attempts on relation rendering, so filtering them 
>> will come handy.
>> Not because there are many of them (to the contrary), but because the 
>> index API
>> would be very simple then: Iterable<OsmPrimitive> 
>> giveMeAllThePrimitivesInside(Bounds bounds);
>> (or better "visitAllThePrimitivesInside(Bounds bounds, Visitor vis);"
>>   
> Speaking of bounds: I saw that in -NG your QTree indexes all primitives 
> by bounds. Have you considered indexing ways (or rather their segments) 
> by intersected (crossed) nodes instead of using the segment bounds? I 
> guess with a bucket size of 100 that might not make that much of a 
> difference, because segments are usually relatively short compared to 
> the node density, but you might have had other reasons as well.

The reason is that you can have a way that crosses current screen, yet none of its
nodes are on the screen. Long way on close zoom, for example.
For a nice graphical explanation, see:
http://wiki.openstreetmap.org/index.php/QuadTiles#Indexing_tile_intersections

>> Not initially, but you will, earlier or later, end up caching the 
>> associated style too,
>> (this is the "below" where you'll clutter OsmPrimitive with another 
>> field) and this is
>> tags dependent. 
> Yes, also because damage tracking is dependent on the visual (pixel) 
> extent for a primitive which, in turn is style dependent.

This is something I don't currently deal with, so it may (rarely, see below*)
happen that when you should see a half of the icon on the edge of the screen,
the icon might not render at all. The simplest workaround for this is to
just add enough pixels to the bounds before asking the index.

*) Because the quadtile indexing is rough (that is, you usually already get more
data than you asked for), the problem would only be visible on the very rare case
when a node ends up very close to the quadtile border and you hapenned to have similarly
positioned viewport.


>> Also, the index might take current zoom into account too and structurally
>> filter out unimportant (highway=residential, untagged node) primitives 
>> when looking
>> at the whole shebang. See:
>> http://svn.openstreetmap.org/applications/editors/josm-ng/src/org/openstreetmap/josmng/view/osm/View.java 
>>
>>   
> Great Idea!

Very roughly realized in:
http://svn.openstreetmap.org/applications/editors/josm-ng/src/org/openstreetmap/josmng/view/osm/ViewData.java
see qGet() (and the other q* functions)
In reality, the qTree alone could take care of the detail level.
The next trick would be to generalize the ways for wide zooms and keep
exact data for close zooms.

>> The second important thing is the way you'll react to modifications. 
>> You've got the hook
>> in the form of setCoords, so what would you do?
>> 1. Update the index for given Node (that is, remove and readd it)
>> 2. Find all the referers (ways, relations). Well, (d) from third 
>> paragraph has higher
>>     importance, it seems, as long as you don't have self-consistent 
>> backref baked into
>>     the DataSet (josm-ng does)
>> 3. Update referer bboxes (maybe recursively)
>>
>> Is this right? NO! Imagine a user drags a 4000node forest (there is 
>> one such in Germany,
>> and I've even been (physically) to one 5500+ nodes in Poland recently 
>> ;-) )
>> You're going to get 4000 node updates and you're likely to end up 
>> visiting all the 4000 nodes
>> each time to compute the new bounds (4000^2). 
> Sorry, you've lost me with the -squared. Why would we have to visit all 
> other nodes per node?

So you get an independent event that node N1 have moved. You have no idea
there are additional 3999 events to come, so you look up all the N1's ways
(let's say that there's only one, W1). If you want to be correct, you have to
visit all W1's nodes and compute the new bbox - this covers the case when
the N1 was an extreme node and by moving it, the bbox shoudl shrunk. Thus N^2.
You can opt to err on the safe side by only checking whether the bbox is now
larger after the move, this would slash the cost back to O(N).
With the queue, you're at similar complexity while staying exact. Moreover,
there are relations and if you want to track their bounds too, and when
there's a hierarchy of them, oh well ...

>> Also, possibly traversing a large hierarchy
>> of relations (there is one such in Germany, covering all the 
>> motorways, boundaries and so on)
>> each time won't be nice too. Safer is to:
>> 1. Add the node to a queue. Period. Full stop.
>> OK, 2. before each index inquiry, collect all the primitives 
>> influenced by the queue content
>> and update them only once.
>>   
> Are you talking about transient operations (like repaints during a drag 
> operation) with a "commit" into the index after the drag ended here, or 
> about longer-lived entries in this queue?

No, I do all the updates synchronously during the drag (I can afford it, so far).
That is:
1. the user starts dragging (a large forest)
2. First node moved event comes, node is added to a queue, repaint scheduled
3. Another node moved -> queue
...
4002. Last node moved -> queue
4003. Repaint comes, asks index for the data on the screen
4004. Index finds its toUpdate queue nonempty, updates
     all relevant elements at once
4005. view is repaited after the first partial move
4006. user keeps moving -> goto 2

Keeping the affected entities aside and "commit the index" only when the user
finishes modification would work too, but you'll need a channel for telling
the index about it. And that would be mixing data view and controller stuff
in a way I don't like ;-)

Note: I was also playing with an idea of having everything indexed on-disk
and keep only the modified things (and a small cache) in RAM, but such a design
would only be dictated by completely different scalability requirements...

-- 
Petr "Nenik" Nejedly, NetBeans/Sun Microsystems, http://www.netbeans.org
355/113 -- Not the famous irrational number PI, but an incredible simulation!