Method and apparatus for storing or displaying prespecified geometric objects and computer program product

• US 8,417,454 B2
• Filed: 11/21/2007
• Issued: 04/09/2013
• Est. Priority Date: 11/24/2006
• Status: Active Grant

• Current Assignee: Continental Automotive GmbH (Continental AG)
• Original Assignee: Continental Automotive GmbH (Continental AG)
• Inventors: Pfeifle, Martin, Sasse, Volker, Tantz, Uwe
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): LOUIE, WAE LENNY
• Application Number:
  US12/516,271
• Publication Number:
  US 20100070177A1
• Time in Patent Office: 1,966 Days
• Field of Search: 701/211, 701/212, 701/208, 701/400, 701/540, 345/619, 382/203, 382/305
• US Class Current: 701/540
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps

Abstract

To store geometric objects, a distance is determined from each prespecified objects to one other prespecified object. The distance represents a similarity of the corresponding prespecified objects. The prespecified objects are grouped together such that the prespecified objects are more similar with respect to prespecified geometric objects of the same group than with respect to objects of the other groups. For each group, a representative is ascertained, depending on the prespecified objects within the groups. The representatives of all the groups (are stored. In a representative fashion for the prespecified objects, only one identification of the prespecified object an indication of the corresponding representative of the prespecified object and values, by which a size and position of the corresponding representative is prespecified, is stored for each of the prespecified objects, depending on the size and the position of the corresponding prespecified objects.

Claims

1. A method for storing a plurality of prespecified geometric objects on a computer readable storage medium, the method comprising:

determining a respective distance between at least one of the prespecified geometric objects and each of the other plural prespecified geometric objects, said distance being representative of a similarity of corresponding ones of the plural prespecified geometric objects;

combining the plural prespecified geometric objects into one or more groups based at least in part on the determined distances such that the prespecified geometric objects in a same group are more similar to each other than to prespecified geometric objects in another group;

determining a representative for each group based at least in part on the prespecified geometric objects in each of the at least one groups, said representative meeting a quality criterion based at least in part on its similarity to the prespecified geometric objects in the corresponding group and on the distances between the representative and each of the combined prespecified geometric objects in the corresponding group;

storing each of the representatives for each of the at least one groups,

storing for each of the plural prespecified geometric objects only;

an identifier of the prespecified geometric object,

a reference to the corresponding representative of the prespecified geometric object, and

at least one value configured to prespecify a size and position of the corresponding representative based at least in part on a size and position of the corresponding prespecified geometric objects.

2. The method according to claim 1, wherein the prespecified geometric objects are arranged in a prespecified arrangement and the values prespecify the size and position of the representative in the prespecified arrangement.

3. The method according to claim 2, wherein the prespecified arrangement comprises a map and the prespecified geometric objects comprise at least one of road courses, buildings, squares, and natural objects.

4. The method according to claim 1, wherein the prespecified geometric objects comprise lines, and a method to determine a distance between two of the lines comprises:

shifting the lines such that a respective starting point of each of the two lines is at an origin of a coordinate system;

at least one of rotating, stretching, and compressing the lines such that a respective end point of each of the two lines is at a prespecified point on an axis of the coordinate system;

determining a separation between the two lines is at a plurality of prespecified support points; and

determining the distance between the two lines based at least in part on the separations between the two lines at the plural support points.

5. The method according to claim 1, wherein the prespecified geometric objects are combined into the groups such that respective paired distances between the prespecified geometric objects inside the group are less than a first distance threshold value.

6. The method according to claim 1, further comprising:

determining error values based at least in part on the distances between the prespecified geometric objects and their representatives;

assigning and the error values to the identifier of the prespecified geometric objects; and

storing the error values.

7. The method according to claim 1, further comprising:

determining a number of representatives based at least in part on a storage capacity of the computer readable storage medium,

wherein the prespecified geometric objects are combined into groups such that a number of groups corresponds to the possible number of representatives.

8. The method according to claim 1, wherein the prespecified geometric objects are elements displayed on a display of a navigation system.

9. An apparatus for storing prespecified geometric objects on a storage medium, the apparatus configured to:

determine a respective distance between each of a plurality of prespecified geometric objects and at least one other of the plural prespecified geometric objects, the distance being representative of similarity of the corresponding prespecified geometric objects;

combine the prespecified geometric objects into groups based at least in part on distances between the prespecified geometric objects such that the prespecified geometric objects are more similar to prespecified geometric objects in a same group than to prespecified geometric objects in another group;

determine a representative for each group based at least in part on the prespecified geometric objects inside the groups, said representative meeting a quality criterion based on its similarity to the prespecified geometric objects in the corresponding group, said quality criterion depending on the distances between the representative and the individual prespecified geometric objects in the corresponding group;

store the representatives of all groups;

store only an identifier of the prespecified geometric object for each of the prespecified geometric objects in a manner representative of the prespecified geometric objects, a reference to the corresponding representative of the prespecified geometric object and values which prespecify a size and position of the corresponding representative based on the size and position of the corresponding prespecified geometric objects.

10. The apparatus according to claim 9, wherein the apparatus is a navigation system.

11. A method for displaying prespecified geometric objects on a display apparatus, representatives being stored on a computer readable storage medium in a manner representative of the prespecified geometric objects, and values which are dependent on a size and position of the prespecified geometric objects being stored on the computer readable storage medium in a manner representative of a size and position of the representatives, the method comprising:

determining one of the representatives for each prespecified geometric object, said representative representing a group of prespecified geometric objects containing a corresponding prespecified geometric object and meeting a quality criterion with regard to its similarity to the prespecified geometric objects in the corresponding group, said quality criterion based at least in part on the distances between the representative and the individual prespecified geometric objects in the corresponding group;

determining a position and size of the representative for each of the determined representatives using the values; and

displaying the representative in the determined position and size.

12. The method according to claim 11, wherein the representative and the values assigned to the representative are determined based at least in part on an identifier stored in a manner representative of the prespecified geometric object, the identifier being assigned the representative and the values.

13. The method according to either of claim 12, wherein the arrangement comprises a map and the prespecified geometric objects comprise at least one of road courses, buildings, squares, and natural objects.

14. The method according to claim 11, wherein the prespecified geometric objects are arranged in a prespecified arrangement and the values prespecify the size and position of the representatives in the prespecified arrangement.

15. The method according to claim 11, wherein the prespecified geometric objects are elements displayed on a display of a navigation system.

16. An apparatus for displaying prespecified geometric objects on a display apparatus, representatives being stored on a storage medium in a manner representative of prespecified geometric objects, and values which are dependent on a size and position of the prespecified geometric objects being stored on the storage medium in a manner representative of a size and position of the representatives, the apparatus configured to:

determine one of the representatives for each prespecified geometric object, the representative representing a group of prespecified geometric objects containing the corresponding prespecified geometric object, and the representative meeting a quality criterion with regard to its similarity to the prespecified geometric objects in the corresponding group;

determine a position and size of the representative for each of the determined representatives using the values,

display the representative in the position and size determined.

17. The apparatus according to claim 16, wherein the apparatus is a navigation system.

18. A computer program product comprising a computer-readable storage unit with program instructions which can be executed by a computer configured that cause the computer to:

determine a respective distance between at least one of the prespecified geometric objects and each of the other plural prespecified geometric objects, said distance being representative of a similarity of corresponding ones of the plural prespecified geometric objects;

combine the plural prespecified geometric objects into one or more groups based at least in part on the determined distances such that the prespecified geometric objects in a same group are more similar to each other than to prespecified geometric objects in another group;

determine a representative for each group based at least in part on the prespecified geometric objects in each of the at least one groups, said representative meeting a quality criterion based at least in part on its similarity to the prespecified geometric objects in the corresponding group and on the distances between the representative and each of the combined prespecified geometric objects in the corresponding group;

store each of the representatives for each of the at least one groups; and

store for each of the plural prespecified geometric objects only;

an identifier of the prespecified geometric object,

a reference to the corresponding representative of the prespecified geometric object, and

at least one value configured to prespecify a size and position of the corresponding representative based at least in part on a size and position of the corresponding prespecified geometric objects.

19. A computer program product comprising a computer-readable storage unit with program instructions which can be executed by a computer that cause the computer to:

determine one of the representatives for each prespecified geometric object, said representative representing a group of prespecified geometric objects containing a corresponding prespecified geometric object and meeting a quality criterion with regard to its similarity to the prespecified geometric objects in the corresponding group, said quality criterion based at least in part on the distances between the representative and the individual prespecified geometric objects in the corresponding group;

determine a position and size of the representative for each of the determined representatives using the values; and

display the representative in the determined position and size.