Method and apparatus for geographic coordinate data storage

Abstract

The storage space required for representing geographic features is reduced by determining an optimum number of bits that can be used to store coordinate data along each separate axis. Any coordinate change that cannot directly fit within the optimum bit size is subjected to an escape sequence made up of one or more special values and a normal value that fits in the optimum bit size. The special values are obtained by a predetermined calculation for each bit size. If all changes for one axis are in the same direction and special values are not needed, a global sign can be used to further enhance use of the available space on the storage medium.

Claims

Having thus described the invention, what is claimed is:

1. A microprocessor-implemented method of storing data derived from known coordinate sets which represent a geographic feature and which correspond to coordinate locations along a plurality of coordinate axes, said method comprising the steps of:

(a) computing the changes in the coordinate locations between successive coordinate sets along each coordinate axis;

(b) selecting a plurality of different integers each representing a different allowable number of data bits that may potentially be used for storing the data;

(c) assigning to each different integer a special value that is based on and unique to the corresponding integer;

(d) calculating the number of data bits needed to represent each coordinate change along each coordinate axis using one selected integer as the allowable number of bits, with the number of data bits needed to represent each coordinate change that requires more bits than said one selected integer being calculated by taking into account the special value assigned to said one selected integer and the number of special values needed to allow representation of the coordinate change using said one selected integer as the allowable number of bits;

(e) repeating step (d) using each of the remaining selected integers as the allowable number of bits;

(f) adding, for each different integer used, the number of data bits calculated in steps (d) and (e);

(g) selecting an optimum integer for each coordinate axis by choosing the integer that corresponds to the smallest total number of bits resulting from the addition of step (f) for each coordinate axis; and

(h) storing each coordinate change along each coordinate axis using said optimum integer for the coordinate axis as the allowable number of bits, with each coordinate change that requires more bits than said optimum integer being stored as a normal set of bits no greater in number than said optimum integer combined with one or more additional sets of bits each no greater in number than said optimum integer and calculated as the number of special values needed to represent the coordinate change wherein a determination of an optimum storage size of a geographic database is made on a per feature basis, in the manner described above, such that said determination would result in a reduced requirement for available storage space on a data processing storage medium versus a determination of an optimum storage sized made using the same geographic database as a whole.

2. A method as set forth in claim 1, wherein the special value assigned to each integer is equal to 2.sup..DELTA.size-1, where .DELTA.size is the integer.

3. A method as set forth in claim 1, wherein the number of data bits needed to represent each coordinate change along a coordinate axis is calculated as ##EQU1## is a non-zero integral number and ##EQU2## is other than a non-zero integral number, where N is said number of bits, .DELTA.size is the integer, .vertline.x.DELTA..vertline. is the absolute value of the coordinate change along the coordinate axis, and any faction part of ##EQU3## is discarded.

4. A method as set forth in claim 3, wherein the special value assigned to each integer is 2.sup..DELTA.size-1.

5. A method as set forth in claim 1, including the steps of:

(i) determining whether all changes in the coordinate locations between successive coordinate sets along any coordinate axis are all in one direction;

(ii) determining for said any coordinate axis whether all changes in the coordinate locations can be represented using a number of bits equal to said one selected integer without any special value needed; and

(iii) if the determinations in both steps (i) and (ii) are affirmative, assigning a sign representing said one direction to all of the changes in the coordinate locations along said any coordinate axis and reducing the sum obtained from step (f) by a selected number for said any coordinate axis.

6. A method as set forth in claim 5, wherein said selected number is equal to the number of coordinate sets minus one.

7. A microprocessor-implemented method of storing data representing the location of a geographic feature and derived from known coordinate locations of said feature along a coordinate axis, said method comprising the steps of:

(a) computing the coordinate changes between successive coordinate locations;

(b) selecting a plurality of integers each representing a different number of bits that may be used as the allowable number of bits for storing the data;

(c) assigning to each integer a special value that is determined by the integer value;

(d) using one selected integer and one selected coordinate change,

(i) if ##EQU4## is a non-zero integral number, assigning to said one selected change a bit number equal to ##EQU5## (ii) if ##EQU6## is other than a non-zero integral number, assigning to said one selected change a bit number equal to ##EQU7## where .vertline.x.DELTA..vertline. is the absolute value of said one selected change, N is 2.sup..DELTA.size-1 -1, .DELTA.size is the value of said one selected integer, and any fractional part of ##EQU8## is discarded; (e) repeating step (d) using all other integers and all other coordinate changes;

(f) for each different integer used, adding the bit numbers obtained from steps (d) and (e) for all of the coordinate changes;

(g) selecting an optimum integer equal to the integer corresponding to the smallest sum of bit numbers obtained from step (f);

(h) using said optimum integer and one selected coordinate change,

(i) if ##EQU9## is a non-zero integral number, storing a number of special values equal to ##EQU10## and also storing ##EQU11## (ii) if ##EQU12## is other than a non-zero integral number, storing a number of special values equal to ##EQU13## and also storing ##EQU14## where x.DELTA. is the coordinate change value, N.sub.0 is 2.sup..DELTA.size.sub.0.sup.-1 -1, .DELTA.size.sub.0 is said optimum integer, and any fractional part of ##EQU15## is discarded; and (i) repeating step (h) using said optimum integer and all other coordinate changes wherein a determination of an optimum storage size of a geographic database is made on a per feature basis, in the manner described above, such that said determination would result in a reduced requirement for available storage space on a data processing storage medium versus a determination of an optimum storage sized made using the same geographic database as a whole.

8. A method as set forth in claim 7, wherein the special value assigned to each integer is equal to 2.sup..DELTA.size-1.

9. A method as set forth in claim 7, including the step of assigning a directional sign to all coordinate changes and reducing by a selected number the sum obtained in step (f) for any integer having a bit number assigned thereto in accordance with step (d) that is not greater than the integer, if all coordinate changes are in the same direction.

10. A method as set forth in claim 9, wherein said selected number is equal to one less than the number of coordinate locations.

11. A microprocessor apparatus for storing data representing the location of a geographic feature having known coordinate locations along a plurality of coordinate axes, said apparatus comprising:

means for computing the changes in the coordinate locations between successive coordinate sets along each coordinate axis;

means for calculating the number of bits needed to represent each coordinate change along each axis using each of a plurality of different integers as the allowable number of bits, said calculating means using a special value uniquely assigned to each different integer and calculating the number of special values needed to represent each coordinate change for each different integer;

means for adding the total number of bits calculated for each different integer to represent all coordinate changes along each axis; and

means for storing each coordinate change along each axis using an optimum integer as the allowable number of bits for each axis, said optimum integer for each axis being the integer corresponding to the least total number of bits for such axis; and

means for entering in storage, for each coordinate change, the number of special values needed to represent such coordinate change using said optimum integer wherein a determination of an optimum storage size of a geographic database is made on a per feature basis, in the manner described above, such that said determination would result in a reduced requirement for available storage space on a data processing storage medium versus a determination of an optimum storage sized made using the same geographic database as a whole.

12. Apparatus as set forth in claim 11, wherein the special value assigned to each integer is equal to 2.sup..DELTA.size-1, where .DELTA.size is the value of the integer.

13. Apparatus as set forth in claim 11, wherein said means for calculating is operable to calculate the number of bits needed as equal to ##EQU16## is a non-zero integral number and is equal to ##EQU17## is other than a non-zero integral number, where .DELTA.size is the integer, .vertline.x.DELTA..vertline. is the absolute value of the coordinate change N is 2.sup..DELTA.size-1 -1, and any fractional part of ##EQU18## is discarded.

14. Apparatus as set forth in claim 13, wherein the special value assigned to each integer is 2.sup..DELTA.size-1.

15. Apparatus as set forth in claim 11, including:

means for assigning a sign indicating one coordinate change direction to all coordinate changes along a coordinate axis if all of the coordinate changes along said axis are in said one direction and the number of special values needed to represent each coordinate change along said axis is zero for any integer; and

means for reducing the total number of bits calculated for any such integer by a number equal to the number of coordinate locations minus one.

16. A microprocessor-implemented system for storing data representing the location of a geographic feature having known coordinate locations along a coordinate axis, said system comprising:

means for computing the coordinate changes between successive coordinate locations;

means for selecting a plurality of different integers each representing a potential allowable number of bits used for storing the coordinate changes, each integer having a special value assigned thereto which has a predetermined relationship to the value of the integer;

means for calculating, for each coordinate change, the quantity ##EQU19## is a non-zero integral number and the quantity ##EQU20## is other than a non-zero integral number, where .DELTA.size is the integer value, .vertline.x.DELTA..vertline. is the absolute value of the coordinate change, and N is 2.sup..DELTA.size-1 -1, and any fractional part of ##EQU21## is discarded; means for adding the calculated quantities for all of the coordinate changes for each different integer to obtain a total bit count for each integer;

means for selecting as an optimum integer the integer corresponding to the smallest total bit count; and

means for calculating and storing for each coordinate change a number of special values assigned to the optimum integer equal to ##EQU22## and also storing the quantity ##EQU23## is a non-zero integral number, and a number of special values assigned to the optimum integer equal to ##EQU24## and also storing the quantity ##EQU25## is other than a non-zero integral number, where x.DELTA. is the coordinate change value, N.sub.0 is 2.sup..DELTA.size.sub.0.sup.-1 -1, .DELTA.size.sub.0 is the value of the optimum integer, and any fractional part of ##EQU26## is discarded wherein a determination of an optimum storage size of a geographic database is made on a per feature basis, in the manner described above, such that said determination would result in a reduced requirement for available storage space on a data processing storage medium versus a determination of an optimum storage sized made using the same geographic database as a whole.

17. A system as set forth in claim 16, wherein the special value assigned to each integer is 2.sup..DELTA.size-1.

18. A system as set forth in claim 16, including:

means for assigning a sign indicative of one coordinate change direction to all coordinate changes if all coordinate changes are in said one direction and the absolute value of all coordinate changes are not greater than N; and

means for reducing the total bit count for any such integer by a number equal to one less than the number of coordinate locations.

Description

FIELD OF THE INVENTION

This invention relates generally to the storage of data representing geographic features and more particularly to a method and apparatus for storing geographic coordinate data in a manner to reduce the space it occupies in the storage medium of a microprocessor-implemented data processing system.

BACKGROUND OF THE INVENTION

In a variety of applications, geographic features can be represented by coordinate sets and stored in computer data bases in the form of bits representing the coordinate information. The coordinate information often requires a large amount of storage space on the medium that is used to store it. This always presents a significant problem and becomes particularly undesirable when the storage medium has limited capacity that may not be sufficient to handle the data that must be stored.

Polyline and polygon features can be represented by a starting x-y coordinate pair and a list of coordinate changes between successive coordinate pairs. Geographic features vary widely in size and shape, and some features have large changes in the coordinates while others have only small changes. It is not uncommon, especially with man-made structures, for a feature to have large ranging changes in one coordinate direction and only small changes in the other direction. For example, roadways and grids of streets often follow north-south or east-west paths. Other features, both natural and man-made, exhibit similar characteristics.

SUMMARY OF THE INVENTION

The present invention reduces the storage space that is required to store geographic feature data by taking advantage of the frequent occurrence of features having predominantly only small coordinate changes in one direction. In accordance with the invention, the changes in the coordinates for each geographic feature are examined in both coordinate directions so that these changes can be analyzed and an optimum number of maximum allowable bits can be determined for each coordinate direction. The list of changes in the coordinates can then be packed using a storage size that is optimized for each direction. By determining the optimum storage size for each coordinate direction on a per feature basis rather than for the data base as a whole, there is less waste of available space on the storage medium. Consequently, the storage medium can handle features in a larger geographic area.

The optimum bit number ("delta size") is an integer that is determined by testing each possible delta size for potential use with all of the actual coordinate changes. The delta size for each coordinate direction that results in the fewest total number of bits is selected as the optimum delta size for that coordinate direction. The coordinate changes ("deltas") in each coordinate direction are then packed using the optimum delta size for that direction.

Any actual delta that cannot be represented by the optimum delta size number of bits is stored as an escape sequence. The escape sequence contains one or more special delta values that are predetermined for the delta size that is being used, followed by a normal delta value. Each special delta value indicates that the normal delta value is to be increased by an amount corresponding to the special value times the number of special values that are stored.

In some situations, all of the deltas for one or both coordinate directions may have the same sign; i.e., all coordinate changes may be in the same direction. The present invention takes advantage of this circumstance by applying a global sign to the entire set of deltas when all of them have the same sign. As a consequence, each packed delta value does not require its own individual sign bit, and the space occupied by sign bits can be used for other purposes.

This storage technique provides significant advantages in that it uses the available storage medium space more efficiently in a large number of situations. When one coordinate direction has only small deltas for a given geographic feature while the other coordinate direction has larger ranging deltas, the space otherwise used for the small delta coordinate direction can be used for other data. Also, in a situation where most of the deltas in one direction are small and only a small number of deltas are large, the large delta values do not unduly penalize the remaining small deltas because they are all packed using an optimum delta size that is smaller than the large delta values would otherwise require using a standard storage scheme.

BRIEF DESCRIPTION OF THE DRAWINGS

In the accompanying drawings which form a part of the specification and are to be read in conjunction therewith and in which like reference numerals are used to indicate like parts in the various views:

FIGS. 1A, 1B, 1C, 1D and 1E represent a flow chart for the software which may be used with a computer to implement the method and apparatus of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

The present invention is directed to a method and apparatus for efficiently storing data representing the coordinates of a geographic feature in an efficient manner using a computer and software which is represented in flow chart form in FIGS. 1a-1e. In accordance with the invention, a particular geographic feature having known coordinates which are to be stored is represented by a starting coordinate pair and a list of successive coordinate changes ("deltas"). The starting coordinates and all of the coordinate deltas are stored with the deltas using a maximum allowable number of bits ("delta size") which is optimized for each coordinate direction.

Optimization of the delta size involves making use of an escape sequence for deltas that cannot be represented directly by the delta size number of bits. The escape sequence makes use of special delta values followed by a normal delta value. The optimization technique involves testing all of the coordinate deltas using all of the possible delta sizes and selecting a delta size that results in the fewest total number of bits. A special delta value is assigned to each delta size and is unique to that delta size. The special delta value implies a preselected additional delta length which is set equal to 2.sup..DELTA.size-1 -1. Table 1 below is a table of example delta sizes, the special delta values in hexadecimal form and the additional delta length that is implied by each special value for each example delta size.

                  TABLE 1
    ______________________________________
               Special delta value
                             Additional delta length
    Delta size in bits
               (hexadecimal) implied by special value
    ______________________________________
    2          0 .times. 00000002
                             1
    3          0 .times. 00000004
                             3
    4          0 .times. 00000008
                             7
    5          0 .times. 00000010
                             15
    6          0 .times. 00000020
                             31
    7          0 .times. 00000040
                             63
    8          0 .times. 00000080
                             127
    9          0 .times. 00000100
                             255
    10         0 .times. 00000200
                             511
    11         0 .times. 00000400
                             1023
    12         0 .times. 00000800
                             2047
    13         0 .times. 00001000
                             4095
    14         0 .times. 00002000
                             8191
    15         0 .times. 00004000
                             16383
    16         0 .times. 00008000
                             32767
    17         0 .times. 00010000
                             65535
    18         0 .times. 00020000
                             131071
    19         0 .times. 00040000
                             262143
    20         0 .times. 00080000
                             524287
    21         0 .times. 00100000
                             1048575
    22         0 .times. 00200000
                             2097151
    23         0 .times. 00400000
                             4194303
    24         0 .times. 00800000
                             8388607
    25         0 .times. 01000000
                             16777215
    26         0 .times. 02000000
                             33554431
    27         0 .times. 04000000
                             67108863
    28         0 .times. 08000000
                             134217727
    29         0 .times. 10000000
                             268435455
    30         0 .times. 20000000
                             536870911
    31         0 .times. 40000000
                             1073741823
    32         0 .times. 80000000
                             2147483647
    ______________________________________

                  TABLE 2
    ______________________________________
    BINARY NO.    BASE 10 NO.
    ______________________________________
    10            SPECIAL VALUE
    11            -1
    00            0
    01            1
    100           SPECIAL VALUE
    101           -3
    110           -2
    111           -1
    000           0
    001           1
    010           2
    011           3
    ______________________________________

• Inventors
  Robinson, Stephen C.; Beesley, Darin J.; Walters, Thomas H.;
• Assignee
  Garmin Corporation (TW)
• Published
  Nov-30-1999
• Current US Classes:
  701/200
  701/208
  707/101
  707/102
  707/104.1
  711/170
• Application #
  904642
• International Classes
  G06F 012/02; G06F 009/302
• Field of Search
  711/170 701/200 701/208 701/209 707/100 707/101 707/102 707/104 707/2 708/201 708/203 708/207 364/578 345/202 379/88.1 382/201 382/232 382/244
• Examiner
  Peikari; B. James
• Agent
  Shook, Hardy & Bacon, L.L.P.
• US Patent References:
  4613913
  4646015
  4677563
  4686642
  4734863
  4788645
  4796191
  4811491
  4811613
  4914605
  4939661
  5067081
  5204817
  5247356
  5297051
  5311195
  5426780
  5477458
  5546107
  5559707
  5751612