Generalization of Features in a Digital Map Using Round Number Coordinates

• US 20090040229A1
• Filed: 08/06/2008
• Published: 02/12/2009
• Est. Priority Date: 08/06/2007
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Decarta (Uber Technologies, Inc.)
• Inventors: Stitt, Andrew, Poppen, Richard F.
• Granted Patent: US 8,243,060 B2
• Time in Patent Office: Days
• US Class Current: 345/441
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

A system and processes for generalizing a collection of objects using points not necessarily part of the original objects are provided. Generalization of features in a digital map includes moving points to round number coordinates, while keeping topology correct and not moving points outside an allowed distance range, thus substantially reducing the size of the data so generalized. However, doing so requires moving points from the original polyline to new points. Generalization of polylines to points preferentially chosen from a relatively sparse set is described.

Claims

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

identifying a plurality of candidate shape points having round number coordinates, at least one of the plurality of candidate shape points not located on the polyline, and the plurality including at least one candidate terminal point associated with each terminal point of the polyline;

determining a position for each of the plurality of candidate shape points;

creating a set of nodes by, for each pair of candidate shape points;

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 a candidate first terminal point to a node including a candidate last terminal point, 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 each candidate point is located within a threshold distance of at least one of the original shape points.

3. The method of claim 1 wherein each candidate point falls within a bounding box centered on one of the original shape points.

4. The method of claim 3 wherein the bounding box is specified by a distance in an x direction and a distance in a y direction.

5. The method of claim 4 wherein the bounding box is specified by a distance in longitude and latitude.

6. The method of claim 1 wherein each candidate point is located within a threshold distance of the polyline.

7. The method of claim 1 wherein each candidate terminal point is located within a threshold distance of a terminal point of the polyline.

8. The method of claim 1 wherein the determined position for each of the plurality of candidate shape points includes a position number and an offset.

9. The method of claim 8 further comprising:

determining a point P on the polyline nearest to the candidate shape point;

responsive to the determined point P being an original shape point and located on the polyline between a second original shape point A and a third original shape point B;

determining that the position number of the candidate shape point is the position number of P;

given a line segment l_A at P, perpendicular to AP in a direction away from the interior angle of APB, a line segment l_B at P, perpendicular to PB, and a line segment l_cand from P to the candidate point, determining a ratio of the angle between l_A and l_cand to the angle between l_A and l_B; and

determining the offset of the candidate shape point as a function of the determined ratio.

10. The method of claim 9 wherein the function is one half of the determined ratio minus one quarter.

11. A computer program product for generalizing a feature of a digital map, the feature including a polyline, the polyline including a plurality of original shape 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:

identifying a plurality of candidate shape points having round number coordinates, at least one of the plurality of candidate shape points not located on the polyline, and the plurality including at least one candidate terminal point associated with each terminal point of the polyline;

determining a position for each of the plurality of candidate shape points;

creating a set of nodes by, for each pair of candidate shape points;

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 a candidate first terminal point to a node including a candidate last terminal point, 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.

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