MAP DATABASE HAVING VECTORS FOR DETERMINING DESTINATIONS, AND VECTOR DETERMINATION METHOD

• US 20110160995A1
• Filed: 12/10/2008
• Published: 06/30/2011
• Est. Priority Date: 12/10/2008
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: Tomtom North America Incorporated (TomTom NV)
• Inventors: Geilich, Michael, Snell, Duane
• Granted Patent: US 8,655,590 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3811 Point data, e.g. Point of Interest [POI]

Abstract

A method, database, memory computer readable medium and navigation device are disclosed. In at least one embodiment, the method includes projecting a plurality of known address points onto an address segment vector of a source map database, to create projection points; interpolating locations for addresses of the address points, to create corresponding interpolation points; and segmenting the address segment vector into a plurality of address sub-segment vectors, upon a distance between a projection point and a corresponding interpolation point exceeding a threshold distance. Embodiments include a memory including a digital map application database storing the address sub-segment vectors of the method, at least one of in place of and in addition to corresponding address segment vectors, upon an address segment vector being segmented; a navigation device including the memory; a digital map application database including a plurality of address segment vectors and a plurality of address sub-segment vectors and a computer readable medium including the digital map application database.

Claims

1. An automated method, comprising:

projecting a plurality of known address points onto an address segment vector of a map database, to create projection points;

interpolating locations for addresses of the address points, to create corresponding interpolation points; and

segmenting the address segment vector into a plurality of address sub-segment vectors, upon a distance between a projection point and a corresponding interpolation point exceeding a threshold distance.

2. The method of claim 1, comprising:

determining a relatively largest distance among distances between corresponding projection and interpolation points, wherein the segmenting is performed upon the determined relatively largest distance exceeding the threshold distance.

3. The method of claim 1, comprising:

determining an average distance between all projection point and corresponding interpolation point pairs, wherein the segmenting is performed upon the determined average distance exceeding the threshold distance.

4. The method of claim 2, wherein the projecting, interpolating and determining are performed for multiple segmenting into address sub-segment vectors, such that either

an average distance between projection points and corresponding interpolation points within each of the address sub-segment vectors is less than the threshold distance, or

the relatively largest distance within each of the address sub-segment vectors

5. The method of claim 1, wherein the threshold distance is set so as to allow only a maximum or relatively largest number of interpolation addresses to fall between a projection point and a corresponding interpolation point pair.

6. The method of claim 1, wherein the threshold distance is a distance function.

7. The method of claim 1, further comprising:

storing the plurality of address sub-segment vectors in the map database, at least one of in place of and in addition to a corresponding address segment vector.

8. The method of claim 1, further comprising:

storing, upon the distance not exceeding the threshold distance for the address segment vector, the address segment vector without further segmenting.

9. The method of claim 2, further comprising:

storing, upon the determined relatively largest distance not exceeding the threshold distance for an address segment vector or address sub-segment vector, the address segment vector or address sub-segment vector without further segmenting.

10. The method of claim 4, further comprising:

storing, upon the determined average distance not exceeding the threshold distance for an address segment vector or address sub-segment vector, the address segment vector or address sub-segment vector without further segmenting.

11. The method of claim 1, wherein the threshold distance is adjustable for different conditions.

12. The method of claim 1, wherein the segmenting is performed at least one point along the address segment vector or address sub-segment vector that reduces an average distance between all projection point and corresponding interpolation point pairs.

13. The method of claim 12, wherein the point is a projection point.

14. The method of claim 1, wherein an address segment vector corresponds to a street segment of one side of a street.

15. The method of claim 1, wherein an address segment vector corresponds to a street segment of both sides of a street.

16. The method of claim 1, wherein an address segment vector or address sub-segment vector is segmented at one of the projection points.

17. A memory, storing unsegmented address segment vectors and storing the address sub-segment vectors of the method of claim 1, at least one of in place of and in addition to corresponding address segment vectors, upon an address segment vector being segmented.

18. A navigation device including the memory of claim 17.

19. A computer readable medium, comprising:

a map database, the map database including a plurality of address segment vectors and a plurality of address sub-segment vectors, the plurality of the address sub-segment vectors being stored in the map database at least one of in place of and in addition to a corresponding address segment vector upon a distance between a projection point, corresponding to a known address point projected onto the address segment vector, and a corresponding interpolation point, corresponding to an interpolated location of an address of the address point, exceeding a threshold distance.

20. The computer readable medium of claim 19, wherein the map database includes the plurality of sub-segment vectors being stored at least one of in place of and in addition to a corresponding address segment vector, upon a relatively largest distance, among distances between corresponding projection and interpolation points, exceeding the threshold distance.

21. The computer readable medium of claim 19, wherein the map database includes further segmented address sub-segment vectors being stored at least one of in place of and in addition to a corresponding address sub-segment vector, until the relatively largest distance does not exceed the threshold distance.

22. The computer readable medium of claim 19, wherein the map database includes the plurality of sub-segment vectors being stored at least one of in place of and in addition to a corresponding address segment vector, upon an average distance, determined between all projection point and corresponding interpolation point pairs, exceeding the threshold distance.

23. The computer readable medium of claim 19, wherein the map database includes further segmented address sub-segment vectors being stored at least one of in place of and in addition to a corresponding address sub-segment vector, until an average distance between projection points and corresponding interpolation points of the address sub-segment vector is less than the threshold distance.

24. The computer readable medium of claim 19, wherein the threshold distance is set so as to allow only a maximum or relatively largest number of interpolation addresses to fall between a projection point and a corresponding interpolation point pair.

25. A map database, storable on a storage medium, comprising:

a plurality of address segment vectors; and

a plurality of address sub-segment vectors, the plurality of the address sub-segment vectors being stored in the map database at least one of in place of and in addition to a corresponding address segment vector upon a distance between a projection point, corresponding to a known address point projected onto the address segment vector, and a corresponding interpolation point, corresponding to an interpolated location of an address of the address point, exceeding a threshold distance.

26. The map database of claim 25, wherein the map database includes the plurality of sub-segment vectors being stored at least one of in place of and in addition to a corresponding address segment vector, upon a relatively largest distance, among distances between corresponding projection and interpolation points, exceeding the threshold distance.

27. The map database of claim 25, wherein the map database includes further segmented address sub-segment vectors being stored at least one of in place of and in addition to a corresponding address sub-segment vector, until the relatively largest distance does not exceed the threshold distance.

28. The map database of claim 25, wherein the map database includes the plurality of sub-segment vectors being stored at least one of in place of and in addition to a corresponding address segment vector, upon an average distance, determined between all projection point and corresponding interpolation point pairs, exceeding the threshold distance.

29. The map database of claim 25, wherein the map database includes further segmented address sub-segment vectors being stored at least one of in place of and in addition to a corresponding address sub-segment vector, until an average distance between projection points and corresponding interpolation points of the address sub-segment vector is less than the threshold distance.

30. The map database of claim 25, wherein the threshold distance is set so as to allow only a maximum or relatively largest number of interpolation addresses to fall between a projection point and a corresponding interpolation point pair.

31. A device, comprising:

a memory storing a map database, the map database including a plurality of address segment vectors and a plurality of address sub-segment vectors, the plurality of the address sub-segment vectors being stored in the map database at least one of in place of and in addition to a corresponding address segment vector upon a distance between a projection point, corresponding to a known address point projected onto the address segment vector, and a corresponding interpolation point, corresponding to an interpolated location of an address of the address point, exceeding a threshold distance; and

an output device to output a location of an input or selected address using the stored map database.

32. The device of claim 31, wherein the output device is at least one of a display, a text output device and an audible output device.

33. The device of claim 31, wherein the map database includes the plurality of sub-segment vectors being stored at least one of in place of and in addition to a corresponding address segment vector, upon a relatively largest distance, among distances between corresponding projection and interpolation points, exceeding the threshold distance.

34. The device of claim 31, wherein the map database includes further segmented address sub-segment vectors being stored at least one of in place of and in addition to a corresponding address sub-segment vector, until the relatively largest distance does not exceed the threshold distance.

35. The device of claim 31 wherein the map database includes the plurality of sub-segment vectors being stored at least one of in place of and in addition to a corresponding address segment vector, upon an average distance, determined between all projection point and corresponding interpolation point pairs, exceeding the threshold distance.

36. The device of claim 31, wherein the map database includes further segmented address sub-segment vectors being stored at least one of in place of and in addition to a corresponding address sub-segment vector, until an average distance between projection points and corresponding interpolation points of the address sub-segment vector is less than the threshold distance.

37. The device of claim 31, wherein the threshold distance is set so as to allow only a maximum or relatively largest number of interpolation addresses to fall between a projection point and a corresponding interpolation point pair.

38. The device of claim 31, wherein the device is a navigation device, the navigation device further comprising:

an input device to prompt input or selection of a travel destination; and

a processor to calculate a travel route to the input or selected travel destination, wherein the travel route calculation utilizes the stored map database and wherein the output device is useable to output the calculated travel route.

39. The navigation device of claim 38, wherein the navigation device is a portable navigation device.

40. The navigation device of claim 38, wherein the navigation device is an in-vehicle navigation device.

41. A system for providing a user with information corresponding to a desired location, comprising:

a map database including a plurality of address segment vectors and a plurality of address sub-segment vectors, the plurality of the address sub-segment vectors being stored in the map database at least one of in place of and in addition to a corresponding address segment vector upon a distance between a projection point, corresponding to a known address point projected onto the address segment vector, and a corresponding interpolation point, corresponding to an interpolated location of an address of the address point, exceeding a threshold distance; and

a processor, to retrieve, using an applications program, an interpolated location corresponding to an address segment vector or address sub-segment vector of the map database, in response to a query regarding the desired location.

42. A system according to claim 41, wherein the system comprises an Internet-based system.

43. A system according to claim 41, wherein the system comprises an in-vehicle navigation system.

44. A Geographical Information Systems (GIS) based applications program for providing a user with information corresponding to a desired place, comprising:

a map database including a plurality of address segment vectors and a plurality of address sub-segment vectors, the plurality of the address sub-segment vectors being stored in the map database at least one of in place of and in addition to a corresponding address segment vector upon a distance between a projection point, corresponding to a known address point projected onto the address segment vector, and a corresponding interpolation point, corresponding to an interpolated location of an address of the address point, exceeding a threshold distance.