Smoothing Road Geometry

• US 20130328916A1
• Filed: 09/30/2012
• Published: 12/12/2013
• Est. Priority Date: 06/06/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Arikan, Okan, Dumont, Vincent, Chen, Billy P., Blumenberg, Christopher
• Granted Patent: US 9,355,476 B2
• Time in Patent Office: Days
• US Class Current: 345/619
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 7/0004 Industrial image inspection
• CPC Class Codes: G09G 5/00 Control arrangements or circuits for visual indicators common to cathode-ray tube indicators and other visual indicators image data processing or generation, in general G06T

Abstract

Some embodiments provide a method for a mapping service. For a set of road segments that intersect at a junction in a map region, the method generates an initial set of geometries for use in generating downloadable map information for the map region. For each corner formed by the geometries at the junction, the method determines whether to perform a smoothing operation. When a particular corner meets a set of criteria, the method modifies the geometries of at least one road segment to smooth the corner.

Claims

1. A machine readable medium storing a program for execution by at least one processing unit, the program comprising sets of instructions for:

receiving a road graph for a map region, the road graph comprising a plurality of roads, each road comprising a plurality of vertices that define a centerline of the road;

automatically identifying a bend in the centerline of a particular road that is at least a threshold angle; and

automatically modifying the vertices of the particular road around the identified bend in order to smooth the road.

2. The machine readable medium of claim 1, wherein each road comprises a plurality of road segments combined together, wherein the road segments store the vertex information to define the centerline for the road.

3. The machine readable medium of claim 2, wherein the bend is identified at a meeting of a first road segment and a second road segment.

4. The machine readable medium of claim 2, wherein the bend is identified at the middle of a road segment.

5. The machine readable medium of claim 1, wherein the set of instructions for automatically modifying the vertices of the particular road comprises a set of instructions for using Laplacian smoothing within a particular distance of the bend to move the vertices near the bend.

6. The machine readable medium of claim 1, wherein a segment of the particular road that includes the identified bend has a speed limit, wherein the set of instructions for automatically modifying the vertices comprises a set of instructions for defining a threshold distance by which a vertex can move based on the speed limit of the segment of the particular road.

7. The machine readable medium of claim 6, wherein roads with higher speed limits are allowed larger vertex movements than roads with lower speed limits.

8. The machine readable medium of claim 1, wherein the automatic modification is performed prior to generating geometries for the road graph.

9. For a mapping service, a method comprising:

for a set of road segments that intersect at a junction in a map region, generating an initial set of geometries for use in generating downloadable map information for the map region;

for each corner formed by the geometries at the junction, determining whether to perform a smoothing operation; and

when a particular corner meets a set of criteria, modifying the initial geometries of at least one road segment to smooth the corner.

10. The method of claim 9, wherein the set of road segments comprises only a first road segment and a second road segment that are parts of the same road

11. The method of claim 10, wherein the first and second road segments have different widths and the modification to the geometries comprises tapering at least one side of the first road segment to meet a side of the second road segment.

12. The method of claim 11, wherein prior to modification the geometry for the first road segment aligns with the geometry for the second road segment on a first side of the road at the junction and does not align with the geometry for the second road segment on a second, opposite side of the road, forming unrealistic 90°

angles in the second side of the road.

13. The method of claim 11, wherein the first road segment is wider than the second road segment.

14. The method of claim 11, wherein the first road segment is narrower than the second road segment.

15. The method of claim 9, wherein the initial geometry for a particular road segment comprises two road sides parallel to a centerline of the road segment.

16. The method of claim 9, wherein the set of road segments comprises first, second, and third road segments.

17. The method of claim 16, wherein each pair of subsequent road segments in the junction forms a corner.

18. The method of claim 17, wherein for the corner formed by the first and second road segments, modifying the geometries comprises modifying one of the first and second road segments based on an angle between the first and second road segments.

19. A mapping service system for generating map tiles, the system comprising:

a road graph generation module for aggregating road segments and junctions into roads;

a road smoothing module for identifying angled bends in aggregated roads and modifying vertices of the roads in order to smooth the angled bends;

a geometry growing module for generating initial geometries for road segments in a road graph; and

a geometry smoothing module for smoothing intersections of geometries in order to generate more realistic road geometries.

20. The system of claim 19, wherein the geometry growing module is for defining vertices for the road segments.

21. The system of claim 20, wherein the geometry smoothing module is for modifying the vertices defined by the geometry growing module.