Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Approximate with DistancePlaneProjection #2983

Open
wants to merge 1 commit into
base: master
Choose a base branch
from
Open

Approximate with DistancePlaneProjection #2983

wants to merge 1 commit into from

Conversation

otbutz
Copy link
Contributor

@otbutz otbutz commented Apr 22, 2024

Fixes #2973

@karussell
Copy link
Member

karussell commented Apr 24, 2024 •
edited

Interesting, thanks.

The problem is that the larger the distances get the larger the differences get and because the plane distance is larger than the haversine distance the heuristic is no longer admissible (it will overestimate the cost of reaching the goal), which could lead to (more) correctness problems with the landmark algorithm IMO. But maybe my thinking is wrong here @easbar?

@otbutz
Copy link
Contributor Author

otbutz commented Apr 25, 2024

Wouldn't that be a positive side effect judging from the comments?

graphhopper/core/src/main/java/com/graphhopper/routing/lm/LMApproximator.java

Lines 123 to 125 in ff8f2b2

// Since both the LM and the beeline approximations underestimate the real remaining weight the larger one is
// more accurate. For example when the speed is reduced for all roads the beeline approximation adjusts automatically
// to the reduced global maximum speed, while the LM approximation becomes worse.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

LMApproximator overhead
2 participants
@otbutz @karussell