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.

Other References

• Robert French, "Map Matching Origin, Approaches and Applications", Second Symposium on Land Vehicle Navigation, Munster, Germany, Jul. 1989 pp. 211-234
• Newman and Sproul, "Principles of Interactive Computer Graphics," 2nd Ed., 1979, pp. 65-67
• Nicholl et al, "An Efficient New Algorithm for 2D Line Clipping: Its Development and Analysis", Computer Graphics, vol. 21, No. 4 Jul. 1987, pp. 253-262
• Robert French, "Automobile Navigation Technology: Where is it Going?" May 25, 1988
• Kaijian et al., "An Efficient Line Clipping Algorithm", Computer and Graphics, vol. 14, No. 2, pp. 297-301, 199