Method and apparatus for geographic coordinate data storage

• US 5,995,970 A
• Filed: 08/01/1997
• Issued: 11/30/1999
• Est. Priority Date: 08/01/1997
• Status: Expired due to Term

• Current Assignee: Garmin Corporation (Garmin Limited)
• Original Assignee: Garmin Corporation (Garmin Limited)
• Inventors: Beesley, Darin J., Walters, Thomas H., Robinson, Stephen C.
• Primary Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US08/904,642
• Time in Patent Office: 851 Days
• 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
• US Class Current: 1/1
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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

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.Δ

size-1, where Δ

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, Δ

size is the integer, |xΔ

| 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.Δ

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 |xΔ

| is the absolute value of said one selected change, N is 2.sup.Δ

size-1 -1, Δ

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Δ

is the coordinate change value, N₀ is 2.sup.Δ

size₀^-1 -1, Δ

size₀ 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.Δ

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.Δ

size-1, where Δ

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 Δ

size is the integer, |xΔ

| is the absolute value of the coordinate change N is 2.sup.Δ

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.Δ

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 Δ

size is the integer value, |xΔ

| is the absolute value of the coordinate change, and N is 2.sup.Δ

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Δ

is the coordinate change value, N₀ is 2.sup.Δ

size₀^-1 -1, Δ

size₀ 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.Δ

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.