Navigation system

• US 9,068,853 B2
• Filed: 02/21/2013
• Issued: 06/30/2015
• Est. Priority Date: 02/22/2012
• Status: Active Grant

• Current Assignee: Harman Becker Automotive Systems GmbH (Samsung Group)
• Original Assignee: Harman Becker Automotive Systems GmbH (Samsung Group)
• Inventors: Strassenburg-Kleciak, Marek, Mitrakis, Stavros
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): HUYNH, LUAT T
• Application Number:
  US13/773,273
• Publication Number:
  US 20130218465A1
• Time in Patent Office: 859 Days
• Field of Search: 701/533, 701/431, 701/454, 701/461
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G09B 29/003 Maps

Abstract

A navigation system (NS) may include a processor that can retrieve geographic map data from a database, where the geographic map data includes polygonal chains. The processor can determine a straightness value, a length ratio, and/or an angle-to-length ratio for each of the polygonal chains based on segments and/or vertices of the polygonal chain. Also, a first class and a second class of the polygonal chains can be determined based on one or more of the three determined values for each of the polygonal chains. The first class may represent roads that are less winding than the second class, and such an attribute may be beneficial in selecting an optimal route.

Claims

1. A method, comprising:

retrieving, by a processor of a navigation system, geographic map data from a database, where the geographic map data includes at least two polygonal chains, where each of the at least two polygonal chains includes segments;

determining, by the processor, a straightness value for each of the at least two polygonal chains;

determining, by the processor, a first class and a second class of the at least two polygonal chains based on the straightness value for each of the at least two polygonal chains, the first class including a lower range of straightness values than that of the second class;

determining, by the processor, a route to a destination based on the determined class of the first class and the second class of the at least two polygonal chains; and

displaying the determined route on a display of the navigation system.

2. The method of claim 1, further comprising determining, by the processor, respective ranks for the first class and the second class of the at least two polygonal chains.

3. The method of claim 2, wherein determining, by the processor, the route to the destination based on the determined class of the at least two polygonal chains comprises determining, by the processor, the route based on the respective ranks.

4. The method of claim 1, where the straightness value for each of the at least two polygonal chains is an angle sum.

5. The method of claim 4, where the angle sum is a sum of each angle between each pair of adjacent segments of a polygonal chain.

6. The method of claim 4, where the angle sum is a sum of one or more angles between one or more pairs of adjacent segments of a polygonal chain.

7. The method of claim 4, wherein determining, by the processor, the route to the destination based on the determined class of the at least two polygonal chains comprises determining, by the processor, the route including a polygonal chain from the first class.

8. A method, comprising:

retrieving, by a processor of a navigation system, geographic map data from a database, where the geographic map data includes at least two polygonal chains, where each of the at least two polygonal chains includes segments;

determining, by the processor, a length ratio for each of the at least two polygonal chains;

determining, by the processor, a first class and a second class of the at least two polygonal chains based on the length ratio for each of the at least two polygonal chains, the first class including a lower range of length ratios than that of the second class;

determining, by the processor, a route to a destination based on the determined class of the first class and the second class of the at least two polygonal chains; and

displaying the determined route on a display of the navigation system.

9. The method of claim 8, further comprising determining, by the processor, respective ranks for the first class and the second class of the at least two polygonal chains.

10. The method of claim 9, wherein determining, by the processor, the route to the destination based on the determined class of the at least two polygonal chains comprises determining, by the processor, the route based on the respective ranks.

11. The method of claim 8, further comprising calculating the length ratio for each of the at least two polygonal chains based on a length of a segment directly connecting a starting vertex and an ending vertex of a polygonal chain and a sum of each segment length of the polygonal chain.

12. The method of claim 11, where the calculating of the length ratio for each of the at least two polygonal chains includes dividing the sum of each segment length of the polygonal chain by the length of the segment directly connecting the starting vertex and the ending vertex of the polygonal chain.

13. The method of claim 12, wherein determining, by the processor, the route to the destination based on the determined class of the at least two polygonal chains comprises determining, by the processor, the route including a polygonal chain from the first class.

14. A method, comprising:

retrieving, by a processor of a navigation system, geographic map data from a database, where the geographic map data includes at least two polygonal chains, where each of the at least two polygonal chains includes segments;

determining, by the processor, an angle-to-length ratio for each of the at least two polygonal chains;

determining, by the processor, a first class and a second class of the at least two polygonal chains based on the angle-to-length ratio for each of the at least two polygonal chains, the first class including a lower range of angle-to-length ratios than that of the second class;

determining, by the processor, a route to a destination based on the determined class of the first class and the second class of the at least two polygonal chains; and

displaying the determined route on a display of the navigation system.

15. The method of claim 14, further comprising determining, by the processor, respective ranks for the first class and the second class of the at least two polygonal chains.

16. The method of claim 15, wherein determining, by the processor, the route to the destination based on the determined class of the at least two polygonal chains comprises determining, by the processor, the route based on the respective ranks.

17. The method of claim 14, further comprising calculating the angle-to-length ratio for each of the at least two polygonal chains based at least on an angle sum of a polygonal chain.

18. The method of claim 17, further comprising calculating the angle-to-length ratio for each of the at least two polygonal chains further based on a length of a segment directly connecting a starting vertex and an ending vertex of the polygonal chain.

19. The method of claim 17, further comprising calculating the angle-to-length ratio for each of the at least two polygonal chains further based on a sum of each segment length of the polygonal chain.

20. The method of claim 14, further comprising calculating the angle-to-length ratio for each of the at least two polygonal chains based at least on an average angle of a polygonal chain, the average angle calculated by dividing the angle sum by a number of intermediate vertices of the polygonal chain.