Generalization of features in a digital map using round number coordinates
First Claim
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.
12 Assignments
0 Petitions
Accused Products
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.
-
Citations
13 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13)
-
Specification