Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2001-01-16
2002-11-19
Zanelli, Michael J. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
Reexamination Certificate
active
06484090
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of data storage techniques. More specifically, the present invention is directed to improved systems and methods for storing geographic data to provide improved efficiency and simpler access to the underlying data.
2. Description of the Related Art
The known car navigation systems require a map with digital road data on a removable storage medium, e.g. a CD-ROM, in order to realize functionality such as calculations of routes between a start and a destination point and displaying a road map on a display screen. In most cases the amount of data to be processed is very large and can be some hundreds of Megabytes. On the other hand, the embedded computer system in the navigation system has very restricted system memory capacity, e.g. 4 Megabytes, which is shared among the various components, such as the operating system and the application software. Therefore, the required amount of digital road data cannot be loaded from the storage medium into the system in one step but is structured in smaller units which can be processed by the computer system. The method of structuring is called parceling and a unit of road data is called a parcel. In addition to this parceling, the application software requires the organization of the road data in several levels to cover different scales for map display and different densities of the road network for route planning. For example, the most detailed level contains road data corresponding to city maps, a less detailed level only contains connector roads between cities and villages and the least detailed level only contains freeways and motorways. The number of levels is not fixed and depends on the characteristics of the area of which the map with road data is stored. The parceling is applied to each level of the map independently.
The method of parceling is described in U.S. Pat. 4,888,698. In that patent, a pattern of rectangular parcels is defined covering the map of which the road data are to be stored, whereby each parcel covers a particular part of the map. The size for the area of a parcel is chosen in such a way that the amount of data stored in the parcel does not exceed a certain maximum amount. The size of this area may be different for different parcels at the same level of the map. So a parcel covering a part of a city may have a small corresponding area whereas a parcel covering a less populated part may have a much larger corresponding area. A map contains line features which extend between two nodes and which have a certain geographical extension, e.g. a part of a road running between two intersections. If such a line feature crosses the border between two parcels, in the known method the line feature is divided into two new line features by adding an additional node at that border and the two new line features together with their nodes are stored into the two parcels. This method has some undesired effects. First, storing the additional nodes requires extra storage space without holding any information about the map itself. In practical situations, the number of additional nodes stored in a parcel can be 20% of the total number of nodes in that parcel. Furthermore, an application program using the stored map requires extra computational effort for processing the additional nodes. For instance, for constructing a route the line features are linked together and every additional node requires an additional link to be made.
SUMMARY OF THE INVENTION
it is an object of the invention to provide a method of the kind set forth which produces a storage medium with a reduced number of additional nodes compared with the known method. This object is achieved according to the invention in a method which is characterized in that each of the parcels has around its standard border a border region bounded by an inner border and an outer border, whereby the inner border of a particular parcel coincides with the outer border of its neighboring parcel in the pattern; and that the step of determining whether the line feature needs to be divided includes determining whether the line feature is fully enclosed by the outer border of a particular parcel and, if this is not the case, deciding that the line feature is to be divided. By making a border region for a parcel and by allowing a line feature to intersect the standard border and not to divide it as long as it remains inside the border region, the number of divided line features and consequently the number of additional nodes is reduced. In the method according to the invention, the network of roads is not sharply cut at the borders between the parcels but the topology of the network is taken into account by checking whether there are ‘natural’ break points in the network in the form of existing nodes near that border. If such break point exists, there is no need to cut the network at an artificial place and there is no need to place an additional node in the network. This advantage is achieved while maintaining the basic regular structure of parcels, which is advantageous for processing the map data, e.g. for displaying the map. The minor disadvantage that a feature at a geographical position in the border region of a parcel may not be stored in that parcel but in its neighboring parcel, can be resolved by retrieving that neighboring parcel.
Adding the additional node to an existing intermediate point has the advantage that no complete new item of information has to be stored. This saves storage space on the storage medium.
It is a further object of the invention to provide a system for producing a storage medium with a map of the kind set forth which produces a storage medium with a reduced number of additional nodes compared with the known system. This object is achieved according to the invention in a system that is characterized in that each of the parcels has around its standard border a border region bounded by an inner border and an outer border, whereby the inner border of a particular parcel coincides with the outer border of its neighboring parcel in the pattern; and that the means for determining whether the line feature needs to be divided are arranged to determine whether the line feature is fully enclosed by the outer border of a particular parcel and, if this is not the case, to decide that the line feature is to be divided. The reduction of the number of additional nodes on the storage medium is advantageous in that it saves storage space and computational effort in the application program using the line features from the storage medium.
It is a further object of the invention to provide a storage medium of the kind set forth with a reduced number of additional nodes compared with the known storage medium. This object is achieved according to the invention in a storage medium that is characterized in that each of the parcels has around its standard border a border region bounded by an inner border and an outer border, whereby the inner border of a particular parcel coincides with the outer border of its neighboring parcel in the pattern, and that the line feature intersects the standard border of a particular parcel while being fully enclosed in the outer border of that parcel. Such storage medium has fewer additional nodes for a given map, since fewer line features have been divided into multiple line features. A line feature is allowed to intersect the standard border, whereby it has not been divided if it does not intersect the outer border as well. So as long as the line feature does not completely cross the border region, it has not been divided. Apart from saving storage space, the storage medium according to the invention also has the advantage that a system using the map data from that storage medium requires less computational effort to process the line features.
It is a further object of the invention to provide a system of the kind set forth which is arranged to read a storage medium with a map according to the invention. This object is achieved according to the i
Lahaije Paul Dominique Marie Etienne
Neukirchner Ernst-Peter
Otto Hans-Ulrich
Mannesmann VDO AG
Mayer Brown Rowe & Maw
Zanelli Michael J.
LandOfFree
Method for producing a storage medium with a map does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for producing a storage medium with a map, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for producing a storage medium with a map will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2992495