Scalable and efficient cutting of map tiles

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

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Carbonneau, Guillaume A., Dumont, Vincent, Dhamija, Anuj, Laprise, Denis, Arikan, Okan, Howard, James A.
• Primary Examiner(s): Hoang, Peter
• Application Number:
  US13/632,004
• Publication Number:
  US 20130328879A1
• Time in Patent Office: 1,388 Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation

Abstract

A process is provided that reduces the amount of data for a map tile that could not be displayed separately on the scale of that tile. The process generates an equivalent of the road data by rasterizing the vectors representing road segments lying within a tile and generating a connectivity mask that keeps track of which pixels are connected to which other pixels along the vectors. The process constructs an undirected graph. Each “on” pixel of the undirected graph represents a vertex and the vertices are connected by edges generated from the connectivity graph, but without a set direction. The process traces the undirected graph to generate chains of connected road segments and takes the chains and simplifies them in order to reduce the amount of data that must be stored and transmitted for the tile in order to produce all the visible roads of the tile at that scale.

Claims

1. A method of generating map tiles for a mapping application, the method comprising:

receiving a request from a user device for a map tile at a particular zoom level;

receiving a set of vectors, each vector representing a particular road segment in the map tile;

rasterizing the set of vectors to identify a set of active pixels through which the vectors pass based on the particular zoom level;

generating a connectivity byte mask that identifies a direction from which vectors enter a pixel for each active pixel in the connectivity byte mask;

generating an undirected graph of vertices and edges connecting the vertices from the connectivity byte mask;

reducing a number of the vertices within the undirected graph;

creating a simplified map tile with less data than the map tile based on the reduced number of vertices; and

transmitting the simplified map tile to the user device for rendering in the mapping application.

2. The method of claim 1, wherein the method further comprises generating a traced graph, that identifies connections between chains of vertices identifying ends of road segments, from the set of vectors, wherein reducing a number of the vertices comprises simplifying the traced graph to eliminate intermediate vertices.

3. The method of claim 2, wherein generating the traced graph comprises identifying the chains of vertices based on the undirected graph.

4. The method of claim 1, wherein the connectivity byte mask identifies a direction from which vectors enter a pixel in order to identify which active pixels are directly connected to adjacent active pixels.

5. The method of claim 1, wherein reducing a number of the vertices comprises removing intermediate vertices based on positions of the intermediate vertices with respect to end vertices.

6. The method of claim 1, wherein rasterizing the set of vectors further comprises eliminating redundant road segments in which vectors that represent the redundant road segments overlap a same set of active pixels.

7. A method of generating map tiles for a mapping application, the method comprising:

receiving a vector representing a road in an original map tile;

generating an undirected graph of vertices and edges connecting the vertices from the vector;

identifying a current vertex of the undirected graph in a chain of vertices connected by edges;

iteratively, for the chain of vertices;

identifying an available edge connecting the currently identified vertex to a candidate vertex;

making the candidate vertex the currently identified vertex;

adding the currently identified vertex to the chain;

setting the edge to be unavailable; and

repeating the iterated operations until the then currently identified vertex has no available edges for making connections; and

simplifying the vector by eliminating intermediate vertices in the chain of vertices in order to reduce a number of vertices in the chain of vertices.

8. The method of claim 7 further comprising creating a simplified map tile using the chain of vertices with the reduced number of vertices, wherein the simplified map tile comprises less data than the original map tile.

9. A method of eliminating data redundancy in a map tile, the method comprising:

receiving a plurality of vectors representing road segments in a geographical area represented by the map tile;

identifying a set of pixels through which the vectors pass by rasterizing the vectors to identify a set of active pixels through which the vectors pass;

generating a connectivity byte mask that identifies a direction from which vectors enter a pixel for each active pixel in the connectivity byte mask in order to identify which active pixels are directly connected to adjacent active pixels;

generating an undirected graph of vertices and edges from the connectivity byte mask;

generating a traced graph by identifying chains of vertices connected by edges in the undirected graph; and

simplifying the traced graph to generate a set of vertices that contain the relevant data from the vectors.

10. The method of claim 9, wherein generating the connectivity byte mask comprises removing roads going in a same direction on a same set of pixels in the map tile from road data about the map tile.

11. The method of claim 9, wherein generating the undirected graph comprises removing roads going in opposite directions on a same set of pixels in the map tile from road data about the map tile.

12. The method of claim 9, wherein the vectors are rasterized using a Bresenham line algorithm.

13. The method of claim 9, wherein the traced graph is simplified by a Douglas-Peucker algorithm.

14. The method of claim 9, wherein the rasterization operation removes redundant road segments that begin and end in a single pixel from the data.

15. The method of claim 9, wherein generating the traced graph comprises selecting a vertex in a same direction as a previous direction, when there is a choice of directions for selecting a next vertex.

16. A non-transitory machine readable medium storing a program that when executed by at least one processing unit generates map tiles for a mapping application, the program comprising sets of instructions for:

receiving a request from a user device for a map tile at a particular zoom level;

receiving a set of vectors, each vector representing a particular road segment in the map tile;

rasterizing the set of vectors to identify a set of active pixels through which the vectors pass based on the particular zoom level;

generating a connectivity byte mask that identifies a direction from which vectors enter a pixel for each active pixel in the connectivity byte mask;

generating an undirected graph of vertices and edges connecting the vertices from the connectivity byte mask;

reducing a number of the vertices within the undirected graph;

creating a simplified map tile with less data than the map tile based on the reduced number of vertices; and

transmitting the simplified map tile to the user device for rendering in the mapping application.

17. The non-transitory machine readable medium of claim 16, wherein the program further comprises a set of instructions for generating a traced graph, that identifies connections between chains of vertices identifying ends of road segments, from the set of vectors, wherein the set of instructions for reducing a number of vertices comprises a set of instructions for simplifying the traced graph to eliminate intermediate vertices.

18. The non-transitory machine readable medium of claim 17, wherein the set of instructions for generating the traced graph comprises a set of instructions for identifying the chains of vertices based on the undirected graph.

19. The non-transitory machine readable medium of claim 16, wherein the set of instructions for reducing a number of the vertices comprises a set of instructions for removing intermediate vertices based on positions of the intermediate vertices with respect to end vertices.

20. The non-transitory machine readable medium of claim 16, wherein the set of instructions for rasterizing the set of vectors further comprises a set of instructions for eliminating redundant road segments in which vectors that represent the redundant road segments overlap a same set of active pixels.

21. A non-transitory machine readable medium storing a program that when executed by at least one processing unit generates map tiles for a mapping application, the program comprising sets of instructions for:

receiving a vector representing a road in an original map tile;

generating an undirected graph of vertices and edges connecting the vertices from the vector;

identifying a current vertex of the undirected graph in a chain of vertices connected by edges;

iteratively, for the chain of vertices;

identifying an available edge connecting the currently identified vertex to a candidate vertex;

making the candidate vertex the currently identified vertex;

adding the currently identified vertex to the chain;

setting the edge to be unavailable; and

repeating the iterated operations until the then currently identified vertex has no available edges for making connections; and

simplifying the vector by eliminating intermediate vertices in the chain of vertices in order to reduce a number of vertices in the chain of vertices.

22. The non-transitory machine readable medium of claim 21, wherein the program further comprises a set of instructions for creating a simplified map tile using the chain of vertices with the reduced number of vertices, wherein the simplified map tile comprises less data than the original map tile.

23. A non-transitory machine readable medium storing a program that when executed by at least one processing unit eliminates data redundancy in a map tile, the program comprising sets of instructions for:

receiving a plurality of vectors representing road segments in a geographical area represented by the map tile;

identifying a set of pixels through which the vectors pass by rasterizing the vectors to identify a set of active pixels through which the vectors pass;

generating a connectivity byte mask that identifies a direction from which vectors enter a pixel for each active pixel in the connectivity byte mask in order to identify which active pixels are directly connected to adjacent active pixels;

generating an undirected graph of vertices and edges from the connectivity byte mask;

generating a traced graph by identifying chains of vertices connected by edges in the undirected graph; and

simplifying the traced graph to generate a set of vertices that contain the relevant data from the vectors.

24. The non-transitory machine readable medium of claim 23, wherein the set of instructions for generating the connectivity byte mask comprises a set of instructions for removing roads going in a same direction on a same set of pixels in the map tile from road data about the map tile.

25. The non-transitory machine readable medium of claim 23, wherein the set of instructions for generating the undirected graph comprises a set of instructions for removing roads going in opposite directions on a same set of pixels in the map tile from road data about the map tile.

26. The non-transitory machine readable medium of claim 23, wherein the program further comprises a set of instructions for eliminating redundant road segments that begin and end in a single pixel from the tile data.