JPS6311987A - Searching of map data - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a search method for map data, and particularly to a search method for map data in which each position on a road and intersection position on a map is digitized and stored in an in-vehicle navigation device. It is related to.

In recent years, there has been research into in-vehicle navigation devices that guide a vehicle to a predetermined destination by storing map information in a memory, reading the map information from the memory, and displaying the map information along with the vehicle's current location on a display device. , has been developed.

Such navigation devices detect the vehicle's travel distance and direction based on output data from a travel distance sensor, a direction sensor, etc. mounted on the vehicle, and estimate the vehicle's current location, which changes from moment to moment, based on this. , the current location is displayed on the map displayed on the display.

In this case, it is preferable that the current location is always displayed on the road on the map, so that the vehicle is guided to the road or intersection closest to the current location. In order to perform this pull-in, it is necessary to search the map data for the road or intersection closest to the current location, but if the search area is wide, the search will take a long time, and the This means that the changing current location cannot be displayed smoothly.

The present invention has been made in view of the above-mentioned points, and an object of the present invention is to provide a map data search method that speeds up the search and enables smooth display of the current location of a vehicle. .

The method for navigating map data according to the present invention is that when each position on the road and intersection position on the map is digitized and stored as map data, the map is subdivided and stored in area units, and When searching for the nearest location or the closest intersection, the search is performed in units of areas to which the current location belongs.

Fruit - one thought, one appearance Embodiments of the present invention will be described below based on the drawings.

FIG. 1 is a block diagram showing the configuration of an in-vehicle navigation device according to the present invention. In the figure, 1 is a geomagnetic sensor for outputting vehicle azimuth data based on geomagnetism, 2 is an angular velocity sensor for detecting the angular velocity of the vehicle,
3 is a mileage sensor for detecting the distance traveled by the vehicle;
4 is GP3 (Global Po5tionino) for detecting the current location of the vehicle from latitude and longitude information, etc.
The output of each of these sensors (devices) is supplied to the system controller 5.

The system controller 5 has an interface 6 which inputs the outputs of each sensor (device) 1 to 4 and performs A10 (analog/digital) conversion, etc., and a system controller 5 which processes various image data and receives outputs from each sensor sequentially from the interface 6. (Device) CPU that calculates the amount of movement of the vehicle, etc. based on the output data of 1 to 4 <Central processing circuit) 7
, a ROM (read-only memory) 8 in which various processing programs of the CPU 7 and necessary information are stored in advance, and a RAM (read-only memory) 8 in which information necessary for executing the programs is written and read. a random access memory) 9, a recording medium 10 consisting of a so-called CD-ROM, an IC card, etc., on which digitized (numerical) map information is recorded, and a V-RAM (Vid
a graphic memory 11 consisting of a
Graphic data such as a map sent from the CPU 7 is drawn in the graphic memory 11 and CR as an image.
It is comprised of a graphic controller 13 that controls the display 12 such as T. The input device 14 consists of a keyboard or the like, and various commands are issued to the system controllers 0 to 5 by the user's keystrokes.

Map information is recorded on the recording medium 10, and its data structure will be explained below.

First, as shown in Figure 2 (A), the entire map of Japan is divided into, for example, 1
It is divided into 6384 (=2') [m] square (7) meshes, and one mesh at this time is called a territory.

The territory is Terri 1 (TX).

Ty), and each territory is assigned a territory number based on, for example, the lower left territory in the figure. Territory No. is the current location (Crntx.

Crnty). Territory is the largest management unit in this data structure. The entire structure of the map data file is shown in Figure 2 (B).
As shown in Figure 2 (C), the D file contains the territory number, the start address in the file for (Tx, Ty), the latitude of the bottom left of the territory (real number), and the longitude of the bottom left of the territory (real number). , geomagnetic declination (real number), and other data are written for each territory.

The territory file is the most important file in this data structure, and various map data and data necessary for map drawing are written therein. In FIG. 3A, the navigation ID and section table are files for searching roads and intersections in navigation, the picture ID is a file for display management, and the data from road section data to intersection data is actual map data. As shown in Figure 3 (B), the map data has an alternating layer structure, with the bottom layer being polygon data for rivers, oceans, lakes, etc., the top layer being line data for roads, railways, etc., and the top layer being various types of data. Character data such as marks, etc., above that is character data such as place names, and the top layer is intersection data. The intersection data on the top layer is data used for intersection drawing, which will be described later, and is not displayed on the display.

Next, as shown in FIG. 4 (A>), one territory is divided into, for example, 256 parts, and the resulting
4 (2”) [m] square mesh is called a unit.This unit also has unit number, (Nx, Ny)
Managed by, its no.

('Nx, Ny) is the current location (Crntx, Crnt
y). A unit is an intermediate management unit, and map information is recorded in this unit, and a collection of 256 units constitutes a territory file. Maps are drawn based on this unit, so it can be called the basic unit of drawing. As shown in Figure 4 (B), the Navi ID file contains data such as the line start address, intersection start address, road section start address, and intersection start address in the file for unit N00 (Nx, Ny>) for each unit. is written in.

Furthermore, as shown in FIG. 5 (△), one unit is divided into, for example, 16, resulting in 256
) [m] square mesh is called a section. This section is similarly managed by section No. (Sx, Sy), and the current location (Crntx) is
, Crnty). A section is the smallest management unit, and information on line segments (roads, etc. are represented by connections of l!! minutes) and intersections within this range is shown in Figure 5 (B
) and (C) as section tables, and as section data as shown in FIG. 6 <A>, (B) and FIG. 7 (Δ>, (B)) in the territory file.

Furthermore, as shown in FIG. 3(A), the territory file includes a file called picture ID for display management. In this example, the scale of the map data is set to three types, for example, 1/25,000, 1/50,000, and 1/100,000, and the actual map data is set to 2, which is the largest scale. I only have one in 50,000. The map of each scale is divided into areas as shown in each figure (A> of FIGS. 8 to 10), and this area is divided into areas N o , (A
nx.

Any). Area No. <Anx,
Any) is determined from the current location (Crntx, Crnty). If the scale is 1/25,000, area No.
and unit number are the same, and in the case of 1/50,000, it is 1
One area corresponds to 4 unit files, and in the case of 1/100,000, one area corresponds to 16 units.

In addition, the picture ID of each scale includes the beginning of polygon, line, character, and character data necessary to display the map of that scale, as shown in each figure (B) of Figures 8 to 10. Address and data size are recorded.

Next, polygon data and line data will be explained. The polygon data and line data are shown in Figure 11 (A>
As shown in Figure 12 (A>), it is represented by a connected vector (line segment) represented by a starting point and an ending point. If you represent a map with a scale of 1/100,000 or 1/100,000, the distance between the starting point and the ending point will shrink, so it may not be necessary to display all the points based on what you see on the display.Taking this into consideration Figure 11 (
B) and as shown in FIG. 12(B), each thinning bit of polygon and line data is entered in advance. Then, the number of line segments (vectors) to be displayed can be reduced by checking the thinning bits when displaying each scale and removing points containing information in the thinning bits as necessary.

Furthermore, as shown in Figure 13 (A>), all the intersections within one unit are given serial numbers (x n, yn).
There are various types of roads, such as 5 branch roads, but especially at intersections where there are multiple roads with similar directions, when passing through this intersection, the sensor accuracy, total error, map accuracy, etc. may cause you to select the wrong road, and the screen may appear. There is a possibility that the road on which the current location is displayed does not match the road on which the driver is actually driving. Therefore, for such intersections, the 13th
As shown in Figure (B), difficulty data indicating the yli difficulty of the intersection is stored in the difficulty bit in the intersection data. When passing through an intersection, by performing processing based on this difficulty level data, it is possible to prevent the wrong road from being selected. The processing will be explained later.

Next, regarding the display of map data, a case will be described in which, for example, a V-RAM is used as the graphic memory 11. As shown in FIG. 14(A), the display configuration is a 512 (dot) x 512 (dot) V-RAM.
The screen above is divided into 16 areas, and each area has an independent 1
Display multiple maps. 1 area is 1 unit of 128 dots) x 128 (dots), and 1 unit
By dividing into 6 areas, 1 area is 32 (dots) x 32
(dot) (Figure 14 (B), (
(See C). An actual in-vehicle display has 256 (dots)
A 56 (dot) area (encircled by a thick line) is displayed, and this area moves on the V-RAM to express the movement of the vehicle's current location.

Next, the basic steps executed by the CPU 7 are explained in the first
This will be explained according to the flowchart in FIG.

The CPU 7 first performs initialization to execute the program (step S1), and then determines whether the current location of the vehicle has been set (step 32). If the current location has not been set, a current location setting routine is executed (step S3), in which the current location is manually set using keys on the input device @14, for example. Next, the mileage is reduced to zero (step S4), and it is then determined whether there is any key input from the input device 14 (step S35).

If there is no key personnel available, a map of the area around the current location is displayed on the display 12, and the current location of the vehicle and its direction are displayed on this map using, for example, a vehicle mark, and when the vehicle moves, the map scrolls as the vehicle moves. Furthermore, when the vehicle position is likely to exceed the range of the map data currently on the graphic memory 11, the necessary map data is read out from the recording medium 10 and displayed on the display 12 (step S6).

If there is key human power, the current location is reset (step S7) and sensor correction (step S8) according to the input data.
, destination setting (step 89), and map enlargement/reduction (step 510) routines are executed.

In addition, the CPU 7 receives an interrupt from the timer, and the 16th
As shown in the figure, a process is performed in which the direction of the vehicle is constantly determined based on the output data of the geomagnetic sensor 1 and the angular velocity sensor 2 at regular time intervals (step S11.512).

Furthermore, when data is input from the mileage sensor 3, the CPU 7 performs interrupt processing by the mileage sensor. In this interrupt process, as shown in FIG. 17, the current location is calculated from the travel distance and direction (step 513), right turn or left turn is determined (step 514), turning to the road (step 515), intersection drawing (snap), etc. 816), and retraction based on mileage (step 517) is performed.

Note that each process in steps 313 to 817 will be explained in detail later.

In addition, the latitude and longitude data obtained from the GPS device 4 are
As shown in FIG. 18, the data is processed by a GPS data reception interrupt, and the coordinates are converted as current location data (step 818).

The travel distance of the vehicle is determined from the output of the travel distance sensor 3. As this mileage sensor 3, for example, a sensor configured to calculate the mileage by integrating the distance of one revolution from the rotation speed of the car's so-called speedometer cable (637 revolutions/Km according to the JIS standard) is used. , it is inevitable that errors will occur in the travel distance obtained due to the accuracy of the sensor 3. Also, the accuracy of the sensor 3 (not the map accuracy, changes in tire air pressure, slip, etc.) are also factors in the error in the mileage. Therefore, unless you correct the mileage frequently, it will not be accurate. This makes it impossible to calculate the distance.

Therefore, by calculating the distance correction coefficient rs from the actual measured distance obtained from the output of the mileage sensor 3 and the distance obtained from the map data, and performing distance correction using this correction coefficient rs, the mileage can always be accurately determined. It can be detected.

Further, the direction of the vehicle is determined from the output of the geomagnetic sensor 1. This azimuth detection method is described in Japanese Patent Application No. 60-282341 filed by the present applicant and others.

The north indicated by this geomagnetic sensor 1 is magnetic north, not map north. Therefore, if the magnetic north is deviated from the map north, the estimated current location P1 obtained from the output of the geomagnetic sensor 1 when traveling a certain distance from the reference position will be different from the actual current location P2, as shown in FIG. This will result in a deviation. Therefore, it is necessary to convert the orientation determined by the geomagnetic sensor 1 into a map orientation.

As shown in FIG. 20, this conversion work is performed using a rotation angle determined by two-dimensional geometric coordinate conversion, that is, an orientation correction coefficient θS. This azimuth correction coefficient θS varies depending on the region, and the mounting error that occurs when the geomagnetic sensor 1 is attached to the vehicle body also varies depending on the error. This direction correction coefficient θS
As shown in FIG. 21, the coefficient can be set to zero and the vehicle travels between two points whose positions are known, and can be determined from the error between the current location and the arrival point determined by inertial navigation.

By correcting the direction using this direction correction coefficient θS, the direction of the vehicle can always be accurately detected.

Note that the method for calculating the distance correction coefficient rs and the direction correction coefficient θS is described in the specification of Japanese Patent Application No. 1982-282344 by the present applicant and others.

Next, the mileage sensor 3 executed by the CPU 7
The interrupt processing procedure will be explained according to the flowchart of FIG. 22. Based on the output data of the mileage sensor 3, the current location is estimated at any time, and the current location H
This routine is called as the H routine at a predetermined timing.

First, the CPU 7 determines whether or not the vehicle has traveled a unit distance of 10 (step S20). Here, the unit distance refers to a certain distance actually traveled by the vehicle, for example, 20 [m].
is set to . Then, this routine is executed every certain distance traveled, and first, the relationship with the map data, that is, the distance 111jj1m to the nearest line segment, the angle θn between that line segment and the north of the map, etc., as shown in Fig. 23, are determined. When there are two or more line segments approximately equidistant, this fact is indicated with a flag (step 521). It is also possible to determine the number of intersections, presence or absence of nearby intersections, etc. here. Next, it is determined whether the distance ρm exceeds a preset threshold fJth (
Step 522). If not, the error IJm is corrected, assuming that the current location is in the vicinity of that line segment (step 523). This error numerator Jm is caused by a detection error of the mileage sensor 1-3, a digitization error of the map data, and the like.

This correction is done in order to recognize the current location next time.
This is because it is necessary to cancel those errors. Thereafter, the process proceeds to a pattern drawing routine to be described later.

On the other hand, if the distance j1m exceeds the threshold r th,
Next, it is determined whether the vehicle has made a curve (turn right or left) (step 524). For information on how to detect curves,
This will be discussed separately later. If the curve does not occur, the difference between the vehicle's traveling direction θ obtained from the output data of the geomagnetic sensor 1 and the line segment angle θn is compared with a set reference value θth (step 525). If 1θ-θnl>θth, the process proceeds to the pattern pull-in routine without doing anything. In this case,
For example, there may be cases where the user is heading towards the end of a crossroads, or driving on a road that is not stored as map data. Next, it is determined whether there is a more difficult intersection with a smaller angle, such as a Y-junction, in the vicinity (step 826). If there is a Y-junction nearby, for example, there is a possibility that the vehicle will be drawn into a road different from the one on which it is currently running, so the process proceeds to the pattern drawing routine without doing anything.

Since the data indicating the difficulty level of the intersection is inserted in advance into the difficulty level bit of the intersection data as shown in FIG. 13(B) when the map is digitized, the CPU 7
All you have to do is check this bit.

If the above two conditions do not apply, it is determined that an error has occurred in the sensor or the like and the road data is starting to deviate from the road data. In this case, the current location is corrected, that is, it is included in the road data (step 527).

As shown in FIG. 24, the new current location measurement point P cpd is determined by the nearest line segment L1. : Set as the point that intersects with the vertical line drawn down, and change the display, etc. Distance jm and coordinates of current estimated point PCp (
X m, Y m) are the correction values at that point,
It is stored for use in the pattern acquisition routine described later.

If it is determined in step 824 that the force has been released, the intersection pull-in routine is entered. First of all, the previous intersection was H7B.
Find the traveling distance ρC from the point where the travel distance ρC
is multiplied by a constant [i a c to be the intersection detection threshold u Cth (step 328). Constant value aC
is a value related to the accuracy of the mileage sensor 3, and λ is 0.
The value should be about 0B.

The distance 5Jc from the current location Pcp to each intersection is determined from the intersection data included as map data (step S29), and it is determined whether there is an intersection where J c <fJ cth (step 530).

In step S30, a certain distance range (for example, several hundred meters)
] It is also judged whether or not it is within the range (degree). Here, if no intersection exists, the process proceeds to a pattern pull-in routine. In addition, it is determined that there are multiple nearby intersections and the distances IJc to the intersections are about the same, so it is not possible to identify the nearby intersections (
If step 531) is performed, the process also proceeds to the pattern pull-in routine.

If a nearby intersection is specified, that intersection is selected as a new current location estimation point P cpd (step 532). At this time, the distance fJc to the intersection and the coordinates (X c, Y c) of the current location Pcp are stored as a pull-in base. Furthermore, the estimated current location point P cpd is stored (updated) as a new recognized intersection. As a result, when the current location of the vehicle deviates from the road on the map displayed on the display 12, the current location of the vehicle is forcibly placed on the intersection on the map, so-called intersection pulling is performed.

Next, the distance and direction correction coefficients rs and θS are updated based on the coordinates of the intersection recognized last time, the sum of correction values therefrom, and the coordinates of the current location (step 533). In this way, every time an intersection is recognized or when the distance between intersections is long, the number of roads is 1! If the distance and direction correction coefficients rs and θS are updated every time the vehicle travels by tllp, it becomes possible to estimate the current location with higher accuracy.

Next, pattern pull-in will be explained. This routine is constant! It is executed after running for tNpo. The distance fJ po has a value of 1000 [m], for example. Note that if intersection recognition is performed in step 831, the travel distance is reset.

A constant path! While traveling 11ρpo, the distance fJm to the nearest line segment is n=jl po/if o [times]
The n error correction amounts ei are stored as data. Furthermore, for one measurement, the error correction amount e i-1 from the previous measurement and the current error correction amount ei
It is assumed that the difference between the two values is calculated as a change 1ici (ei - ei-1).

When it is determined that you have run only a certain distance j5jpo (step 5)
34), step 535) to calculate the variation in the value of the amount of change C1, and then the deviation α.

6). This value α is then compared with a predetermined threshold αthh (step 537). This value α is determined by taking into account detection errors of each sensor, travel distance, and the like. α〉
In the case of αthh, it is determined that pull-in is not possible, and pattern pull-in is not performed. On the other hand, if α is αthhh, it is further determined in step 83 whether or not retraction is currently being performed.
8) If the pull-in has not been performed, that is, if the current location is located outside the road data, the pull-in is performed to the line segment closest to the current location (step $39). Furthermore, compared with the threshold αtM determined in the same way as the threshold αthh, in step 540), when α<α11+9, the distance and direction correction coefficients rs and O3 are updated (step 541).
).

With the above method, it is possible to re-enter another road after driving off the road. In other words, if the vehicle travels on a road that has not been digitized and then travels again on a digitized path, the road will be recognized after a certain distance has been traveled, making it possible to accurately estimate the current location. Also, for a constant distance J po, a better distance U
It is also possible to calculate the deviation with respect to t and shorten the distance 1!1fJpo to improve accuracy and make the response times similar. The situation is shown in FIGS. 25(A) and 25(B).

As described above, pulling to the nearest intersection or drawing to the nearest neighboring line segment is performed. ) is required.

Searching for the latest intersection or nearest line segment requires a lot of line segment or intersection data, that is, if the search area is wide, it takes time, and the current location, which changes constantly, cannot be displayed smoothly. become. However, in this embodiment, as is clear from the data structures shown in FIGS. 2 to 5, the search area from the current location is made as small as possible, and the data of line segments and intersections that fall into that area are managed. By having data (section data, section table), it is possible to search for line segments and intersections within the minimum unit section as a search area, thereby reducing the time required for the search. The procedure executed by the CPU 7 to search for the nearest line segment and nearest intersection from the current location will be described below with reference to the flowchart of FIG. 26.

CPLj7 first displays the current location (crntx, cril
ty) to Territory No., (Tx, Ty), lnit No., (Nx, Ny), Section No., (Sx.

(Steps 850 to 552).

This can be determined by a simple calculation (division) since each area is divided into 2 units. Next, the section is set as a cheria, and the line segments and intersection data existing in this section are loaded by referring to the section table and section data (steps 353 to 55).
5). Based on the loaded data, calculate the distance from the current location to all line segments in the search area (the length of the perpendicular to the line segment) and the distance to all intersections, and compare them to find the nearest line segment. A recent intersection point can be obtained (step 856). The speed of searching is proportional to the number of line segments and the number of intersections, but according to the search method based on the data structure described above, the search area (section) is small and the number of line segments to be calculated is proportional to the number of line segments and intersections. Since there are fewer intersections and intersections, high-speed searches are possible.

By the way, when displaying map data at various scales in a navigation system, if you have map data at all scales, the display can be done easily and quickly, but on the other hand, the disadvantage is that the data size increases. There is 1-. On the other hand, if the map has only large-scale map data and other scales are represented by simple reduction, the data size will be smaller but the display will be slower.

In contrast, in this embodiment, as is clear from the data structure shown in FIGS. 8 to 10, in order to reduce the data size, only the map data of the largest scale is included, and in addition, map data of other scales are included. When displaying data, display management files and thinned data are used to speed up the display. Hereinafter, the procedure for enlarging/reducing the map executed by the CPU 7 will be explained according to the flowchart of FIG. 27.

When the CPU 7 first determines that the scale to be displayed has been manually entered from the input device 9, (step 560),
Find the area No, (Anx, △ny>) corresponding to the scale from the current location (Crntx, Crnty) (steps 861-563), then refer to the picture ID of that scale (steps 364-866), and calculate the start address and data. The map data is loaded depending on the size and drawn in each of the 16 areas on the V-RAM (step 567). In this way, the picture ID for display management makes it possible to reference the identified map data to be displayed (as the scale becomes smaller, the displayed roads, place names, etc. are narrowed down to important ones), which speeds up the display. can be realized.

Also, for polygon and line data, as explained in Figures 11 and 12, information to that effect is included in the thinning bits of points that can be omitted from display, so When drawing maps of 1/100,000 or 1/100,000,
The thinned out bits are checked (step 568), and the points targeted for thinning are drawn (step 569). In this way, when the map is reduced, the number of line segments to be displayed can be reduced by thinning out the points that can be visually omitted when displayed on the display. This makes it possible to achieve faster speeds.

Note that in the above embodiment, a thinning bit is provided for polygon and line data, and information to that effect is entered in the thinning bit for points that can be omitted from display. Plot it with
The same effect can be obtained by thinning out images according to a predetermined rule (for example, skipping by one in the case of a scale of 1/50,000, skipping by four in the case of a scale of 1/100,000, etc.) at the time of display.

Next, step 82 in the flowchart of FIG.
The method for determining the curve (right turn/left turn) in No. 4 will be explained.

Basically, a right turn or a left turn is determined based on the output data of the azimuth sensor, for example, the geomagnetic sensor 1, and when a turn is detected, the intersection is pulled through the process from step 828 onwards. However, the geomagnetic sensor 1 is sensitive to external disturbances, and its output data will contain a large error when a large vehicle (for example, a truck or a bus) passes by the vehicle, such as when passing through a railroad crossing or a railway bridge. If this data is used as it is to judge whether to turn right or left, the vehicle will mistakenly think that the vehicle has turned when it was traveling straight and will pull into the intersection even though it is not even an intersection, causing the current location to deviate from the correct location.

Therefore, in this embodiment, the radius of curvature and vehicle speed are included in the criteria to determine whether the vehicle has turned.
This makes it possible to accurately judge whether to turn right or left. Below, C.P.
The procedure of the right-turn/left-turn judgment method executed by U7 will be explained according to the flowchart of FIG. 28.

First, the CPU 7 moves from a certain distance (for example, 15 [m]
) when the vehicle turns at a certain angle (for example, 40 degrees) or more, it is determined that the vehicle has made a curve (turn right or left) (step 370). However, when the curve is made, the radius of curvature R at that time is a constant value Rmi which is the minimum radius of rotation for the judgment criterion.
n (for example, 3.5 [m]) or less, it is determined that the data is wrong and it is not determined that the curve is curved (step 571).

This is because the vehicle cannot turn below its minimum turning radius. Furthermore, if the vehicle speed S exceeds a certain maximum judgment standard speed of 3max (e.g. 40 [Km/h]), it is normally unthinkable to turn at an intersection; (Step 572).Also, to determine whether to turn right or left, for example, if east is 0 degrees, north is 90 degrees, west is 180 degrees, and south is 270 degrees, then the direction is increased or decreased. (Step 573).In other words, the direction in which the bearing increases is a left turn (Step 574), and the direction in which the bearing decreases is a right turn (Step 575).
It is possible to determine a left turn.

Note that the radius of curvature R is determined at a certain point a, as shown in FIG.
If the angle between the vehicle's direction at point A and the vehicle's direction at point A, which has traveled a certain distance 1 from point a, is θ [radian], then j=R・θ, so it can be obtained by transforming this equation. It can be determined from the following formula R=fJ/θ.

In addition, the current location is controlled so that it is always located on the road shown on the map displayed on the display by the intersection pull-in, etc. performed by the process according to the flow shown in Figure 22. However, for example, if the distance between intersections is long, If so, the current location will be slightly corrected during that time, but due to distance errors due to sensor accuracy, calculated 1L map accuracy, etc., there may be a distance difference between the actual current location from the last intersection and the current location on the map. This error increases as the distance between intersections increases. In such a case, if there are a plurality of intersections close to each other in the vicinity of the intersection where the vehicle should pull in next, there is a possibility that the vehicle will pull in at the wrong intersection. Therefore, in this embodiment, after traveling a certain distance between intersections,
We are trying to pull in based on so-called mileage. Hereinafter, the procedure will be explained according to the flowchart of FIG. 30.

First, initial values are set (step 880). As this initial value, a fixed current location is required, but this can be set by the user first, or the current location when pulling into a fixed point such as an intersection can be used, or if the current location has already been fixed, If the data is registered in the non-Normal memory, it only needs to be set once. The mileage is reset to zero at this confirmed current location (Step 581), whether the user turns at an intersection (Step 582), or whether the driver has traveled a certain distance (Step 583). A point at a certain distance from the previously detected position on the zero-reset map is found, the current location is changed to that point, and the pull-in is performed (step 584). While driving a certain distance, the vehicle's current location is drawn on the road on the map displayed on the display by drawing a perpendicular line to the line segment closest to the top and drawing it to the intersection (step 585). can be set. If it is detected that the vehicle has turned, the intersection pull-in is performed (step 886). This intersection lead-in is as described above.

In addition, the distance traveled can be effectively used to determine whether the vehicle has turned at an intersection. In other words, it is possible to determine a curved intersection from the map data based on the distance between the intersections and the travel distance.

As explained above, according to the present invention, when each position on the road and the intersection position on the map is digitized and stored as map data, the map is subdivided and stored in area units. When serving the nearest position on the road or the most recent example sentence destination from the vehicle's current location, by doing so in units of areas to which the current location belongs, the calculation time required to search for the nearest location or nearest intersection can be greatly reduced. Since the search time can be shortened, the search speed can be increased, and the current location can be displayed smoothly as the vehicle travels.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing the configuration of an in-vehicle navigation device according to the present invention, and FIGS. 2(A) to 13(C) to 13(
A) and (B) are diagrams showing the data structure of the map information stored in the recording medium in FIG. 1, and FIG.
) is a diagram showing the screen configuration on the V-RAM, FIGS. 15 to 18 are flowcharts showing the basic procedures executed by the CPLI in FIG. 1, and FIGS. 19 to 21 are
The figure shows how to obtain the direction correction coefficient θS, and Fig. 22 shows C
Flowchart showing the procedure of the intersection drawing routine and the pattern drawing routine executed by the PU, 2nd
Figures 3 and 24 are diagrams showing the positional relationship between the current location on the map and the nearest line segment, Figure 25 is a diagram showing Haku's method of drawing into a road, and Figure 26 is a diagram showing the positional relationship between the current location on the map and the nearest line segment, and Figure 26 is a diagram showing the nearest line segment and intersection. 27 is a flowchart showing the procedure for enlarging/reducing the map; FIG. 28 is a flowchart showing the procedure for determining whether to turn right or left;
Fig. 9 is a diagram showing how to obtain the radius of curvature, and Fig. 30 is a flowchart showing the procedure for retracting the travel distance. Explanation of symbols of main parts

Claims (1)

[Claims] When each position on the road and the intersection position on the map are digitized and stored as map data, the map is subdivided and stored in area units, and the nearest position on the road or the nearest intersection from the current location of the vehicle is A search method for map data, characterized in that when searching for , the search is performed in units of areas to which the current location belongs.