METHOD AND SYSTEM FOR REDUCING SHAPE POINTS IN A GEOGRAPHIC DATA INFORMATION SYSTEM

• US 20120121206A1
• Filed: 12/31/2009
• Published: 05/17/2012
• Est. Priority Date: 05/04/2009
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: Tomtom North America Incorporated (TomTom NV)
• Inventors: Witmer, James Alan
• Granted Patent: US 9,068,849 B2
• Time in Patent Office: Days
• US Class Current: 382/291
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G09B 29/102 using electrical means

Abstract

Embodiments of the present invention provide a method of generating a shaped line in a geographic data information system, comprising selecting a first shaped line (100) in the geographic data information system, determining (205) a clothoid spline (300) representation of the shaped line, determining (210) a location of a first shape point corresponding to the clothoid spline (300) and determining (235) a location of a second shape point corresponding to the clothoid spline (300), wherein the location of the second shape point is determined (510) to be a maximum chord length from the first shape point within a predetermined tolerance.

Claims

1. A method of generating a shaped line in a geographic data information system, comprising:

selecting a first shaped line in the geographic data information system;

determining a clothoid spline representation of the shaped line;

characterised by;

determining a location of a first shape point corresponding to the clothoid spline; and

determining a location of a second shape point corresponding to the clothoid spline, wherein the location of the second shape point is determined to be a maximum chord length from the first shape point within a predetermined tolerance.

2. The method of claim 1, wherein, when the first shape point corresponds to a first clothoid section forming the clothoid spline and the second shape point is determined to extend beyond the end of the first clothoid section, the method includes determining whether to place the second shape point at an end of the first clothoid section according to a remainder of the tolerance.

3. The method of claim 2, wherein if the remainder of the tolerance is greater than a predetermined level, carrying the remainder over to a second clothoid section of the clothoid spline to determine the location of the second shape point.

4. The method of claim 1, wherein the determining of the maximum chord length comprises determining a curvature of a clothoid section forming the clothoid spline.

5. The method of claim 4, wherein the determining of the curvature of the clothoid section comprises determining an effective curvature e_f of the clothoid section according to:

6. The method of claim 1, wherein the maximum chord length is determined according to:

Length=2√

{square root over ((r²−

(r−

t²)))}

wherein r is a radius of curvature of the clothoid section and t is indicative of the tolerance.

7. The method of claim 1, comprising determining a location of one or more further shape points corresponding to the clothoid spline, wherein each shape point is determined to be a maximum chord length from a preceding shape point within the predetermined tolerance.

8. The method of claim 1, wherein the first and second shape points form a second shaped line comprising fewer shape points than the first shaped line.

9. The method of claim 1, wherein the first shape point represents a start of the clothoid spline (300).

10. The method of claim 1, wherein the first shaped line represents a roadway geographic data information system.

11. A computer program comprising computer executable code which, when executed on a computer, performs the method of claim 1.

12. A geographic data information system, comprising:

a data processor arranged to determine a clothoid spline representing a first shaped line;

characterised in that the data processor is arranged to determine two or more shape points forming a second shaped line corresponding to the clothoid spline by;

determining a location of a first shape point forming the second shaped line; and

determining a location of a second shape point forming the second shaped line, wherein the location of the second shape point is determined to be a maximum chord length from the first shape point within a predetermined tolerance.

13. The geographic data information system of claim 12, wherein, when the first shape point corresponds to a first clothoid section forming the clothoid spline and the second shape point is determined to extend beyond the end of the first clothoid section, the method includes determining whether to place the second shape point at an end of the first clothoid section according to a remainder of the tolerance.

14. The geographic data information system of claim 13, wherein if the remainder of the tolerance is greater than a predetermined level, carrying the remainder over to a second clothoid section to determine the location of the second shape point.

15. The geographic data information system of claim 12, wherein the maximum chord length is determined according to one of:

an effective curvature e_f of the clothoid section determined by;