Car mounted navigation system
First Claim
1. A navigation system comprising:
- a map data base comprising a plurality of polygons each side of each of said polygons corresponding to a road of a predetermined rank;
a display;
a first means coupled to said display for reading said map data base and for providing on said display at least a selected portion of said map data base and for providing on said display a straight line in said map data base connecting a first point in the selected portion of said map data base to a second point in said map data base;
a second means for selecting from said plurality of polygons in said map data base a chain of polygons disposed about said straight line, said chain of polygons connecting a first terminal polygon to a second terminal polygon wherein a first side of said first terminal polygon includes said first point and a first side of said second terminal polygon includes said second point with each polygon in said chain of polygons having at least one side common to an adjacently disposed polygon and wherein the second means provides a perpendicular line from a center point of each of the polygons in said chain of polygons to said straight line and said second means determines which one of said polygons have the shortest perpendicular line between said center points and said straight line; and
a third means for selecting predetermined ones of the sides of said polygons in said chain of polygons, each of said selected sides being connected to at least one other selected side to provide at least one continuous route from said first point to said second point and for computing a distance between said first point and second point along each of a plurality of the routes and for determining a most appropriate route based on at least said computed distances.
1 Assignment
0 Petitions
Accused Products
Abstract
A car mounted navigation system uses map data of polygons defined by roads of a predetermined rank or more of significance, connects a starting polygon containing a starting point to a destination polygon containing a destination with a chain of polygons adjoining at common sides of each pair of adjoining polygons and arranged between the starting and destination polygons to compute a plurality of routes extending from the starting point to the destination polygon, each route including a combination of sides of the chain polygons, the starting polygon and the destination polygon. A car operator selects an appropriate route from the computed routes. The system requires neither need for a great amount of database-made map data nor need for an entry of map data with a digitizer.
147 Citations
11 Claims
-
1. A navigation system comprising:
-
a map data base comprising a plurality of polygons each side of each of said polygons corresponding to a road of a predetermined rank; a display; a first means coupled to said display for reading said map data base and for providing on said display at least a selected portion of said map data base and for providing on said display a straight line in said map data base connecting a first point in the selected portion of said map data base to a second point in said map data base; a second means for selecting from said plurality of polygons in said map data base a chain of polygons disposed about said straight line, said chain of polygons connecting a first terminal polygon to a second terminal polygon wherein a first side of said first terminal polygon includes said first point and a first side of said second terminal polygon includes said second point with each polygon in said chain of polygons having at least one side common to an adjacently disposed polygon and wherein the second means provides a perpendicular line from a center point of each of the polygons in said chain of polygons to said straight line and said second means determines which one of said polygons have the shortest perpendicular line between said center points and said straight line; and a third means for selecting predetermined ones of the sides of said polygons in said chain of polygons, each of said selected sides being connected to at least one other selected side to provide at least one continuous route from said first point to said second point and for computing a distance between said first point and second point along each of a plurality of the routes and for determining a most appropriate route based on at least said computed distances. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method of determining a route between a first point and a second point in a map data base said method comprising the steps of:
-
reading the map data base, said map data base provided by a plurality of polygons each side of said polygons corresponding to a road having a predetermined rank; providing a straight line in said map data base from the first point in said map data to the second point in said map data base; selecting from said plurality of polygons a chain of polygons disposed about said straight line, said chain of polygons connecting a first terminal polygon to a second terminal polygon wherein a first side of said first terminal polygon includes said first point and a first side of said second terminal polygon includes said second point with each of said polygons in said chain of polygons having at least one side common to an adjacently disposed polygon on said chain; providing, with a second means, a perpendicular line from a center point of each of the polygons in said chain of polygons to said straight line; determining, with the second means, which one of said polygons have the shortest perpendicular line between said center points and said straight line; selecting, with a third means, at least one route between said first and second points with said route comprised of at least one side of each of said polygons in said chain of polygons; computing, with said third means, a distance of each of the routes selected; and determining, in response to at least said step of computing, a most appropriate route of said selected routes between said first point and said second point based on said computed distances. - View Dependent Claims (9, 10, 11)
-
Specification