Generalization of features in a digital map using round number coordinates

• US 8,243,060 B2
• Filed: 08/06/2008
• Issued: 08/14/2012
• 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.
• Primary Examiner(s): WANG, JIN CHENG
• Application Number:
  US12/187,341
• Publication Number:
  US 20090040229A1
• Time in Patent Office: 1,469 Days
• Field of Search: 345418-427, 345440-442, 3409951-99528
• US Class Current: 345/418
• 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, 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, by a computer, a set of nodes by, for each pair of candidate shape points;

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 candidate shape point in one node is the same point as the first candidate shape point in the other node;

identifying, by the computer, an original shape point on the polyline corresponding to the candidate shape point;

determining, by the computer, a first angle, the first angle formed by the polyline at the original 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 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

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 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. The method of claim 1 wherein the candidate shape point and the identified original shape point on the polyline are the same point.

12. 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 non-transitory 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 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 candidate shape point in one node is the same point as the first candidate shape point in the other node;

identifying an original shape point on the polyline corresponding to the candidate shape point;

determining a first angle, the first angle formed by the polyline at the original 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 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

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

13. The computer program product of claim 12 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.