LOOP-BASED ROUTE FINDING AND NAVIGATION
First Claim
1. A navigation method, comprising the steps of:
- providing a map having a network of roads and intersections;
tracing the roads to form one or more continuous loops;
specifying a starting point and a destination on the map; and
identifying a set of one or more loops linked by mutually continuous roads and/or intersections such that a route can be traced from the starting point to the destination along the roads and/or intersections comprising the identified loops.
3 Assignments
0 Petitions
Accused Products
Abstract
A navigation system and method uses loops as opposed to existing search techniques to more expeditiously find routes on a map from a starting point to a destination. Roads on a map are traced to form one or more continuous loops. Information regarding the loops is stored for future reference. A starting point and at least one destination are specified, and loops that connect the loops containing the starting point and destination are determined. A route is then formulated from the starting point to the destination using road segments or intersections where the identified loops are mutually contiguous. A list is generated including the loops and the road segments associated therewith. The road segments of an initial loop are examined and, if a road segment or intersection common to a next loop is identified, the road segments of that loop are examined, and so on, until a route from the starting point to the destination is found. Alternatively the route may be formulated by searching for routes along the roads that form one or more continuous loops connecting the starting point and the destination. Various speed-up algorithms and/or heuristics may be applied to the route formulation. The method finds application is many fields of endeavor, including wireless client-server navigation; embedded/dedicated automotive navigation, and logistics control, to name a few.
-
Citations
25 Claims
-
1. A navigation method, comprising the steps of:
-
providing a map having a network of roads and intersections; tracing the roads to form one or more continuous loops; specifying a starting point and a destination on the map; and identifying a set of one or more loops linked by mutually continuous roads and/or intersections such that a route can be traced from the starting point to the destination along the roads and/or intersections comprising the identified loops. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
Specification