Scalable processing for associating geometries with map tiles

• US 9,235,906 B2
• Filed: 09/30/2012
• Issued: 01/12/2016
• Est. Priority Date: 06/10/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Carbonneau, Guillaume A., Dumont, Vincent
• Primary Examiner(s): Hoang, Peter
• Application Number:
  US13/632,003
• Publication Number:
  US 20130328941A1
• Time in Patent Office: 1,199 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation

Abstract

A method is provided that utilizes a parallel processing system to determine whether different geometries intersect each tile in a map hierarchy. The method receives a description of a geometry and an identification of a tile in a tile tree. The method utilizes an available processing unit to determine whether the geometry intersects the tile. When the geometry intersects the tile and the tile has child tiles, the method stores several task descriptions that can be assigned to any processing units in the parallel processing system. Each task description includes the description of the portion of the geometry that overlaps the tile and an identification of one of the child tiles of the tile. The method then assigns each of the tasks to an available processing unit to continue down the tree hierarchy to determine whether each child tile intersects a portion of the geometry.

Claims

1. A method of identifying associations between a plurality of map tiles and a geometry, the map tiles defined as a tile tree comprising the plurality of tiles at a plurality of parent-child hierarchical levels, the plurality of tiles comprising (i) a root tile having a plurality of child tiles and no parent tile, (ii) a plurality of leaf tiles, each leaf tile having only one parent tile and no child tiles, and (iii) a plurality of intermediate tiles having only one parent tile and a plurality of child tiles, the method comprising:

at a first processing unit of a plurality of parallel processing units;

receiving a description of the geometry and an identification of a tile in the plurality of tiles;

determining whether the tile intersects the geometry; and

when the tile intersects the geometry and has child tiles, storing a description of a plurality of tasks for determining whether a portion of the geometry intersects any of the child tiles of the tile, the description of each task comprising a description of the portion of the geometry that intersects the tile and an identification of a child tile of the tile; and

at a second processing unit of a plurality of parallel processing units;

receiving a description of a task comprising the description of a portion of the geometry and the identification of a particular child tile of the tile;

determining whether the particular child tile intersects the portion of the geometry; and

when the particular child tile intersects the portion of the geometery and has child tiles, storing a description of a plurality of tasks for determining whether a portion of the geometry portion that intersects the particular child tile intersects any of the child tiles of the particular child tile, the description of each task comprising a description of the portion of the geometry portion and an identification of a child tile of the particular child tile,

each defined task assignable to a processing unit in the plurality of parallel processing units to determine whether the portion and the tile described for the task intersect.

2. The method of claim 1, wherein each hierarchical level in the tile tree corresponds to a zoom level for displaying a map on a display screen of an electronic device.

3. The method of claim 1, wherein the tile tree is a quadtree comprising a plurality of nodes, each node corresponding to a map tile, each non-leaf node having four child nodes, each node other than the root node having only one parent node.

4. The method of claim 1, wherein the identification of a tile uniquely identifies (i) a position of the tile in the tile tree and (ii) the child tiles of the tile when the tile is not a leaf tile.

5. A method of identifying associations between a plurality of map tiles and a geometry to store in the map tiles, the method comprising:

receiving a description of the map tiles defined as a tile tree comprising the plurality of tiles at a plurality of parent-child hierarchical levels, the plurality of tiles comprising (i) a root tile having a plurality of child tiles and no parent tile, (ii) a plurality of leaf tiles, each leaf tile having only one parent tile and no child tiles, and (iii) a plurality of intermediate tiles having only one parent tile and a plurality of child tiles;

at a first processing unit in a plurality of parallel processing units;

receiving a description of the geometry and an identification of a particular tile in the plurality of tiles;

determining whether the particular tile intersects the geometry; and

when the particular tile intersects the geometry and is not a leaf tile, storing a description of a first portion of the geometry that intersects the particular tile and an identification of each child tile in the plurality of child tiles of the particular tile; and

at a second processing unit in the set of parallel processing units;

receiving the description of the first portion of the geometry that intersects the particular tile and the identification of a child tile of the particular tile;

determining whether the child tile intersects the first portion of the geometry; and

when the child tile intersects the first portion of the geometry, storing a description of a second portion of the geometry that intersects the child tile and an identification of each child tile in plurality of child tiles of said child tile.

6. The method of claim 5, wherein each hierarchical level in the tile tree corresponds to a zoom level for displaying a map on a display screen of an electronic device.

7. The method of claim 5, wherein the tile tree is a quadtree comprising a plurality of nodes, each node corresponding to a map tile, each non-leaf node having four child nodes.

8. A non-transitory computer readable medium storing a program for identifying associations between a plurality of map tiles and a geometry, the program executable by each processing unit in a plurality of parallel processing units, the map tiles defined as a tile tree comprising a plurality of tiles at a plurality of parent-child hierarchical levels, the plurality of tiles comprising (i) a root tile having a plurality of child tiles and no parent tile, (ii) a plurality of leaf tiles, each leaf tile having only one parent tile and no child tiles, and (iii) a plurality of intermediate tiles having only one parent tile and a plurality of child tiles, the program comprising sets of instructions for:

at a first processing unit of a plurality of parallel units;

receiving a description of the geometry and an identification of a tile in the plurality of tiles;

determining whether the tile intersects the geometry; and

when the tile intersects the geometry and has child tiles, storing a description of a plurality of tasks for determining whether a portion of the geometry intersects any of the child tiles of the tile, the description of each task comprising a description of the portion of the geometry that intersects the tile and an identification of a child tile of the tile; and

at a second processing unit of a plurality of parallel processing units;

receiving a description of a task comprising the description of a portion of the geometry and the identification of a particular child tile of the tile;

determining whether the particular child tile intersects the portion of the geometry; and

when the particular child tile intersects the portion of the geometry and the child tiles, storing a description of a plurality of tasks for determining whether a portion of the geometry portion that intersects the particular child tile intersects any child tiles of the particular child tile, the description of each task comprising a description of the portion of the geometry portion and an identification of each child tile of the particular child tile,

each defined task assignable to a processing unit in the plurality of parallel processing units to determine whether the portion and the tile described for the task intersect.

12. The non-transitory computer readable medium of claim 8, wherein each hierarchical level in the tile tree corresponds to a zoom level for displaying a map on a display screen of an electronic device.

13. The non-transitory computer readable medium of claim 8, wherein the tile tree is a quadtree comprising a plurality of nodes, each node corresponding to a map tile, each non-leaf node having four child nodes, each node other than the root node having only one parent node.

14. The computer readable medium of claim 8, wherein the identification of a particular tile uniquely identifies (i) a position of the particular tile in the tile tree and (ii) the child tiles of the particular tile when the tile is not a leaf tile.

9. A non-transitory computer readable medium storing a program for identifying associations between a plurality of map tiles and a geometry, the program executable by each processing unit in a plurality of parallel processing units, the map tiles defined as a tile tree comprising the plurality of tiles at a plurality of parent-child hierarchical levels, the plurality of tiles comprising (i) a root tile having a plurality of child tiles and no parent tile, (ii) a plurality of leaf tiles, each leaf tile having only one parent tile and no child tiles, and (iii) a plurality of intermediate tiles having only one parent tile and a plurality of child tiles, the program comprising sets of instructions for:

receiving, at a processing unit of the plurality of parallel processing units a description of the geometry and an identification of the root tile in the plurality of tiles;

determining whether the root tile intersects the geometry;

when the root tile intersects the geometry and has child tiles, storing a description of a plurality of tasks for determining whether a portion of the geometry intersects any of the child tiles of the root tile, the description of each task comprising a description of the portion of the geometry that intersects the tile and an identification of a child tile of the tile; and

assigning, for each particular tile in the tile tree that (i) has a parent tile and (ii) the parent tile of which intersects a particular portion of the geometry, a processing unit in the plurality of processing units to determine whether the particular tile intersects the particular portion of the geometry by;

receiving a description of the particular portion of the geometry and an identification of the particular tile;

determining whether the particular tile intersects the particular portion of the geometry;

determining whether the particular tile has child tiles; and

storing, when the particular tile intersects the particular portion of the geometry and has child tiles, a description of a plurality of tasks for determining whether a portion of the geometry that intersects the particular tile intersects any of the child tiles of the particular tile, the description of each task comprising a description of a portion of the geometry that intersects the particular tile and an identification of a child tile of the particular tile, each task assignable to a processing unit in the plurality of parallel processing units to determine whether any portion of the geometry intersects any of the child tiles of the particular tile.

10. The non-transitory computer readable medium of claim 9, the program further comprising a set of instructions for storing, when a processing unit determines that a tile intersects the geometry, a description of the portion of the geometry that intersects the tile in a local storage of the processing unit.

11. The non-transitory computer readable medium of claim 10, the program further comprising a set of instructions for:

retrieving, from local storage of different processing units, the descriptions of the portions of the geometry that intersect each particular tile; and

merging the retrieved descriptions in storage structure corresponding to each particular tile.

15. A non-transitory computer readable medium storing a program for identifying associations between a plurality of map tiles and a geometry to store in the map tiles, the program comprising sets of instructions for:

receiving a description of the map tiles defined as a tile tree comprising the plurality of tiles at a plurality of parent-child hierarchical levels, the plurality of tiles comprising (i) a root tile having a plurality of child tiles and no parent tile, (ii) a plurality of leaf tiles, each leaf tile having only one parent tile and no child tiles, and (iii) a plurality of intermediate tiles having only one parent tile and a plurality of child tiles;

at a first processing unit in a set of parallel processing units;

receiving a description of the geometry and an identification of a particular tile in the plurality of tiles, the tile having a plurality of child tiles;

determining whether the particular tile intersects the geometry; and

storing, when the particular tile intersects the geometry and is not a leaf tile, a description of a first portion of the geometry that intersect the particular tile and an identification of each child tile in the plurality of child tiles of the particular tile; and

at a second processing unit in the set of parallel processing units;

receiving the description of the first portion of the geometry that intersects the particular tile and the identification of a child tile of the particular tile;

determining whether the child tile intersects the first portion of the geometry; and

when the child tile intersects the first portion of the geometry, storing a description of a second portion of the geometry that intersects the child tile and an identification of each child tile in the plurality of child tiles of said child tile.

16. The non-transitory computer readable medium of claim 15, wherein each hierarchical level in the tile tree corresponds to a zoom level for displaying a map on a display screen of an electronic device.

17. The non-transitory computer readable medium of claim 15, wherein the tile tree is a quadtree comprising a plurality of nodes, each node corresponding to a map tile, each non-leaf node having four child nodes.