Smoothing road geometry

• US 9,355,476 B2
• Filed: 09/30/2012
• Issued: 05/31/2016
• 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
• Primary Examiner(s): Hoang, Peter
• Application Number:
  US13/632,001
• Publication Number:
  US 20130328916A1
• Time in Patent Office: 1,339 Days
• Field of Search: None
• US Class Current: 1/1
• 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. For a mapping service, a method comprising:

receiving a road graph comprising a plurality of roads for a map region, each road comprising one or more road segments combined together, each road segment comprising a plurality of vertices, wherein the vertices for the road segments of each road define a centerline of the road;

automatically identifying a bend in the centerline of a particular road that is at least a threshold angle, wherein a segment of the particular road that includes at least a portion of the identified bend has a defined speed limit;

defining a threshold distance by which a vertex can move based on the speed limit of said segment of the particular road; and

based on the defined threshold distance, automatically modifying the vertices of said segment of the particular road around the identified bend in order to smooth the road.

2. The method of claim 1, wherein the defined threshold distance is larger for roads with higher speed limits than for roads with lower speed limits.

3. The method of claim 1, wherein said segment of the particular road is a first road segment, wherein the bend is identified at a meeting of the first road segment and a second road segment.

4. The method of claim 1, wherein the bend is identified at a location within said segment of the particular road.

5. The method of claim 1, wherein automatically modifying the vertices of said segment of the particular road comprises using Laplacian smoothing within a particular distance of the bend to move the vertices near the bend.

6. The method of claim 1, wherein the automatic modification is performed prior to generating geometries for the road graph.

7. The method of claim 1, wherein the road segments comprise metadata defining road properties, wherein the defined threshold distance is further based at least partly on metadata of said segment of the particular road.

8. A non-transitory 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 comprising a plurality of roads for a map region, each road comprising one or more road segments combined together, each road segment comprising a plurality of vertices, wherein the vertices for the road segments of each road define a centerline for the road;

automatically identifying a bend in the centerline of a particular road that is at least a threshold angle, wherein a segment of the particular road that includes at least a portion of the identified bend has a defined speed limit;

defining a threshold distance by which a vertex can move based on the speed limit of said segment of the particular road; and

based on the defined threshold distance, automatically modifying the vertices of said segment of the particular road around the identified bend in order to smooth the road.

9. The non-transitory machine readable medium of claim 8, wherein roads with higher speed limits are allowed larger vertex movements than roads with lower speed limits.

10. The non-transitory machine readable medium of claim 8, wherein said segment of the particular road is a first road segment, wherein the bend is identified at a meeting of the first road segment and a second road segment.

11. The non-transitory machine readable medium of claim 8, wherein the set of instructions for automatically modifying the vertices of said segment 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.

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

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; and

for each corner formed between two geometries at the junction,

determining whether to perform a smoothing operation based on an angle formed at the corner;

when the angle is greater than a first threshold angle, modifying the two geometries to smooth the corner by applying a first smoothing operation;

when the angle is greater than a second threshold angle and less than the first threshold angle, modifying the two geometries to smooth the corner by applying a second smoothing operation; and

when the angle is greater than a third threshold angle and less than a fourth threshold angle, modifying the two geometries to smooth the corner by applying a third smoothing operation.

13. The non-transitory machine readable medium of claim 12, wherein a second set of road segments meet at a second junction, wherein the second set of road segments comprises only a first road segment and a second road segment that are parts of the same road.

14. The non-transitory machine readable medium of claim 13, wherein the initial set of geometries is a first initial set of geometries, wherein the first and second road segments have different widths, the program further comprising sets of instructions for:

generating a second initial set of geometries for the second set of road segments; and

modifying the geometries of the second initial set by tapering at least one side of the first road segment to meet a side of the second road segment.

15. The non-transitory machine readable medium of claim 14, 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 9020 angles in the second side of the road.

16. The non-transitory machine readable medium of claim 14, wherein the first road segment is wider than the second road segment.

17. The non-transitory machine readable medium of claim 14, wherein the first road segment is narrower than the second road segment.

18. The non-transitory machine readable medium of claim 12, wherein the initial geometry for a particular road segment comprises two road sides parallel to a centerline of the road segment.

19. The non-transitory machine readable medium of claim 12, wherein the set of road segments comprises first, second, and third road segments.

20. The non-transitory machine readable medium of claim 19, wherein each pair of subsequent road segments in the junction forms a corner.

21. The non-transitory machine readable medium of claim 20, wherein for the corner formed by the first and second road segments, the two geometries are smoothed in order to remove an unrealistic discontinuity between the first and second road segments.

22. The non-transitory machine readable medium of claim 12, wherein the first smoothing operation tapers a side of a first road segment to line up with a side of a second road segment.

23. The non-transitory machine readable medium of claim 12, wherein the second smoothing operation projects a side of a first road segment to meet a side of a second road segment.

24. The non-transitory machine readable medium of claim 12, wherein the third smoothing operation clips a side of a first road segment to avoid overshooting a side of a second road segment.

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

a set of processing units; and

a set of machine-readable media storing;

a road graph generation module which when executed by at least one of the processing units aggregates road segments and junctions into roads;

a road smoothing module which when executed by at least one of the processing units identifies angled bends in aggregated roads and modifies vertices of the roads in order to smooth the angled bends;

a geometry growing module which when executed by at least one of the processing units generates initial geometries for road segments in a road graph; and

a geometry smoothing module which when executed by at least one of the processing units smooths corners between pairs of geometries that intersect each other based on angles formed at the corners in order to generate more realistic road geometries, wherein the geometry smoothing module smooths a particular corner by performing (i) a first smoothing operation when a particular angle of the particular corner is greater than a first threshold angle, (ii) a second smoothing operation when the particular angle is greater than a second threshold angle and less than the first threshold angle, and (iii) a third smoothing operation when the particular angle is greater than a third threshold angle and less than a fourth threshold angle.

26. The system of claim 25, wherein the geometry growing module defines vertices for the road segment geometries.

27. The system of claim 26, wherein the geometry smoothing module modifies the road segment geometry vertices defined by the geometry growing module.