Dynamic vector map tiles

• US 9,798,926 B2
• Filed: 09/01/2015
• Issued: 10/24/2017
• Est. Priority Date: 09/02/2014
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Pahwa, Aroon, Lenoski, Brian A., Courtemanche, Mathieu
• Primary Examiner(s): Azarian, Seyed
• Application Number:
  US14/842,782
• Publication Number:
  US 20160098598A1
• Time in Patent Office: 784 Days
• Field of Search: 382100, 382103, 382106, 382113, 382154, 382155, 382162, 382168, 382173, 382180, 382181, 382190-195, 382204, 382209, 382223-224, 382232, 382254, 382274, 382276, 382285-291, 382 3- 5, 382312, 382 35, 382295, 701421, 345552, 345629, 345419, 348 43
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G01C 21/3889 Transmission of selected map data, e.g. depending on route
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 2200/04 involving 3D image data
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 3/067 Reshaping or unfolding 3D tree structures onto 2D planes
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps
• CPC Class Codes: G09B 29/106 using electronic means
• CPC Class Codes: H04N 19/44 Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder

Abstract

The present disclosure relates to systems and processes for providing vector map data for generating a view of a map in a mapping application. In one example process, a request for a vector map sub-tile can be received by a map server. The map server can identify a pre-generated vector map tile corresponding to the requested vector map sub-tile and can generate the requested vector map sub-tile from the identified vector map tile by dividing the vector map tile into two or more vector map sub-tiles. In some examples, dividing the vector map tile into multiple vector map sub-tiles can include identifying features and attributes of the vector map tile that should be included in the requested vector map sub-tile and generating the requested vector map sub-tile to include these features and attributes. The map server can then transmit the requested vector map sub-tile to the requesting electronic device.

Claims

1. A computer-implemented method comprising:

at one or more servers;

receiving, from an electronic device, a request for a vector map sub-tile;

identifying a vector map tile corresponding to the requested vector map sub-tile;

accessing the vector map tile;

generating the requested vector map sub-tile by dividing the vector map tile into a plurality of vector map sub-tiles, the plurality of vector map sub-tiles comprising the requested vector map sub-tile, wherein the vector map tile comprises one or more of a point map feature, line map feature, polygon map feature, or a three-dimensional (3D) polygon map feature, and dividing the vector map tile into the plurality of vector map sub-tiles comprises selecting one of a plurality of processes for dividing the vector map tile depending upon the map feature within the vector map tile; and

transmitting the requested vector map sub-tile to the electronic device.

2. The computer-implemented method of claim 1, wherein the vector map tile comprises vector data representing a portion of a map.

3. The computer-implemented method of claim 1, wherein accessing the vector map tile comprises:

retrieving the vector map tile from a storage of the one or more servers; and

decoding the vector map tile from an encoding format.

4. The computer-implemented method of claim 3, wherein generating the requested vector map sub-tile by dividing the vector map tile into a plurality of vector map sub-tiles comprises dividing the decoded vector map tile.

5. The computer-implemented method of claim 3 further comprising:

at the one or more servers, encoding the requested vector map sub-tile into the encoding format prior to transmitting the requested vector map sub-tile to the electronic device.

6. The computer-implemented method of claim 1, wherein the vector map tile comprises a point map feature, and wherein generating the requested vector map sub-tile by dividing the vector map tile into a plurality of vector map sub-tiles comprises:

at the one or more servers;

determining whether the point map feature is located within the requested vector map sub-tile;

in accordance with a determination that the point map feature is located within the requested vector map sub-tile, generating the requested vector map sub-tile to include the point map feature; and

in accordance with a determination that the point map feature is not located within the requested vector map sub-tile, generating the requested vector map sub-tile to exclude the point map feature.

7. The computer-implemented method of claim 6, wherein the point map feature represents a point of interest.

8. The computer-implemented method of claim 1, wherein the vector map tile comprises a line map feature, and wherein generating the requested vector map sub-tile by dividing the vector map tile into a plurality of vector map sub-tiles comprises:

at the one or more servers;

determining whether the line map feature is located within the requested vector map sub-tile;

in accordance with a determination that the line map feature is not at least partially located within the requested vector map sub-tile, generating the requested vector map sub-tile to exclude the line map feature;

in accordance with a determination that the line map feature is located entirely within the requested vector map sub-tile, generating the requested vector map sub-tile to include the line map feature; and

in accordance with a determination that the line map feature is located partially within the requested vector map sub-tile;

applying a flattening algorithm to the line map feature;

generating a plurality of line segments by dividing the flattened line map feature at intersections between vector map sub-tiles of the plurality of vector map sub-tiles;

applying a curve fitting algorithm to one or more line segments of the plurality of line segments located within the requested vector map sub-tile; and

generating the requested vector map sub-tile to include the one or more line segments.

9. The computer-implemented method of claim 8 further comprising:

at the one or more servers;

in accordance with a determination that the line map feature is located partially within the requested vector map sub-tile, tagging ends of the one or more line segments located at an edge of the requested vector map sub-tile to indicate that the one or more line segments connect to other line segments of other vector map sub-tiles.

10. The computer-implemented method of claim 8, wherein the line map feature represents a road, a path, a highway, or a river.

11. The computer-implemented method of claim 1, wherein the vector map tile comprises a polygon map feature, and wherein generating the requested vector map sub-tile by dividing the vector map tile into a plurality of vector map sub-tiles comprises:

at the one or more servers;

determining whether the polygon map feature is located within the requested vector map sub-tile;

in accordance with a determination that the polygon map feature is not at least partially located within the requested vector map sub-tile, generating the requested vector map sub-tile to exclude the polygon map feature;

in accordance with a determination that the polygon map feature is located entirely within the requested vector map sub-tile, generating the requested vector map sub-tile to include the line polygon feature; and

in accordance with a determination that the polygon map feature is located partially within the requested vector map sub-tile;

generating a plurality of polygon segments by dividing the polygon map feature at intersections between vector map sub-tiles of the plurality of vector map sub-tiles; and

generating the requested vector map sub-tile to include one or more polygon segments of the plurality of polygon segments located within the requested vector map sub-tile.

12. The computer-implemented method of claim 11 further comprising:

at the one or more servers;

in accordance with a determination that the polygon map feature is located partially within the requested vector map sub-tile, tagging edges of the one or more polygon segments located at an edge of the requested vector map sub-tile to indicate that the tagged edges represent interior edges.

13. The computer-implemented method of claim 11, wherein the line polygon map feature represents a body of water or an area of land.

14. The computer-implemented method of claim 1, wherein the vector map tile comprises a three-dimensional (3D) polygon map feature, the 3D polygon map feature having a two-dimensional (2D) base, and wherein generating the requested vector map sub-tile by dividing the vector map tile into a plurality of vector map sub-tiles comprises:

at the one or more servers;

determining whether the requested vector map sub-tile is a vector map sub-tile of the plurality of vector map sub-tiles having a largest portion of the 2D base located therein;

in accordance with a determination that the requested vector map sub-tile is the vector map sub-tile of the plurality of vector map sub-tiles having the largest portion of the 2D base located therein, generating the requested vector map sub-tile to include the 3D polygon map feature; and

in accordance with a determination that the requested vector map sub-tile is not the vector map sub-tile of the plurality of vector map sub-tiles having the largest portion of the 2D base located therein, generating the requested vector map sub-tile to exclude the 3D polygon map feature.

15. The computer-implemented method of claim 14, wherein the line 3D polygon map feature represents a building.

16. The computer-implemented method of claim 1, wherein generating the requested vector map sub-tile by dividing the vector map tile into a plurality of vector map sub-tiles comprises:

at the one or more servers;

generating the requested vector map sub-tile to include one or more attributes of the vector map tile.

17. The computer-implemented method of claim 16, wherein the one or more attributes comprises a local North direction.

18. The computer-implemented method of claim 1, wherein the electronic device is a watch.

19. The computer-implemented method of claim 1, wherein the electronic device is a mobile phone.