Revision 74c2347...

Go back to digest for 24th April 2011

Optimization in Educational

Dennis Nienhüser committed changes in [marble] /lib/routing:

Optimize the calculation of the closest point on the route.

Make use of the bounding box of each route segment as a quick estimate
of the minimum distance to a given point (current location). Cache the
last visited segment as an educated guess for the segment with the
smallest distance. Only calculate the distance to all points of a
segment if its minimal distance is smaller than the guessed minimum
distance. In the average case only one segment has to be fully
evaluated to determine the smallest distance.

Reduces the cpu consumption by about 9% (callgrind, large routes).

File Changes

Modified 4 files
  • /lib/routing
  •   src/Route.cpp
  •   src/Route.h
  •   src/RouteSegment.cpp
  •   src/RouteSegment.h
4 files changed in total