On Sat, 2009-09-12 at 17:58 +0100, Robert Scott wrote: > On Saturday 12 September 2009, Dave Hansen wrote: > > > > I've been hacking on the JOSM validator plugin for a while. One of the > > repeating "hard problems" that comes up are doing the UnconnectedWays tests. > > You need to do searches for every segment in a way to see if there are any > > nearby nodes. This generally means that you do a number of searches on the > > same order as the number of nodes that you have. > ... > > I realize this is quite a crude reply to such a detailed email. > > Did you investigate kd-trees at all? > > http://en.wikipedia.org/wiki/Kd_tree
Nope. I did some searching to find multidimensional search algorithms before I started this, but none of them seemed too horribly nice. kd-trees do like quite nice. I do believe what I've implemented is relatively close to what they do, though. They have the advantage that they split in a single dimension at each level in the tree. QuadBuckets are hard-coded for 2 dimensions and just basically split into those two dimensions at once. But, I think there is a lot of similarity. It also looks like kd-trees are intelligent about the values at which they decide to split. This means that if you have a bunch of entries all bunched up into one end of a bucket and you split it, you'll always get them split in half. QuadBuckets will instead force a bunch more splits until the buckets are well-split. QuadBuckets are stupid about where the split: they only do it into geometric quarters of the original bucket. I basically chose the algorithm that I did since it modeled something else that I and other OSMers are familiar with. It's even possible that we could use the quadtile indexes in a way to make communication with the DB server faster, although I'm using slightly different calculations than it is as it stands now. If someone knows of any existing Java kd-tree implementations, I'd be happy to look into it and see if it could be applied here. I love nothing more than to throw my own code away. Seriously. ;) -- Dave _______________________________________________ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
