Constructing road geometry

• US 9,396,563 B2
• Filed: 09/30/2012
• Issued: 07/19/2016
• Est. Priority Date: 06/06/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Arikan, Okan, Dumont, Vincent, Moore, Christopher D.
• Primary Examiner(s): Hoang, Peter
• Application Number:
  US13/632,000
• Publication Number:
  US 20130328924A1
• Time in Patent Office: 1,388 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. The method generates an initial set of geometries for a road graph defined for a map region. The road graph includes several road segments and junctions aggregated into roads. The method identifies an overlap between a first geometry of a first road segment and a second geometry of a second road segment. The first road segment and the second road segment are parts of different roads and do not meet at a junction. The method automatically modifies at least one of the first and second geometries in order to prevent the first geometry and second geometry from overlapping. In some embodiments each geometry is defined by a set of vertices that specify its boundaries. The method of some embodiments automatically modifies the vertices of at least one of the first and second geometries.

Claims

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

generating an initial set of geometries for a road graph defined for a map region, the road graph comprising a plurality of road segments and junctions aggregated into roads;

identifying an overlap between a first geometry of a first road segment and a second geometry of a second road segment, wherein the first road segment and the second road segment are parts of different roads and do not meet at a junction, wherein the first and second geometries comprise centerline vertices;

for at least two pairs of centerline vertices of the first and second geometries that are located adjacent to the overlap, applying a displacement amount that is proportional to an amount of overlap that is adjacent to each centerline vertex in the pairs, wherein the applied displacement amount is larger when the overlap is greater; and

based on the applied displacement amount, moving centerline vertices of the first and second geometries apart from each other in order to prevent the first geometry and second geometry from overlapping.

2. The machine readable medium of claim 1, wherein the centerline vertices of the geometries define the centerline of the road segment.

3. The machine readable medium of claim 2, wherein the set of instructions for moving the centerline vertices comprises a set of instructions for adjusting centerline of the first and second road segments away from each other.

4. The machine readable medium of claim 1, wherein each of the moved centerline vertices are displaced a different distance related to the amount of the overlap adjacent to the moved centerline vertices.

5. The machine readable medium of claim 3, wherein the centerline vertices within a particular distance are moved.

6. The machine readable medium of claim 1, wherein the program further comprises a set of instructions for, in response to the movement, reducing a width of at least one of the geometries.

7. The machine readable medium of claim 6, wherein a width of the first geometry and a width of the second geometry are reduced by an equal amount.

8. The machine readable medium of claim 6, wherein the width of only one of the geometries is reduced.

9. The machine readable medium of claim 1, wherein the program further comprises a set of instructions for automatically defining a road median geometry between the first road segment and the second road segment.

10. The machine readable medium of claim 9, wherein the program further comprises a set of instructions for determining whether the first road segment and second road segment are corresponding halves of a dual carriageway, wherein the road median geometry is only defined when the first road segment and second road segment are corresponding halves of a dual carriageway.

11. For a mapping service, a method comprising:

receiving a road graph for a map region, the road graph comprising (i) a plurality of road segments aggregated into roads and (ii) a plurality of junctions at which two or more road segments intersect;

generating an initial set of geometries for the road segments in the road graph, each geometry defined by a set of vertices that specify boundaries of the geometry;

determining that a boundary of a first geometry for a first road segment and a boundary of a second geometry for a second road segment overlap based on locations of the vertices that specify the boundary of the first geometry and the vertices that specify the boundary of the second geometry, wherein the first road segment and the second road segment do not share a junction;

for at least two pairs of vertices that specify overlapping boundaries the first and second geometries, applying a displacement amount that is proportional to an amount of overlap between the two pairs of vertices, wherein the applied displacement amount is larger when the overlap is greater; and

based on the applied displacement amount, moving the vertices that specify the boundaries of the first and second geometries in order to remove the overlap,

wherein said receiving, generating, determining, applying, and moving are performed by at least one server.

12. The method of claim 11, wherein the geometries are used to generate map tiles for download to user devices requesting electronic maps of the map region.

13. The method of claim 11, wherein moving the vertices that specify the boundaries further comprises moving centerlines of the first road segment and the second road segment apart from each other, wherein the vertices that specify the boundaries of the first and second road segments are moved with the centerline.

14. The method of claim 13, wherein the centerlines of the first and second road segments are only moved in the vicinity of the overlap.

15. The method of claim 13, wherein an amount of movement of the centerlines is proportional to the amount of overlap.

16. The method of claim 11, wherein moving the vertices that specify the boundaries comprises reducing a width of at least one of the geometries by moving the vertices towards a centerline of the road segment.

17. The method of claim 11, wherein the first and second road segments are at a same elevation.

18. For a mapping service, a method comprising:

generating an initial set of geometries for a road graph defined for a map region, the road graph comprising a plurality of road segments and junctions aggregated into roads;

identifying an overlap between a first geometry of a first road segment and a second geometry of a second road segment, wherein the first road segment and the second road segment are parts of different roads and do not meet at a junction, wherein the first and second geometries comprise centerline vertices;

for at least two pairs of centerline vertices of the first and second geometries that are located adjacent to the overlap, applying a displacement amount that is proportional to an amount of overlap that is adjacent to each centerline vertex in the pairs, wherein the applied displacement amount is larger when the overlap is greater; and

based on the applied displacement amount, moving centerline vertices of the first and second geometries apart from each other in order to prevent the first geometry and second geometry from overlapping.

19. The method of claim 18, wherein the centerline vertices of the geometries define the centerline of the road segment.

20. The method of claim 19, wherein moving the centerline vertices comprises adjusting centerline of the first and second road segments away from each other.

21. The method of claim 20, wherein the centerline vertices within a particular distance are moved.

22. The method of claim 18, wherein each of the moved centerline vertices are displaced a different distance related to the amount of the overlap adjacent to the moved centerline vertices.