Generating and serving tiles in a digital mapping system

• US 20050270299A1
• Filed: 03/23/2005
• Published: 12/08/2005
• 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
• Granted Patent: US 7,599,790 B2
• Time in Patent Office: Days
• US Class Current: 345/552
• 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; 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 (RME) 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 tile maker operates according to a configuration file that defines areas and zoom levels for which map tiles should be generated.

7. The system of claim 6 wherein the configuration file further defines at least one of geographical data sets to use and how the map should be drawn including label placement information.

8. The system of claim 6 wherein the tile maker uses the map painter module to generate the digital map images for areas defined in the configuration file.

9. The system of claim 6 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.

10. 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 mage into tiles.

11. 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.

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

13. 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.

14. The system of claim 13 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.

15. 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.

16. The system of claim 15 wherein at least one of the front end tile servers can identify one or more uni-colored the 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.

17. The system of claim 16 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.

18. The system of claim 16 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.

19. The system of claim 15 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.

20. The system of claim 15 wherein the number of back end servers 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.

21. The system of claim 15 wherein each back end tile server is dedicated to serving 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.

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

23. The system of claim 15 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.

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

25. The system of claim 15 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.

26. The system of claim 15 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 and/or back end servers can be accessed from the tile storage.

27. 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.

28. The method of claim 27 further comprising:

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

29. The method of claim 28 wherein generating the digital map images further includes defining at least one of geographical data sets to use, how the map should be drawn including label placement information.

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

31. The method of claim 30 wherein the desired image format is sub-pixel bitmaps.

32. The method of claim 27 wherein serving one or more of the map tiles includes caching the served map tiles.

33. The method of claim 27 further comprising:

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

34. The method of claim 27 wherein generating map tiles from digital map images comprises:

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

rendering the rendering areas, and dividing the resulting image into map tiles.

35. The method of claim 34 wherein 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.

36. The method of claim 34 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.

37. The method of claim 27 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.

38. 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.

39. The method of claim 38 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.

40. The method of claim 39 wherein the instructions are represented in a configuration file.

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

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

43. The method of claim 38 wherein pre-rendering decisions prevent problematic features from crossing borders between sub-areas.

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

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

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