It is sometimes necessary to compare a plurality of routes determined with respect to map data. The routes may be between an origin and destination pair of locations. For example, it may be desired to compare routes between the origin and destination locations which have been calculated using different digital map data, such as map data from different sources or different versions of the same map data. The map data may be map data in different formats such as in a proprietary format of a mapping data company and another format.
It is known to compare curves, which may represent the routes, by determining a Fréchet distance δF between the two curves. The Fréchet distance is a measure of similarity between curves which takes into account the location and ordering of points along the curves. The Fréchet distance may be thought of as a man walking along one curve with a dog walking along another curve. The man is holding a lead connected to the dog. Both the man and dog may vary their speed, but neither can backtrack. The Fréchet distance is the shortest length of lead which may be used.
The journal article by Thomas Eiter and Heikki Mannila entitled “Computing Discrete Fréchet Distance”, Tech. Report CD-TR 94/96 (1994), Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria considered a discrete variation of the Fréchet distance for polygonal curves. The variation is known as the coupling distance δDF which looks at all possible couplings between end points of line segments of the polygonal curves. The coupling distance provides a good approximation to the Fréchet distance and represents an upper bound. The coupling distance is also quicker to calculate in O(pq) time compared to O(pq log2 pq) for the Fréchet distance wherein p and q are the number of segments on polygonal curves.
It is an object of embodiments of the invention to at least mitigate one or more of the problems of the prior art.
USPTO Backgrounds
USPTO Backgrounds