search

ToureNPlaner / tourenplaner-server

The ToureNPlaner Server component
Apache License 2.0
1 stars 4 forks source link

Use something better for NNSearch #3

Open niklas88 opened 11 years ago

niklas88 commented 11 years ago

We need to fix the NNSearch to be fast even if there is no point close by. At the moment we just return node 0 when there is nothing in the sorounding grid cells. Look into adapting Sascha's octree code.

karussell commented 11 years ago

You can apply some "flood filling algorithm" so that every cell has some content like done here (instead of using only one integer per cell you should keep your arraylist per cell)

But I prefer being more precise, consuming less memory and accepting that some queries do not always return with a node so I've created a quadtree alternative with which I was able to import world wide data but still it has a meaningful size (less than 10% of the graph)