Generalization of features in a digital map

• US 7,859,536 B2
• Filed: 07/26/2006
• Issued: 12/28/2010
• Est. Priority Date: 07/26/2005
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Decarta (Uber Technologies, Inc.)
• Inventors: Poppen, Richard F.
• Primary Examiner(s): Wu; Xiao M
• Assistant Examiner(s): Ma; Tize
• Application Number:
  US11/460,226
• Publication Number:
  US 20070024624A1
• Time in Patent Office: 1,616 Days
• Field of Search: 345441-443, 3409951-99528, 701/208
• US Class Current: 345/441
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges

Abstract

Generalization of features in a digital map is enabled by performing a simplification of polylines. A set of chords between points on a polyline is selected such that each chord does not violate specified rules such as maximum distance from the original polyline. If a chord is acceptable, a node representing the chord is created, described by the start and end points of the chord. For pairs of nodes created, a transition from the first node to the second node is evaluated to determine whether it is acceptable. In one embodiment, a transition is acceptable if the absolute value of the angle formed by the chords is within a threshold angle from the angle formed by the original polyline at that point. If the transition is acceptable, a link between the two nodes is established. A least-cost path through the graph is chosen, and a simplified polyline is then generated.

Claims

1. A method for generalizing a feature of a digital map, the feature including a polyline, the polyline including a plurality of shape points, the method comprising:

creating, by a computer, a set of nodes by, for each pair of shape points in the polyline;

determining, by the computer, whether a chord from the first shape point of the pair to the second shape point of the pair is acceptable;

responsive to the chord being acceptable, creating, by the computer, a node representing the chord;

creating, by the computer, a set of links by, for each pair of nodes in which the second shape point in one node is the same shape point as the first shape point in the other node;

determining, by the computer, a first angle, the first angle formed by the polyline at the shape point;

determining, by the computer, a second angle, the second angle formed by a transition from the chord represented by the first of the pair of nodes to the chord represented by the second of the pair of nodes;

comparing the first angle and the second angle to determine whether the transition having the second angle is acceptable;

responsive to the transition being acceptable, creating, by the computer, a link between the pair of nodes;

for each path from a node including the first shape point in the polyline to a node including the last shape point in the polyline, determining a cost of the path based on a cost associated with each node and a cost associated with each link; and

generating, by the computer, as a simplified polyline the polyline represented by the path having the least cost.

2. The method of claim 1, wherein the set of created nodes includes a first node, the first node having a first start point not on the polyline and a second point on the polyline, and a second node, the second node including the last point on the polyline and an end point not on the polyline.

3. The method of claim 1 wherein a chord from a first point of a pair of nodes in the polyline to a second point of the pair of nodes in the polyline is acceptable if a maximum distance between the polyline and the chord is less than a threshold amount.

4. The method of claim 1 wherein a chord from a first point of a pair of nodes in the polyline to a second point of the pair of nodes in the polyline is acceptable if a heading at each end of the chord deviates from a heading of the original polyline at that point by less than a threshold angle.

5. The method of claim 1 wherein a chord from a first point of a pair of nodes in the polyline to a second point of the pair of nodes in the polyline is acceptable if a number of points on the polyline between the first point of the pair of nodes and the second point of the pair of nodes is more than a threshold number.

6. The method of claim 1 wherein a chord from a first point of a pair of nodes in the polyline to a second point of the pair of nodes in the polyline is acceptable if the length of the chord is less than a threshold length.

7. The method of claim 1 wherein determining whether the transition having the second angle is acceptable further comprises:

responsive to the absolute value of the difference between the first angle and the second angle not exceeding a threshold amount, determining that the transition is acceptable.

8. The method of claim 7 wherein the threshold amount is 180 degrees.

9. The method of claim 1 wherein:

determining whether a chord is acceptable further comprises determining whether the chord intersects a forbidden map object; and

responsive to the chord intersecting the forbidden map object, determining that the chord is not acceptable.

10. A computer program product for generalizing a feature of a digital map, the feature including a polyline, the polyline including a plurality of shape points, the computer program product stored on a non-transitory computer readable medium and including instructions configured to cause a processor to carry out the steps of:

creating a set of nodes by, for each pair of shape points in the polyline;

determining whether a chord from the first shape point of the pair to the second shape point of the pair is acceptable;

responsive to the chord being acceptable, creating a node representing the chord;

creating a set of links by, for each pair of nodes in which the second shape point in one node is the same point as the first shape point in the other node;

determining a first angle, the first angle formed by the polyline in the shape point;

determining a second angle, the second angle formed by a transition from the chord represented by the first of the pair of nodes to the chord represented by the second of the pair of nodes;

comparing the first angle and the second angle to determine whether the transition having the second angle is acceptable;

responsive to the transition being acceptable, creating a link between the pair of nodes;

for each path from a node including the first shape point in the polyline to a node including the last shape point in the polyline, determining a cost of the path based on a cost associated with each node and a cost associated with each link; and

selecting as a simplified polyline the polyline represented by the path having the least cost.

11. The computer program product of claim 10, wherein the set of created nodes includes a first node, the first node having a first start point not on the polyline and a second point on the polyline, and a second node, the second node including the last point on the polyline and an end point not on the polyline.

12. The computer program product of claim 10, wherein a chord from a first point of a pair of nodes in the polyline to a second point of the pair of nodes in the polyline is acceptable if a maximum distance between the polyline and the chord is less than a threshold amount.

13. The computer program product of claim 10 wherein a chord from a first point of a pair of nodes in the polyline to a second point of the pair of nodes in the polyline is acceptable if a heading at each end of the chord deviates from a heading of the original polyline at that point by less than a threshold angle.

14. The computer program product of claim 10 wherein a chord from a first point of a pair of nodes in the polyline to a second point of the pair of nodes in the polyline is acceptable if a number of points on the polyline between the first point of the pair of nodes and the second point of the pair of nodes is more than a threshold number.

15. The computer program product of claim 10 wherein a chord from a first point of a pair of nodes in the polyline to a second point of the pair of nodes in the polyline is acceptable if the length of the chord is less than a threshold length.

16. The computer program product of claim 10 wherein determining whether the transition having the second angle is acceptable further comprises:

responsive to the absolute value of the difference between the first angle and the second angle not exceeding a threshold amount, determining that the transition is acceptable.

17. The computer program product of claim 16 wherein the threshold amount is 180 degrees.

18. The computer program product of claim 10 wherein:

determining whether a chord is acceptable further comprises determining whether the chord intersects a forbidden map object; and

responsive to the chord intersecting the forbidden map object, determining that the chord is not acceptable.