OPTIMIZATION OF NAVIGATION TOOLS USING SPATIAL SORTING

• US 20120303263A1
• Filed: 11/18/2011
• Published: 11/29/2012
• Est. Priority Date: 05/23/2011
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Alam, Mudassir, Gonzalez, Juan Pablo Candelas
• Application Number:
  US13/300,156
• Publication Number:
  US 20120303263A1
• Time in Patent Office: Days
• US Class Current: 701/410
• CPC Class Codes: G01C 21/3632 Guidance using simplified or iconic instructions, e.g. using arrows G01C21/365 takes precedence
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• 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: G01C 21/3896 Transmission of map data from central databases

Abstract

Digital map navigation applications for use with a mobile computing device are optimized using a spatial sorting method. Spatial sorting entails partitioning a digital map into tiles and maintaining information that links tiles to points on the route. When a particular map navigation application is invoked, a set of relevance rules are defined for that map application to determine which of the route points to process. This determination is made by extracting from the look-up table a subset of the full set of route points, based on the relevance rules. Because the subset of route points is processed instead of the original full set of route points, the mobile device is capable of efficiently handling a complex route that otherwise would entail considerable expenditure of processor time and use of computer memory to store and retrieve unnecessary data.

Claims

1. A method, implemented by a mobile electronic device, of optimizing navigation along a prescribed route shown on a digital map, the method comprising:

by use of a mobile electronic device,

receiving a full set of route points associated with the prescribed route;

storing the full set of route points in a memory as a route points vector;

populating a look-up table with a set of keys, wherein the digital map is partitioned into a plurality of tiles, and wherein each key is associated with a different one of the plurality of tiles;

determining which route points, of the full set of route points, are relevant to each of one or more tiles of the plurality of tiles, wherein the determining is based on a set of relevance rules; and

storing the relevant route points for each of the one or more tiles.

2. The method of claim 1, wherein the relevance rules include:

a rule indicating that a pair of route points are relevant to a tile if a route segment connecting them intersects the tile;

a rule indicating that a pair of route points are relevant to a tile if the route segment connecting them intersects one or more edges of the tile;

a rule indicating that a plurality of route points are relevant to a tile if the route segment connecting them leaves and re-enters the tile; and

a rule indicating that a route point in a vicinity of a tile is relevant to the tile.

3. A method, implemented at least in part by a mobile device, of efficiently navigating a prescribed route shown on a digital map, the method comprising:

determining a current location of the mobile device using GPS location information;

selecting map data based at least in part on the GPS location information, wherein the map data comprises a digital map and a route;

rendering the map and the current location of the mobile device for display on the mobile device using spatial sorting optimization; and

tracking progress along the route using spatial sorting optimization.

4. The method of claim 3, wherein the map data is stored on a remote server.

5. The method of claim 3, wherein the route is defined by a full set of route points, and wherein rendering the digital map and the current location comprises:

for each of a plurality of tiles on the map,

selecting a subset of route points that are relevant to the tile; and

processing the subset of selected route points.

6. The method of claim 5, wherein processing the subset of selected route points increases computational efficiency compared with processing the full set of route points.

7. The method of claim 5, wherein the full set of route points is stored as an indexed vector;

each of the plurality of tiles is stored in a look-up table; and

each tile in the look-up table is associated with a list of relevant route points.

8. The method of claim 5, wherein selecting a subset of route points is done according to relevance rules comprising:

a rule indicating that a pair of route points are relevant to a tile if a route segment connecting them intersects the tile;

a rule indicating that a pair of route points are relevant to a tile if the route segment connecting them intersects one or more edges of the tile;

a rule indicating that a plurality of route points are relevant to a tile if the route segment connecting them leaves and re-enters the tile; and

a rule indicating that a route point in a vicinity of a tile is relevant to the tile.

9. The method of claim 8, wherein the subset of route points determined by the relevance rules includes locations on and near the route.

10. A mobile electronic device adapted to optimize map navigation of a prescribed route on a digital map, the mobile device comprising:

a processor;

a mobile transceiver for receiving map data and route points, and communicating with a remote device;

a GPS receiver for receiving location data to be processed by the processor;

a display on which maps and routes are rendered; and

one or more applications, including a map navigation tool that causes the processor to process the map data;

wherein the map navigation tool is configured to use a spatial sorting technique to partition the digital map into tiles, determine relevance of the route points to the tiles, and to process a subset of route points based on the relevance determination.

11. The mobile electronic device of claim 10, wherein the tiles are polygons.

12. The mobile electronic device of claim 10, wherein the tiles are squares.

13. The mobile electronic device according to claim 10, wherein the map navigation tool is configured with data structures comprising:

a look-up table, implemented as a hash table;

an indexed list of relevant route points for each tile; and

a route points vector storing a full set of route points.

14. The mobile electronic device according to claim 13, wherein the look-up table contains one or more LOD values.

15. The mobile electronic device according to claim 13, wherein the look-up table contains keys configured as map tile identifiers.

16. The mobile electronic device according to claim 13, wherein the route points vector is route-specific and contains latitude and longitude coordinates.

17. The mobile electronic device according to claim 13, wherein the list of relevant route points contains tile-specific route point indices.

18. The mobile electronic device according to claim 13, wherein the map navigation tool is configured to select the subset of route points from the route points vector according to a set of relevance rules.

19. The mobile electronic device according to claim 18, wherein the set of relevance rules comprises:

a rule indicating that a pair of route points are relevant to a tile if a route segment connecting them intersects the tile;

a rule indicating that a pair of route points are relevant to a tile if the route segment connecting them intersects one or more edges of the tile;

a rule indicating that a plurality of route points are relevant to a tile if the route segment connecting them leaves and re-enters the tile; and

a rule indicating that a route point in a vicinity of a tile is relevant to the tile.

20. The mobile electronic device according to claim 11, wherein the device is configured as a smart phone.