Method and system for computing road grade data

• US 6,856,897 B1
• Filed: 09/22/2003
• Issued: 02/15/2005
• Est. Priority Date: 09/22/2003
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navteq North America LLC (HERE Holding Corporation)
• Inventors: Alwar, Narayanan, Dorum, Ole Henry, Phuyal, Bishnu
• Primary Examiner(s): Hernandez, Olga
• Application Number:
  US10/667,769
• Time in Patent Office: 512 Days
• Field of Search: 701/208, 701/200, 701/206, 701/209, 701/25, 701/26, 731/78.R, 340/995.24
• US Class Current: 701/208
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method of obtaining data for a geographic database is disclosed. Data indicating a plurality of locations along roads including data indicating altitudes at the plurality of locations is provided. Road grade values for a plurality of subsections of the road are computed; each of the subsections is a portion of the road between two of the locations. A plurality of temporary change points are identified as joining two adjacent subsections having road grade values that differ by a value greater than a predetermined amount. Road grade values for each part of the road between adjacent temporary change points are computed. Consecutive parts of the road having road grade values that falls within a predetermined range are grouped into at least one constant road grade section. The geographic database stores data that define the constant road grade section.

Claims

1. A method of obtaining data for a geographic database comprising:

providing data indicating a plurality of locations along roads, including data indicating altitudes at the plurality of locations;

computing road grade values for a plurality of subsections of the road, each of the subsections being a portion of the road between two of the locations;

identifying a plurality of temporary change points, each of the temporary change points joins two adjacent subsections having road grade values that differ by a value greater than a predetermined amount;

computing a road grade value for each part of the road between adjacent temporary change points;

grouping consecutive parts of the road having road grade values that fall within a predetermined range into at least one constant road grade section; and

storing data that define the constant road grade section in the geographic database.

2. The method of claim 1 further comprising filtering the data to remove closely spaced locations.

3. The method of claim 1 further comprising deriving a smooth altitude profile along the road.

4. The method of claim 3 wherein the smooth altitude profile is derived using a least squares polynomial.

5. The method of claim 1 wherein the temporary change points include a plurality of zero-crossing points, wherein each of the zero-crossing points joins two adjacent subsections having road grade values that change from positive to negative.

6. The method of claim 5 wherein the temporary change points include a plurality of pseudo zero-crossing points, wherein each of the pseudo zero-crossing points joins two adjacent subsections between zero crossing points having road grade values that differ by a value greater than a predetermined amount.

7. The method of claim 6 wherein said pseudo zero-crossing points are identified by performing a rotational transformation of an altitude profile between two adjacent zero-crossing points.

8. The method of claim 1 further comprising:

determining whether the constant road grade section has a corresponding road distance less than a minimum distance; and

if the constant road grade section has the corresponding road distance less than said minimum distance, merging the constant road grade section with an adjacent constant road grade section.

9. A method of obtaining data for a geographic database comprising:

providing data indicating a plurality of locations along roads, including data indicating altitudes at the plurality of locations;

computing a road grade value for each of a plurality of subsections of said road, each of the subsections defined by two of the locations;

if the road grade values of adjacent subsections fall within a predetermined range, grouping the subsections into at least one constant road grade section; and

storing data that define the constant road grade section in the geographic database.

10. The method of claim 9 further comprising deriving a smooth altitude profile along the road.

11. The method of claim 9 further comprising identifying a grade change point corresponding to a position connecting adjacent constant road grade sections.

12. The method of claim 9 further comprising:

determining whether the constant road grade section has a corresponding road distance less than a minimum distance; and

if the constant road grade section has the corresponding road distance less than said minimum distance, merging the constant road grade section with an adjacent constant road grade section.

13. The method of claim 9 further comprising computing a road grade value for the constant road grade section.

14. The method of claim 13 further comprising:

if the road grade value of the constant road grade section is greater than a maximum road grade value, identifying the constant road grade section for human inspection.

15. The method of claim 13 further comprising:

if the road grade value of the constant road grade section is greater than a maximum road grade value, merging the constant road grade section with an adjacent constant road grade section.

16. The method of claim 9 further comprising using the data indicating altitudes as an input to a Hough Line Transform to determine straight line segments corresponding with the constant road grade sections.

17. A method of representing road geometry for a geographic database comprising:

providing data indicating a plurality of locations along roads, including data indicating altitudes at the plurality of locations;

computing a road grade value for each of a plurality of subsections of the road, each of said subsections defined by a pair of locations;

if said road grade values of adjacent subsections differ by a value greater than a predetermined amount, identifying said location between said adjacent subsections as a grade change point; and

storing data that define said grade change point in the geographic database.

18. The method of claim 17 identifying a road grade value for each constant road grade section between adjacent grade change points.

19. The method of claim 17 further comprising:

determining whether a road distance between adjacent grade change points is less than a minimum distance; and

if the road distance between adjacent grade change points is less than said minimum distance, eliminating one of said adjacent grade change points.