Generalization of Features In A Digital Map

• US 20070024624A1
• Filed: 07/26/2006
• Published: 02/01/2007
• Est. Priority Date: 07/26/2005
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Decarta (Uber Technologies, Inc.)
• Inventors: Poppen, Richard
• Granted Patent: US 7,859,536 B2
• Time in Patent Office: Days
• 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 points, the method comprising:

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

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

responsive to the chord from the first point to the second point being acceptable, creating a node representing the chord;

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

determining whether a transition from a chord represented by the first node to a chord represented by the second node 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 point in the polyline to a node including the last 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.

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 a transition from a chord represented by the first node to a chord represented by the second node is acceptable further comprises:

determining a first angle formed by the polyline at the transition point;

determining a second angle formed by the chords at the transition point;

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 points, the computer program product stored on a 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 points in the polyline;

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

responsive to the chord from the first point to the second point being acceptable, creating a node representing the chord;

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

determining whether a transition from a chord represented by the first node to a chord represented by the second node 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 point in the polyline to a node including the last 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. A system for generalizing features of a digital map, the feature including a polyline, the polyline including a plurality of points, the system comprising:

a node creation module adapted to create a set of nodes by, for each pair of points in the polyline;

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

responsive to the chord from the first point to the second point being acceptable, creating a node representing the chord;

a link creation module, coupled to the node creation module, adapted to create a set of links by, for each pair of nodes in which the second point in one node is the same point as the first point in the other node;

determining whether a transition from a chord represented by the first node to a chord represented by the second node is acceptable;

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

a cost assignment module, coupled to the link creation module and the node creation module, adapted to determine for each path from a node including the first point in the polyline to a node including the last point in the polyline, a cost of the path based on a cost associated with each node and a cost associated with each link; and

a path creation module, coupled to the cost assignment module, adapted to select as a simplified polyline the polyline represented by the path having the least cost.