findNClosest fails for large measurementErrorSigma

[kodonnell]

Just something I noticed while trying to understand findNClosest (as I'll be refactoring it for another use) - it won't find all matches if measurementErrorSigma is too large. That is, it will at most only ever find all matches within +- deltaLat/deltaLon.

Not sure if this is intended behaviour or an actual bug. If it is a bug, I think it should be a simple fix to replace

for (int iteration = 0; iteration < 2; iteration++) {
    // should we use the return value of earlyFinish?
    index.findNetworkEntries(queryLat, queryLon, set, iteration);

with

while (!index.findNetworkEntries(queryLat, queryLon, set, iteration))

(from here).

[karussell]

Increasing the underlying "cell width" of the location index could fix this:

index.high_resolution=2000

Be aware of the slower lookup. Also I would rather avoid using an endless loop here.

[kodonnell]

OK, didn't realise that. However, the issue still stands: findNClosest does not (by design) find the closest within the tolerance ... it finds the closest within two iterations (as such), which may or may not be within tolerance.

Also I would rather avoid using an endless loop here.

You've kind of got one already. E.g. if the user sets index.high_resolution=1e10 then you'd effectively get an infinite loop (as two iterations might entail the entire graph). So I guess I'm trying to make the algorithm aware of the tolerance - "keep going until you've reached the tolerance, and no further". In theory, that's what the loop I suggested above does (if I've read findNetworkEntries correctly).

Of course, it's an edge case, and unlikely to benefit most people directly. (Unless, of course, only one iteration is needed instead of two - which would mean 9x less lookups?) Will leave it to you if you wish to close this.

[karussell]

(Unless, of course, only one iteration is needed instead of two - which would mean 9x less lookups?)

It is not too many loops. It is more complicated than one thinks, see https://github.com/graphhopper/graphhopper/pull/221 and https://github.com/graphhopper/graphhopper/issues/232

[kodonnell]

Ah, right. If it was just finding the closest, you could optimise it further (i.e. only check nearby tiles with r_min < distance to closest point in current tile). As an aside, isn't findNClosest misleading, as there's no N?

[karussell]

If it was just finding the closest, you could optimise it further (i.e. only check nearby tiles with r_min < distance to closest point in current tile)

That is what we do for normal LocationIndexTree search. What I meant is the problem regarding 'line rasterization' algorithm which requires neighbor search currently.

As an aside, isn't findNClosest misleading, as there's no N?

Yes, indeed. You can create an PR or issue for it