Generating and serving tiles in a digital mapping system

• US 7,599,790 B2
• Filed: 03/23/2005
• Issued: 10/06/2009
• Est. Priority Date: 03/23/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Rasmussen, Lars Eilstrup, Rasmussen, Jens Eilstrup, Ma, Stephen
• Primary Examiner(s): Camby; Richard M.
• Application Number:
  US11/088,542
• Publication Number:
  US 20050270299A1
• Time in Patent Office: 1,658 Days
• Field of Search: 701207-213, 345/630, 345/422, 345/426, 345/473, 345/474, 345/418, 345/432, 345/424, 345/425, 345/427, 345/582, 345/583, 3409951-99528
• US Class Current: 701/208
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers
• CPC Class Codes: G01C 21/3673 Labelling using text of road map data items, e.g. road names, POI names
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 3/40 Scaling of whole images or parts thereof, e.g. expanding or contracting
• CPC Class Codes: G09B 29/10 Map spot or coordinate position indicators; Map reading aids optical projection apparatus per se G03B
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

Digital tile-based mapping techniques are disclosed that enable efficient online serving of aesthetically pleasing maps. In one particular embodiment, an image tile-based digital mapping system is configured for generating map tiles during an offline session, and serving selected sets of those tiles to a client when requested. Also provided are solutions for handling map labels and other such features in a tile-based mapping system, such as when a map label crosses map tile boundaries. Various processing environments (e.g., servers or other computing devices) can be employed in the system.

Claims

1. A system for generating map tiles for a tile-based digital mapping system comprising:

a map painter module for generating digital map images;

a tile maker for generating map tiles from the digital map images, wherein the tile maker operates according to a configuration file that defines areas and zoom levels for map tiles to be generated and the tile maker uses the map painter module to generate the digital map images for areas defined in the configuration file; and

a tile storage for storing map tiles generated by the tile maker.

2. The system of claim 1 wherein the map painter module is operable to request and receive geographical data for a given area from which the digital map images are generated.

3. The system of claim 2 further comprising:

a map data storage for storing one or more sets of the geographical data for a given area that is accessible by the map painter module.

4. The system of claim 3 wherein the map data storage includes a set of rich mapping format (RMF) files.

5. The system of claim 2 further comprising:

a remote mapping engine (RML) library configured with an application program interface that allows the map painter module to access the geographical data.

6. The system of claim 1 wherein the configuration file defines geographical data sets to use for map tiles to be generated.

7. The system of claim 1 wherein the configuration file further defines a location for placement of a label.

8. The system of claim 1 wherein the tile maker is adapted to divide large areas defined in the configuration file into smaller areas, and uses the map painter module to generate the digital map images for those smaller areas.

9. The system of claim 1 wherein the tile maker is operable to pass information to the map painter module, receive from the map painter module a corresponding digital image that is based on the passed information, and divide the image into tiles.

10. The system of claim 1 wherein the tile maker is further configured to encode the generated map tiles into a desired image format, and to store the formatted map tiles.

11. The system of claim 1 wherein the desired image format is sub-pixel bitmaps.

12. The system of claim 1 further comprising

a map tile serving system configured to serve map tiles stored in the tile storage, in response to map requests from a user.

13. The system of claim 12 wherein the map tile serving system further comprises:

a plurality of front end tile servers for serving one or more map tiles requested by a user;

a request distributor for distributing requests for map tiles between the plurality of front end tile servers; and

a plurality of back end tile servers communicatively coupled with the plurality of front end tile servers, each back end tile server having access to the map tiles generated by the tile maker, and configured to provide requested map tiles to a corresponding front end tile server.

14. A map tile serving system configured to serve map tiles in response to map requests from a user, comprising:

a plurality of front end tile servers for serving one or more map tiles requested by a user;

a request distributor for distributing requests for map tiles between the plurality of front end tile servers; and

a plurality of back end tile servers communicatively coupled with the plurality of front end tile servers, each back end tile server having access to the map tiles, and configured to provide requested map tiles to a corresponding front end tile server;

wherein at least one of the front end tile servers can identify one or more uni-colored map tiles, and is configured to serve the uni-colored map tiles, without having to request those uni-colored map tiles from one of the back end tile servers.

15. The system of claim 14 wherein the one or more uni-colored map tiles are stored in a memory cache included in the at least one front end tile server.

16. The system of claim 14 wherein a user is communicating with the at least one front end server using a computing device, and the at least one front end server causes the computing device to use uni-color map tiles that are locally available to the computing device, so that such tiles do not have to be served.

17. The system of claim 14 wherein each of the map tiles is associated with an N×

N block of map tiles, and each time a map tile is requested, all N² tiles in the corresponding N×

N block are cached, thereby reducing the need for future disk access associated with those map tiles.

18. The system of claim 14 wherein the number of back end sewers is such that each back end server can be used to serve a particular sub-set of the map tiles, and each back end server is capable of caching its corresponding sub-set.

19. The system of claim 14 wherein each back end tile server is dedicated to sewing a sub-set of the map tiles, and each front end tile server is configured to identify an appropriate back end server to use in satisfying a user request for a map tile.

20. The system of claim 19 wherein each front end tile server uses a hashing function based on map tile coordinates to identify the appropriate back end sewer.

21. The system of claim 14 wherein in response to a back end tile server being unavailable to serve its load of map tiles, each front end tile server is configured to distribute that load among the remaining back end tile servers.

22. The system of claim 21 wherein each front end tile server uses a hashing function based on map tile coordinates and an attempt counter to distribute the load.

23. The system of claim 14 wherein each of the map tiles is associated with an N×

N block of map tiles, and each time a map tile is requested, all N² tiles in the corresponding N×

N block are served.

24. The system of claim 14 further comprising

a map tile generation system including a tile maker for generating the map tiles;

and

a tile storage for storing the generated map tiles, wherein map tiles that are not available in caches of the front end or back end servers can be accessed from the tile storage.

25. A tile-based digital mapping method, comprising:

generating map tiles from digital map images;

storing the map tiles; and

serving one or more of the map tiles, in response to a user map request, wherein the serving further comprises

identifying uni-color map tiles that are locally available to a computing device of the user, and

causing the computing device to use uni-color map tiles that are locally available to the computing device, so that such tiles do not have to be sewed.

26. The method of claim 25 further comprising:

generating the digital map images, which includes defining areas and zoom levels for which map tiles should be generated.

27. The method of claim 26 wherein generating the digital map images further includes defining at least one from a group consisting of geographical data sets to use, and a location for placement of a label.

28. The method of claim 25 wherein storing the map tiles includes encoding the generated map tiles into a desired image format, and storing the formatted map tiles.

29. The method of claim 28 wherein the desired image format is sub-pixel bitmaps.

30. The method of claim 25 wherein serving one or more of the map tiles includes caching the sewed map tiles.

31. The method of claim 25 wherein generating map tiles from digital map images comprises:

identifying areas to be drawn, and respective various zoom levels at which to draw each area;

dividing the areas into sub-areas at the respective various zoom levels, such that each sub-area can be pre-rendered in an available memory;

pre-rendering each sub-area at a zoom level of the respective various zoom levels;

dividing each pre-rendered sub-area into rendering areas, such that each rendering area can be rendered in the available memory;

rendering the rendering areas to form a resulting image; and

dividing the resulting image into map tiles.

32. The method of claim 31 wherein pre-rendering each of the sub-areas at a zoom level represents a task, so as to provide a list of tasks defined by area and zoom level, and parallel processing is applied to executing these tasks.

33. The method of claim 31 wherein the map to be displayed to the requesting user has a resolution, and the rendering is done at a resolution N times greater than the resolution of the map to be displayed, and the bitmap produced by the rendering is used as input for generating tiles as sub-pixel bitmaps.

34. The method of claim 25 wherein generating map tiles from digital map

images comprises:

identifying areas to be drawn;

dividing the areas into sub-areas, such that each sub-area can be pre-rendered in an available memory;

pre-rendering each sub-area;

dividing each pre-rendered sub-area into rendering areas, such that each rendering area can be rendered in the available memory; and

rendering the rendering areas.

35. A method for generating digital map tiles from digital map data comprising:

identifying areas to be drawn, and various zoom levels at which each area needs to be drawn;

dividing the areas into sub-areas as needed at the different zoom levels, such that each sub-area can be pre-rendered in an available memory;

pre-rendering each sub-area at a given zoom level;

dividing each pre-rendered sub-area into rendering areas, such that each rendering area can be rendered in the available memory;

rendering the rendering areas to produce an image; and

dividing the image into map tiles.

36. The method of claim 35 wherein pre-rendering each sub-area includes accessing at least one of geographical data sets and a representation of instructions about how to build the digital map image.

37. The method of claim 36 wherein the instructions are represented in a configuration file.

38. The method of claim 35 wherein the sub-areas each have a pre-determined fixed size.

39. The method of claim 35 wherein the sub-areas each have a pre-determined fixed size for each zoom level.

40. The method of claim 35 wherein pre-rendering decisions prevent labels from crossing borders between sub-areas.

41. The method of claim 35 wherein pre-rendering decisions are stored so they can be used in subsequent pre-rendering tasks.

42. The method of claim 35 wherein pre-rendering decisions allow features to cross borders between sub-areas.

43. The method of claim 42 wherein two aligning sub-areas associated with a border crossing feature are not allowed to be pre-rendered at the same time.