VECTOR ROAD NETWORK SIMPLIFICATION

• US 20130332476A1
• Filed: 11/05/2012
• Published: 12/12/2013
• Est. Priority Date: 06/08/2012
• Status: Abandoned Application

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Sinha, Pinaki, Laprise, Denis
• Application Number:
  US13/669,291
• Publication Number:
  US 20130332476A1
• Time in Patent Office: Days
• US Class Current: 707/756
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Apparatus and method for simplifying vector road network data. For example, a method in accordance with one embodiment comprises: receiving input data comprising a vector road network specifying vertices and edges; removing discontinuities in paths defined by the vertices and edges; chaining adjacent edges, the chain reducing the number of vertices and producing a set of paths; merging spatially proximal paths to create a set of merged paths; and determining a set of reduced paths from the set of merged paths.

Claims

1. A machine implemented method comprising:

receiving input data comprising a vector road network specifying vertices and edges;

removing discontinuities in paths defined by the vertices and edges;

chaining adjacent edges, the chain reducing the number of vertices and producing a set of paths;

merging spatially proximal paths to create a set of merged paths; and

determining a set of reduced paths from the set of merged paths.

2. The method as in claim 1 wherein removing discontinuities comprises:

determining whether each discontinuity is perceptible at a current zoom level;

keeping the discontinuity if it is perceptible at a current zoom level; and

removing or replacing the discontinuity if it is not perceptible at a current zoom level.

3. The method as in claim 2 wherein replacing the discontinuity comprises replacing the discontinuity with linear road elements.

4. The method as in claim 1 further comprising:

iterating through each vertex to determine whether the vertex may be considered a road network extrema and, if so, then storing the vertex as an extrema in the vector road network.

5. The method as in claim 1 wherein chaining adjacent edges comprises:

traversing the input data using the vectices; and

assigning edges to paths, ensuring that no edge is included in more than one path.

6. The method as in claim 1 wherein merging spatially proximal paths comprises:

identifying a nearest neighbor edge for each edge in a first path, each nearest neighbor edge being associated with a path other than the first path;

for each nearest neighbor edge, identifying its path;

evaluating each path having a nearest neighbor edge in relation to the first path; and

combining the first path with one or more of the other paths having the identified nearest neighbor edges based on the evaluation.

7. The method as in claim 6 wherein evaluating comprises determining if the paths map to the same pixels or pixels which are at a small threshold apart.

8. The method as in claim 6 wherein evaluating comprises choosing a centerline between the first path and the other paths.

9. The method as in claim 1 wherein determining a set of reduced paths comprises:

building a set of super paths from the set of merged paths.

10. The method as in claim 9 wherein building the super paths comprises ensuring that every edge is a member of one and only one super path.

11. The method as in claim 9 wherein building the super paths comprises attempting to find a least number of paths that covers the entire vector road network which are edge disjoint.

12. A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform the operations of:

receiving input data comprising a vector road network specifying vertices and edges;

removing discontinuities in paths defined by the vertices and edges;

chaining adjacent edges, the chain reducing the number of vertices and producing a set of paths;

merging spatially proximal paths to create a set of merged paths; and

determining a set of reduced paths from the set of merged paths.

13. The non-transitory machine-readable medium as in claim 12 wherein removing discontinuities comprises:

determining whether each discontinuity is perceptible at a current zoom level;

keeping the discontinuity if it is perceptible at a current zoom level; and

removing or replacing the discontinuity if it is not perceptible at a current zoom level.

14. The non-transitory machine-readable medium as in claim 13 wherein replacing the discontinuity comprises replacing the discontinuity with linear road elements.

15. The non-transitory machine-readable medium as in claim 12 further comprising:

iterating through each vertex to determine whether the vertex may be considered a road network extrema and, if so, then storing the vertex as an extrema in the vector road network.

16. The non-transitory machine-readable medium as in claim 12 wherein chaining adjacent edges comprises:

traversing the input data using the vectices; and

assigning edges to paths, ensuring that no edge is included in more than one path.

17. The non-transitory machine-readable medium as in claim 12 wherein merging spatially proximal paths comprises:

identifying a nearest neighbor edge for each edge in a first path, each nearest neighbor edge being associated with a path other than the first path;

for each nearest neighbor edge, identifying its path;

evaluating each path having a nearest neighbor edge in relation to the first path; and

combining the first path with one or more of the other paths having the identified nearest neighbor edges based on the evaluation.

18. The non-transitory machine-readable medium as in claim 17 wherein evaluating comprises determining if the paths map to the same pixels or pixels which are at a small threshold apart.

19. The non-transitory machine-readable medium as in claim 17 wherein evaluating comprises choosing a centerline between the first path and the other paths.

20. The non-transitory machine-readable medium as in claim 12 wherein determining a set of reduced paths comprises:

building a set of super paths from the set of merged paths.

21. The non-transitory machine-readable medium as in claim 20 wherein building the super paths comprises ensuring that every edge is a member of one and only one super path.

22. The non-transitory machine-readable medium as in claim 20 wherein building the super paths comprises attempting to find a least number of paths that covers the entire vector road network which are edge disjoint.