Method and system for storage and fast retrieval of digital terrain model elevations for use in positioning systems

1. A method to retrieve elevation data, the method comprising:

locating a first compressed portion of a Digital Elevation Model (DEM) using a first index, the Digital Elevation Model comprising a plurality of compressed portions which are portions of compressed profiles in a first tile of the Digital Elevation Model, the compressed portions stored in one of: a Memory Mapped File (MMF), Random Access Memory (RAM), and a file in a file system on a digital processing system, the plurality of compressed portions including the first compressed portion, the first index pointing to a storage location where the first compressed portion is stored;

decompressing the first compressed portion to retrieve first elevation data for at least one sample point in the Digital Elevation Model;

identifying the first tile, the first tile containing a first location and being one of a plurality of tiles in an area of the Digital Elevation Model; and

identifying a first profile that is in the vicinity of the first location, the first compressed portion being a portion of the first profile.

2. A method as in claim 1 wherein said decompressing the first compressed portion comprises:

run length decoding the first compressed portion to generate scaled elevation data;

inverse scaling the scaled elevation data to generate normalized elevation data; and

adding a reference elevation to the normalized elevation data to generate the first elevation data.

3. A method as in claim 1 further comprising:

identifying a plurality of sample points in the vicinity of a first location;

retrieving elevations of the plurality of sample points from the Digital Elevation Model; and

computing an elevation of the first location from an interpolation using the elevations of the plurality of sample points.

4. A method as in claim 3 further comprising:

performing a coordinate transformation to express a horizontal position of the first location in a coordinate system used by the Digital Elevation Model.

5. A method as in claim 3 further comprising:

providing the elevation of the first location to a Position Determination Entity to perform altitude aiding in a positioning system.

6. A method as in claim 5 wherein said computing the elevation of the first location comprises:

performing a coordinate transformation such that the elevation of first location is expressed in a coordinate system used by the Position Determination Entity.

7. A machine readable media containing executable computer program instructions which when executed by a digital processing system cause said system to perform a method to retrieve elevation data, the method comprising:

locating a first compressed portion of a Digital Elevation Model (DEM) using a first index, the Digital Elevation Model comprising a plurality of compressed portions which are portions of compressed profiles in a first tile of the Digital Elevation Model, the plurality of compressed portions stored in one of: a Memory Mapped File (MMF), Random Access Memory (RAM), and a file in a file system on a digital processing system, the plurality of compressed portions including the first compressed portion, the first index pointing to a storage location where the first compressed portion is stored;

decompressing the first compressed portion to retrieve first elevation data for at least one sample point in the Digital Elevation Model;

identifying the first tile containing a first location and being one of a plurality of tiles in an area of the Digital Elevation Model; and

identifying a first profile that is in the vicinity of the first location, the first compressed portion being a portion of the first profile.

8. A media as in claim 7 wherein said decompressing the first compressed portion comprises:

run length decoding the first compressed portion to generate scaled elevation data;

inverse scaling the scaled elevation data to generate normalized elevation data; and

adding a reference elevation to the normalized elevation dan to generate the first elevation data.

9. A media as in claim 7 wherein the method further comprises:

identifying a plurality of sample points in the vicinity of a first location;

retrieving elevations of the plurality of sample points from the Digital Elevation Model; and

computing an elevation of the first location from an interpolation using the elevations of the plurality of sample points.

10. A media as in claim 9 wherein the method further comprises:

performing a coordinate transformation to express a horizontal position of the first location in a coordinate system used by the Digital Elevation Model.

11. A media as in claim 9 wherein the method further comprises:

providing the elevation of the first location to a Position Determination Entity to perform altitude aiding in a positioning system.

12. A media as in claim 11 wherein said computing the elevation of the first location comprises:

performing a coordinate transformation such that the elevation of first location is expressed in a coordinate system used by the Position Determination Entity.

13. A digital processing system to retrieve elevation data, the digital processing system comprising:

means for locating a first compressed portion of a Digital Elevation Model (DEM) using a first index, the Digital Elevation Model comprising a plurality of compressed portions which are portions of compressed profiles in a first tile of the Digital Elevation Model, the plurality of compressed portions stored in one of: a Memory Mapped File (MMF), Random Access Memory (RAM), and a file in a file system on a digital processing system, the plurality of compressed portions including the first compressed portion, the first index pointing to a storage location where the first compressed portion is stored;

means for decompressing the firm compressed portion to retrieve first elevation data for at least one sample point in the Digital Elevation Model;

means for identifying the first tile, the first tile containing a first location and being one of a plurality of tiles in an area of the Digital Elevation Model; and

means for identifying a first profile that is in the vicinity of the first location, the first compressed portion being a portion of the first profile.

14. A digital processing system as in claim 13 wherein said means for decompressing the first compressed portion comprises:

means for run length decoding the first compressed portion to generate scaled elevation data;

means for inverse scaling the scaled elevation data to generate normalized elevation data; and

means for adding a reference elevation to the normalized elevation data to generate the first elevation data.

15. A digital processing system as in claim 13 further comprising:

means for identifying a plurality of sample points in the vicinity of a first location;

means for retrieving elevations of the plurality of sample points from the Digital Elevation Model; and

means for computing an elevation of the first location from an interpolation using the elevations of the plurality of sample points.

16. A digital processing system as in claim 15 further comprising:

means for performing a coordinate transformation to express a horizontal position of the first location in a coordinate system used by the Digital Elevation Model.

17. A digital processing system as in claim 15 further comprising:

means for providing the elevation of the first location to a Position Determination Entity to perform altitude aiding in a positioning system.

18. A digital processing system as in claim 17 wherein said means for computing the elevation of the first location comprises:

means for performing a coordinate transformation such that the elevation of first location is expressed in a coordinate system used by the Position Determination Entity.

19. A method to retrieve elevation data, the method comprising:

locating a first compressed portion of a Digital Elevation Model (DEM) using a first index, the Digital Elevation Model comprising a plurality of compressed portions which are portions of compressed profiles in a first tile of the Digital Elevation Model, the compressed portions stored in one of: a Memory Mapped File (MMF), Random Access Memory (RAM), and a file in a file system on a digital processing system, the plurality of compressed portions including the first compressed portion, the first index pointing to a storage location where the first compressed portion is stored;

decompressing the first compressed portion to retrieve first elevation data for at least one sample point in the Digital Elevation Model;

identifying the first tile, the first tile containing a first location and being one of a plurality of tiles in an area of the Digital Elevation Model;

identifying a first profile that is in the vicinity of the first location, the first compressed portion being a portion of the first profile; and

identifying the area, the area containing the first location and being one of a plurality of areas of the Digital Elevation Model.

20. A machine readable media containing executable computer program instructions which when executed by a digital processing system cause said system to perform a method to retrieve elevation data, the method comprising:

locating a first compressed portion of a Digital Elevation Model (DEM) using a first index, the Digital Elevation Model comprising a plurality of compressed portions which are portions of compressed profiles in a first tile of the Digital Elevation Model, the plurality of compressed portions stored in one of: a Memory Mapped File (MMF), Random Access Memory (RAM), and a file in a file system on a digital processing system, the plurality of compressed portions including the first compressed portion, the first index pointing to a storage location where the first compressed portion is stored;

decompressing the first compressed portion to retrieve first elevation data for at least one sample point in the Digital Elevation Model;

identifying the first tile, the first tile containing a first location and being one of a plurality of tiles in an area of the Digital Elevation Model;

identifying a first profile that is in the vicinity of the first location, the first compressed portion being a portion of the first profile; and

identifying the area, the area containing the first location and being one of a plurality of areas of the Digital Elevation Model.

21. A digital processing system to retrieve elevation data, the digital processing System comprising:

means for locating a first compressed portion of a Digital Elevation Model (DEM) using a first index, the Digital Elevation Model comprising a plurality of compressed portions which are portions of compressed profiles in a first tile of the Digital Elevation Model, the plurality of compressed portions stored in one of: a Memory Mapped File (MMF), adorn Access Memory (RAM), and a file in a file system on a digital processing system, the plurality of compressed portions including the first compressed portion, the first index pointing to a storage location where the first compressed portion is stored;

means for decompressing the first compressed portion to retrieve first elevation data for at least one sample point in the Digital Elevation Model;

means for identifying the first tile, the first tile containing a first location and being one of a plurality of tiles in an area of the Digital Elevation Model;

means for identifying a first profile that is in the vicinity of the first location, the first compressed portion being a portion of the first profile; and

means for identifying the area, the area containing the first location and being one of a plurality of areas of the Digital Elevation Model.