Navigation devices
First Claim
Patent Images
1. A method of generating a route across an electronic map using a processor of a computing device, comprising:
- performing, by the processor, a route search across the electronic map, wherein the electronic map comprises a plurality of navigable segments representing segments of a navigable route in an area covered by the map, wherein the map is divided into a plurality of hierarchical regions belonging to at least a coarser level and a neighbouring finer level such that each navigable segment is categorized into at least one region in each of the coarser and finer levels and wherein anyone region of the coarser level contains a plurality of regions of the finer level;
performing, by the processor, in a cost calculation at nodes processed during the route search which represent navigable segments in the electronic map, an assessment of whether navigable segments connected to those nodes are marked, within search acceleration data, as being part of a minimum cost route, and if there are such navigable segments exploring only those navigable segments wherein the search acceleration data indicates that a navigable segment is part of a minimum cost route to a region, the search acceleration data for a region of the finer level being constrained to data that indicates whether a navigable segment within a visibility area of the finer level region is part of a minimum cost route to the region, the visibility area comprising the coarser level region containing the finer level region and any regions determined to be close to the coarser level region;
generating, by the processor, a minimum cost route across the electronic map from an origin to a destination based on the route search; and
providing, by the processor, at least one of;
audible navigation instructions to guide a user along the generated route via an output device and displaying the generated route via a display of the computing device.
6 Assignments
0 Petitions
Accused Products
Abstract
A method of creating map data including search acceleration data arranged to increase the speed at which a route can be planned across an electronic map comprising a plurality of navigable segments, each navigable segment representing a segment of a navigable route in the area covered by the map, wherein the method comprises:
- a) reducing the number of navigable segments to be considered in the creation of the search acceleration data by removing navigable segments to form a core network of navigable segments;
- b) dividing the electronic map into a set of hierarchical regions such that the or each navigable segment is categorized into at least one region in each level of the hierarchy;
- c) using a time varying function associated with at least some, and generally each, navigable segment of the core network to determine whether that navigable segment is part of minimum cost route to at least one of the regions and recording this determination in the search acceleration data.
-
Citations
14 Claims
-
1. A method of generating a route across an electronic map using a processor of a computing device, comprising:
-
performing, by the processor, a route search across the electronic map, wherein the electronic map comprises a plurality of navigable segments representing segments of a navigable route in an area covered by the map, wherein the map is divided into a plurality of hierarchical regions belonging to at least a coarser level and a neighbouring finer level such that each navigable segment is categorized into at least one region in each of the coarser and finer levels and wherein anyone region of the coarser level contains a plurality of regions of the finer level; performing, by the processor, in a cost calculation at nodes processed during the route search which represent navigable segments in the electronic map, an assessment of whether navigable segments connected to those nodes are marked, within search acceleration data, as being part of a minimum cost route, and if there are such navigable segments exploring only those navigable segments wherein the search acceleration data indicates that a navigable segment is part of a minimum cost route to a region, the search acceleration data for a region of the finer level being constrained to data that indicates whether a navigable segment within a visibility area of the finer level region is part of a minimum cost route to the region, the visibility area comprising the coarser level region containing the finer level region and any regions determined to be close to the coarser level region; generating, by the processor, a minimum cost route across the electronic map from an origin to a destination based on the route search; and providing, by the processor, at least one of;
audible navigation instructions to guide a user along the generated route via an output device and displaying the generated route via a display of the computing device. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor of a computing device, causes the computing device to perform a method for generating a route across an electronic map, comprising:
-
performing a route search across the electronic map, wherein the electronic map comprises a plurality of navigable segments representing segments of a navigable route in an area covered by the map, wherein the map is divided into a plurality of hierarchical regions belonging to at least a coarser level and a neighbouring finer level such that each navigable segment is categorized into at least one region in each of the coarser and finer levels and wherein anyone region of the coarser level contains a plurality of regions of the finer level; performing, in a cost calculation at nodes processed during the route search which represent navigable segments in the electronic map, an assessment of whether navigable segments connected to those nodes are marked, within search acceleration data, as being part of a minimum cost route, and if there are such navigable segments exploring only those navigable segments wherein the search acceleration data indicates that a navigable segment is part of a minimum cost route to a region, the search acceleration data for a region of the finer level being constrained to data that indicates whether a navigable segment within a visibility area of the finer level region is part of a minimum cost route to the region, the visibility area comprising the coarser level region containing the finer level region and any regions determined to be close to the coarser level region; generating a minimum cost route across the electronic map from an origin to a destination based on the route search; and providing at least one of;
audible navigation instructions to guide a user along the generated route via an output device and displaying the generated route via a display of the computing device. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
Specification