[josm-dev] Reverse lookups

Karl Guggisberg karl.guggisberg at guggis.ch
Fri Oct 9 06:54:21 BST 2009


> It is way faster than iterating through the data set.  It's also much more
space efficient than keeping an explicit map.  
For ways and nodes that's great and if we can speed up redraw() even the
better. 

Reverse lookup for relation members is probably different. A spatial index
won't help here. We'll need a kind of backreferences from members to
relations. 

-- Karl 

-----Ursprüngliche Nachricht-----
Von: Dave Hansen [mailto:dave at sr71.net] 
Gesendet: Freitag, 9. Oktober 2009 00:47
An: karl.guggisberg at guggis.ch
Cc: 'josm-dev'
Betreff: Reverse lookups

I've been using this code for a while to speed up JOSM validator tests:

	http://www.mail-archive.com/josm-dev@openstreetmap.org/msg00265.html

What I do is just destroy the entire reverse lookup table each time the
DataSet changes.  It works for batched operations, but reverts to sucking
each time that the data is modified.

I just experimented with replacing the explicit HashMap<Node,List<Way>> with
something that uses the QuadBuckets search functionality instead.
It's pretty simple:

   public List<Way> waysUsingNode(Node n)
    {
        QuadBuckets<Way> qb = (QuadBuckets<Way>)ds.ways;
        List<Way> possible_ways = qb.search(n.getCoor(), 0.000001);
        List<Way> result = new ArrayList<Way>();
        for (Way w : possible_ways) {
            if (!w.containsNode(n))
                continue;
            result.add(w);
        }
        return result;
    }

It works because I calculate a bounding box for each node and all of its
nodes are guaranteed to be contained inside the box.  

It is way faster than iterating through the data set.  It's also much more
space efficient than keeping an explicit map.  

BTW, here's the patch for using QuadBuckets for way storage:

	http://josm.openstreetmap.de/ticket/3671

This could also potentially make click processing much faster.  We can also
optimize redraw() operations when zoomed in on a large data set by doing a
search instead of iterating across the entire data set.

-- Dave





More information about the josm-dev mailing list