|Re: O.T. What kind of math?|
Message #4 Posted by C.Ret on 27 Dec 2009, 7:08 p.m.,
in response to message #1 by designnut
Yes, the GPS has the latitude and longitude coordinates of your position acquired nearly every seconds and the latitude/longitude coordinates of your destination.
The road navigation GPS also have now on board map with the most detail of roads, intersections and a large bunch of points of interest. These maps are vectorial maps since they are draw using latitude/longitude coordinate, length and heading of road leg, as well as coordinate of intersection, town, point of interest, also contain street name, the road nomenclature, road categories and same other data concerning one-way roads and other circulation constrains.
This makes a lot of digital data, making that the full country maps are weighting several Go now. All this stuff is present in the map to allow precise drawing in the very probable case you decide to zoom in. But all these data are not used to compute a route.
One may be surprise that route computation is so quick at initial full trip computation as well as on road computation, as soon as the driver leave the planned route. Even with low speed processor (which generally share time with several internal functions concerning GPS signal processing, display and other user interface touch screen, etc… a GPS with 400 Mhz processor seems to be a power full one) and huge among of data in the vetorial map. These amazing little boxes still use a fraction of second to compute or re-compute the route !
The algorithm’s performance and the math involved there are of secondary importance. The high computation speed is mainly due to pre-compute link tables stored in the maps, which make that the GPS have not to carry the full process of a complete Drijska’s method, not to run all the heuristic, nor to evaluate a mountain of combinations. The GPS is mainly using a pre-computed look-up table that summarizes and regroups directions of the map at the appropriate scale.
This make that the computation of a trip following main roads or highways even on a long distance is much more fast than the computation of a short trip of a few tens of miles in a map’s region were no pre-computed table exist (or only incompletely).
The same, when the driver leave the planned route. The GPS rapidly compute a new partial route to the next node present in the already scanned pre-computed links table, never (or rarely) the GPS have to compute a full new route from crash. Sometime, depending of the region where you are travelling in, the GPS propose strange route on the fly with illogic or unnecessary detours.
Of course, the exact process vary from one model or brand of GPS. As well, the efficiency greatly relies of the data organization into the map and how well is all the system organizes altogether. For sure, the pre-compute links table are build up during map compilation using the Dijstra method or one dedicated method deduce from it.