Vehicle map position determining apparatus

• US 5,270,937 A
• Filed: 04/26/1991
• Issued: 12/14/1993
• Est. Priority Date: 04/26/1991
• Status: Expired due to Fees

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Spencer, Mary F., Link, Laura J.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): ZANELLI, MICHAEL J
• Application Number:
  US07/691,872
• Time in Patent Office: 963 Days
• Field of Search: 364/450, 364/444, 364/460, 364/447, 364/436, 340/990-993, 340/995, 73/178 R
• US Class Current: 701/209
• CPC Class Codes: G01C 21/30 Map- or contour-matching

Abstract

A vehicle navigation/position system (10) investigates road segments having start and end coordinates stored in a road map data memory (13). The system determines what road segments have at least a portion inside a rectangle of interest (ROI-100) about an estimated vehicle position (101). Map matching then corrects vehicle position by locating vehicle position on one of the road segments inside the rectangle of interest. Vehicle location/navigation information is then provided. A computer (11) identifies road segments as inside the rectangle of interest (100) by creating electrical signals associated with each road segment start/end coordinate as compared to boundary coordinates of the rectangle. These electrical signals identify the road segment coordinates with respect to areas (B-I) surrounding the rectangle of interest (A). For road segments extending between opposite middle side areas (B-I, C-G), the computer (11) determines the road segment inside the rectangle of interest, and the road segment is added to a list.

Claims

1. Vehicle map position determining apparatus comprising:

map memory means for storing map data defining fixed road segments which exist in an overall geographical area;

determining means coupled to said map memory means for accessing said map data and determining which of said road segments have at least a portion inside a subregion of said geographical area, said subregion generally defining a quadrilateral;

means for receiving vehicle position data; and

utilization means coupled to said receiving means and said determining means for utilizing said vehicle position data and said map data in said map memory means which defines said road segments determined as having at least a portion inside said subregion to provide vehicle navigation/position information to a vehicle user,

wherein said determining means includes,

means for receiving, as said map data, data defining start and end coordinates of each of said road segments;

means for defining said subregion in terms of boundary coordinates;

means, coupled to said receiving means and said defining means, for comparing said start and end road segment coordinates with said boundary coordinates and providing, as a result of said comparison, a set of electrical signals defining the location of each of said start and end coordinates with respect to said subregion, said set of electrical signals defining the location of said start and end road segment coordinates as being inside said subregion or in any one of four corner areas adjacent said subregion or in any one of four middle side areas each between two of said corner areas and adjacent said subregion; and

logic means for identifying any of said road segments as having at least a portion inside said subregion in response to said set of electrical signals indicating each one of said road segment start and end coordinates being in different ones of said middle side areas on opposite sides of said subregion.

2. Vehicle map position determining apparatus according to claim 1 wherein said logic means also identifies said road segment as having at least a portion inside said subregion in response to said set of electrical signals indicating any one of said start and end coordinates being inside said subregion.

3. Vehicle map position determining apparatus according to claim 2, wherein said logic means includes means for identifying said road segment as being outside said subregion in response to said set of electrical signals indicating said start and end road segment coordinates are each located in one of said corner areas and in a middle side area adjacent said one corner area.

4. Vehicle map position determining apparatus according to claim 3 wherein said logic means includes means for identifying said road segment as outside said subregion in response to said set of electrical signals indicating each of said start and end road segment coordinates being in different ones of said four corner areas which are nondiagonally disposed with respect to said subregion.

5. Vehicle map position determining apparatus according to claim 4 wherein said logic means includes means for identifying said road segments as outside said subregion in response to said set of electrical signals indicating that both of said start and end road segment coordinates are in the same one of said four corner or four middle side areas.

6. Vehicle map position determining apparatus according to claim 2 wherein said utilization means includes means for making a list of all of said road segments identified by said logic means as having at least a portion inside said subregion.

7. Vehicle map position determining apparatus according to claim 1 wherein said utilization means includes means for making a list of all of said road segments identified by said logic means as having at least a portion inside said subregion.

8. Vehicle map position determining apparatus according to claim 1 wherein said set of electrical signals form a four digit binary digital signal, said subregion, said four corner areas and said four middle side areas each corresponding to a different specific four digit value for said digital signal.

9. Vehicle map navigation apparatus according to claim 1 wherein said logic means includes means for positively determining if said road segment has at least a portion inside said subregion for 31 of a total possible 45 different possible locations of said road segment start and end coordinates in said subregion, said four corner areas and said four middle side areas by analysis of said set of electrical signals for each of said start and end coordinates.

10. Vehicle map position determining apparatus according to claim 1 wherein said determining means also includes means for solving equations which define said road segment and at least some of said subregion boundaries to determine if there is an intersection.

11. Vehicle map position determining apparatus according to claim 10 wherein said determining means includes means for identifying said road segments as being within said subregions if an intersection solution for said equations exists.

12. Vehicle map position determining apparatus according to claim 1 wherein said road segments have different start and end coordinates.

13. Vehicle map position determining apparatus according to claim 12 wherein said start and end coordinates of said road segments are expressed in terms of Cartesian coordinates.

14. Vehicle map position determining apparatus according to claim 13 wherein said boundary coordinates of said subregion comprise coordinates which define, in Cartesian coordinates, opposite corners of a rectangular area which forms said subregion.

15. Vehicle map position determining apparatus according to claim 14 wherein said road segments comprise straight line segments which exists between said start and end coordinates.

16. Vehicle map position determining apparatus according to claim 1 wherein said boundary coordinates of said subregion comprise coordinates which define, in Cartesian coordinates, opposite corners of a rectangular area which forms said subregion.

17. Vehicle map position determining apparatus according to claim 16 wherein said start and end coordinates are compared with said opposite corner boundary coordinates to create said set of electrical signals.

18. Vehicle map position determining apparatus according to claim 17 wherein four logic signals, which are part of said set of electrical signals, are created and stored in response to each comparison of each of said start and end coordinates with each of said opposite corner coordinates, and wherein for any particular set of said four logic signals which indicate at least one of said start and end coordinates is within said rectangular area, said corresponding road segment between said start and end coordinates is determined to have at least a portion inside said rectangular area.

19. Vehicle map position determining apparatus according to claim 1 wherein said set of electrical signals provided by said comparison means comprise difference signals which result from said comparison, and wherein said logic means analyzes the signs of said difference signals in order to determine if any of said road segments have at least a portion inside said subregion.

20. Vehicle map position determining apparatus according to claim 19 wherein said logic means also identifies said road segment as having at least a portion inside said subregion in response to said set of electrical signals indicating any one of said start and end coordinates being inside said subregion.

21. Vehicle map position determining apparatus according to claim 20 wherein said logic means includes means for identifying said road segment as outside said subregion in response to said set of electrical signals indicating each of said start and end road segment coordinates being in different ones of said four corner areas which are nondiagonally disposed with respect to said subregion.

22. Vehicle map position determining apparatus comprising:

means for providing coordinates for an estimated vehicle position;

map memory means for storing map data defining fixed road segments which exists in an overall geographical area;

determining means coupled to said map memory means for accessing said map data and determining which of said road segments have at least a portion inside a subregion of said geographical area about said estimated vehicle position, said subregion generally defining a quadrilateral;

map matching means coupled to said determining means for utilizing said map data in said map memory means which defines said road segments determined as having at least a portion inside said subregion and said estimated vehicle position to provide a corrected vehicle position; and

means to provide vehicle navigation/position information to a vehicle user based on the corrected vehicle position;

wherein said determining means includes,

means for receiving, as said map data, data defining start and end coordinates of each of said road segments;

means for defining said subregion in terms of boundary coordinates;

means, coupled to said receiving means and said defining means, for comparing said start and end road segment coordinates with said boundary coordinates and providing, as a result of said comparison, a set of electrical signals defining the location of each of said start and end coordinates with respect to said subregion,

said set of electrical signals defining the location of said start and end road segment coordinates as being inside said subregion or in any one of four corner areas adjacent said subregion or in any one of four middle side areas each between two of said corner areas and adjacent said subregion, and

logic means for identifying any of said road segments as having at least a portion inside said subregion in response to said set of electrical signals indicating each one of said road segment start and end coordinates being in different ones of said middle side areas on opposite sides of said subregion.

23. Vehicle map position determining apparatus according to claim 22, wherein said logic means includes means for identifying said road segment as being outside said subregion in response to said set of electrical signals indicating said start and end road segment coordinates are each located in one of said corner areas and in a middle side area adjacent said one corner area.

24. Vehicle map position determining apparatus according to claim 22 wherein said set of electrical signals provided by said comparison means comprise difference signals which result from said comparison, and wherein said logic means analyzes the signs of said difference signals in order to determine if any of said road segments have at least a portion inside said subregion.