Skip to content
This repository has been archived by the owner on Mar 1, 2021. It is now read-only.

findNClosest fails for large measurementErrorSigma #65

Open
kodonnell opened this issue Sep 11, 2016 · 5 comments
Open

findNClosest fails for large measurementErrorSigma #65

kodonnell opened this issue Sep 11, 2016 · 5 comments

Comments

@kodonnell
Copy link
Contributor

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
Copy link
Member

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
Copy link
Contributor Author

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
Copy link
Member

karussell commented Sep 12, 2016

(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 graphhopper/graphhopper#221 and graphhopper/graphhopper#232

@kodonnell
Copy link
Contributor Author

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
Copy link
Member

karussell commented Sep 12, 2016

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

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants