Method to provide smoothness for road geometry data at intersections

• US 7,084,882 B1
• Filed: 04/06/2004
• Issued: 08/01/2006
• Est. Priority Date: 12/05/2000
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Kola, Mohan, Casino, Roy, Dorum, Ole Henry
• Primary Examiner(s): Tung, Kee M.
• Assistant Examiner(s): RAHMJOO, MANUCHER
• Application Number:
  US10/819,029
• Time in Patent Office: 847 Days
• Field of Search: 345441-443, 345/419, 345/629, 345/589, 345/590, 345/592, 345/611, 340/988, 701/208
• US Class Current: 345/589
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

A method for representing shapes of road segments is disclosed. The shape of a portion of road that spans at least one intersection is represented using a single continuous non-uniform B-spline. The single continuous non-uniform B-spline is divided into separate sections by knot insertion at each position corresponding to the location of a spanned intersection. The separate sections of the single continuous non-uniform B-spline are each re-parameterized into multiple separate continuous non-uniform B-splines. Then, data indicating each of the separate non-uniform B-splines is used to represent each of the corresponding road segments in the portion of road.

Claims

1. A computer-implemented method of representing shapes of road segments in a computer-readable medium comprising:

using a single continuous non-uniform B-spline to represent the shapes of two road segments that connect to each other at a location that corresponds to an intersection with a third road segment;

dividing the single continuous non-uniform B-spline into two separate sections by knot insertion at a position along the single continuous non-uniform B-spline that corresponds to the location of the intersection with the third road segment;

parameterizing the two separate sections of the single continuous non-uniform B-spline into two separate non-uniform B-splines; and

storing data indicating the two separate non-uniform B-splines to represent the two road segments respectively.

2. A geographic database that includes representations of road segments formed using the method of claim 1.

3. A computer-readable medium having stored thereon data representations of road segments formed using the method of claim 1.

4. The method of claim 1 wherein each non-uniform B-spline is described by a set of control points and knots.

5. The method of claim 1 wherein knot spacing along each non-uniform B-spline is non-uniform.

6. The method of claim 1 wherein knot spacing along each non-uniform B-spline is uniform.

7. The method of claim 1 wherein a parametric value of the knot insertion is based, at least in part, on a closest-point of a known intersection point projected onto the single continuous non-uniform B-spline.

8. The method according to claim 1 wherein the intersection is determined, at least in part, by a crossing point between the single continuous non-uniform B-spline and another B-spline connected to the single continuous non-uniform B-spline.

9. A computer database that represents road segments located in a geographic area,

wherein road segments are represented in the database by non-uniform B-splines to indicate shapes thereof;

and wherein the non-uniform B-splines used to represent the shapes of two road segments that connect to each other at a location that corresponds to an intersection with a third road segment have a property such that a single continuous non-uniform B-spline representing the shapes of the two road segments together, if divided into two separate sections by knot insertion at the position corresponding to the location of the intersection with the third road segment and parameterized, would form the two separate non-uniform B-splines.

10. A computer-readable medium having stored thereon data representations of road segments formed using the database of claim 9.

11. The database of claim 9 wherein each non-uniform B-spline is described by a set of control points and knots.

12. The database of claim 9 wherein knot spacing along each non-uniform B-spline is nonuniform.

13. The database of claim 9 wherein knot spacing along each non-uniform B-spline is uniform.

14. The database of claim 9 wherein a parametric value of the knot insertion is based, at least in part, on a closest-point of a known intersection point projected onto the single continuous non-uniform B-spline.

15. The database according to claim 9 wherein the intersection is based, at least in part, on crossing points between the single continuous non-uniform B-spline and another B-spline connected to the single continuous non-uniform B-spline.

16. A computer-implemented method of representing shapes of road segments in a computer-readable medium comprising:

using a single continuous non-uniform B-spline to represent the shapes of multiple segments of a road that connect to each other at locations that correspond to intersections of the road with other roads;

dividing the single continuous non-uniform B-spline into separate sections by knot insertion at positions along the single continuous non-uniform B-spline that corresponds to the locations of the intersections;

parameterizing the separate sections of the single continuous non-uniform B-spline into separate non-uniform B-splines; and

storing data indicating the separate non-uniform B-splines to represent each of the respective multiple segments of the road.

17. A geographic database that includes representations of road segments formed using the method of claim 16.

18. A computer-readable medium having stored thereon data representations of road segments formed using the method of claim 16.

19. The method of claim 16 wherein each non-uniform B-spline is described by a set of control points and knots.

20. The method of claim 16 wherein knot spacing along each non-uniform B-spline is non-uniform.

21. The method of claim 16 wherein knot spacing along each non-uniform B-spline is uniform.

22. The database of claim 16 wherein a parametric value of the knot insertion is based, at least in part, on a closest-point of a known intersection point projected onto the single continuous non-uniform B-spline.

23. The database according to claim 16 wherein the intersection is based, at least in part, on crossing points between the single continuous non-uniform B-spline and another B-spline connected to the single continuous non-uniform B-spline.

24. A computer-implemented method comprising:

parameterizing a shape of a first road segment and a second road segment into a single continuous B-spline, wherein the first road segment and the second road segment are connected to a third road segment at an intersection;

dividing the single continuous B-spline into two separate sections by knot insertion at the intersection;

re-parameterizing the two separate sections of the single continuous B-spline into two separate B-splines representing respectively a shape of the first road segment and a shape of the second road segment; and

storing data of the two separate B-splines to a cartographic database.

25. The method according to claim 24 wherein one of the two separate B-splines is connected to multiple road segments at multiple intersections further comprises:

diving the one of the two separate non-uniform B-splines into another two separate sections by knot insertion at each of the other intersections;

re-parameterizing the another two separate sections into another two separate non-uniform B-splines representing respectively a shape of two further road segments of the second road segment; and

storing data of the another two separate non-uniform B-splines to the cartographic database.

26. The method according to claim 24 wherein storing data of the two separate B-splines to a cartographic database further comprises:

storing at least portion of control points and knot values of the two separate B-spline to the cartographic database.

27. The method according to claim 24 wherein the single continuous B-spline is a single continuous non-uniform B-spline having non-uniform knot spacing.

28. The method according to claim 24 wherein the single continuous B-spline is a single continuous uniform B-spline having uniform knot spacing.

29. The method according to claim 24 wherein the B-splines are fitted to the road segment by applying any one or more regression approximation selected from a group of a least squares approximation, least trimmed squares approximation, and least median of squares approximation.

30. The method of claim 24 wherein the intersection is determined, at least in part, from a geographic database.

31. The method of claim 24 wherein a parametric value of the knot insertion is based, at least in part, on a closest-point of a known intersection point projected onto the single continuous B-spline.

32. The method according to claim 24 wherein the intersection is determined, at least in part, by a crossing point between the single continuous B-spline and another B-spline connected to the single continuous B-spline.

33. A geographic database that includes representations of road segments formed using the method of claim 24.

34. A computer-readable medium having stored thereon data representations of road segments formed using the method of claim 24.