Generalized, differentially encoded, indexed raster vector data and schema for maps on a personal digital assistant

• US 6,674,445 B1
• Filed: 07/31/2000
• Issued: 01/06/2004
• Est. Priority Date: 10/12/1999
• Status: Expired due to Term

• Current Assignee: TeleCommunication Systems Inc (Comtech Telecommunications Corporation)
• Original Assignee: Autodesk, Inc.
• Inventors: Chithambaram, Nemmara, Marantz, Howard
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/628,850
• Time in Patent Office: 1,254 Days
• Field of Search: 345/419, 345/420, 345/424, 345/619, 345/620
• US Class Current: 345/619
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06T 9/004 Predictors, e.g. intraframe, interframe coding
• CPC Class Codes: G09B 29/007 using computer methods

Abstract

A schema provides for the storage of geographic information on a personal digital assistant (PDA). Embodiments provide differential encoding and indexing of raster and vector based data. A schema provides for compact and performable storage of both data and metadata for raster, vector, and redlining information. A single database is utilized for mapset metadata and data. Timestamp/history information allows smart, incremental updates of the database. Indexing information allows compact and efficient storage and retrieval of objects and vector geometry. The schema allows a variable number of mapsets, maps, raster tiles, and geometry layers. Metadata for geometry types and redlining markup information are permitted. Geo-referencing information for raster and vector data allows the display of objects at the correct map location. Raster data is augmented with compact vector data. The vector data may be used for efficiently storing and retrieving the map data, allowing interactive selection, and the highlighting and querying of objects. Vectors are generalized by removing detail without losing shape information in a manner appropriate to PDA display resolution. Object location data is differentially encoded to provide precision using a fewer number of bytes (2 bytes per coordinate). The vector object includes spatial indexing information, to allow for spatial filtering of objects that fall within a specified view. Thus, the invention uses cartographic generalization, encoding, and indexing to provide for compact, and efficient spatial storage structures that deal with the PDA constraints of limited storage, processing power, memory and bandwidth.

Claims

1. A system for accessing object data relating to geographical information comprising:

(a) a server;

(b) a servlet executing on the server, the servlet configured to;

(i) obtain a map comprised of multiple raster tiles;

(ii) obtain vector object data for an object of the map;

(iii) generalize a shape of the object by filtering out some of the vector object data;

(iv) differentially encode a location of the object by encoding an offset for the location of the object with respect to an origin of the raster tile where the object is located;

(v) spatially index the vector object data by encoding the bounds of the object.

2. The system of claim 1 wherein the offset and bounds are encoded in an index.

3. The system of claim 2 wherein the raster tiles are stored in row major format followed by the index for each raster tile stored in an order corresponding to the storage of the raster tiles.

4. The system of claim 2 wherein the servlet is further configured to encode in the index a reference to a record containing the generalized vector object data.

5. The system of claim 1 wherein the servlet is further configured to transmit the generalized, spatially indexed, differentially encoded object data to a personal digital assistant.

6. The system of claim 1 wherein the storage of the generalized, spatially indexed, differentially encoded object data provides for determining the object identified by a point by:

evaluating bounds of one or more raster tiles to determine the raster tile containing the point; and

evaluating the bounds of objects within the raster tile containing the point to determine which object contains the point.

7. A system for accessing object data relating to geographic information comprising:

(a) a personal digital assistant;

(b) an application on the personal digital assistant, the application configured to;

(i) obtain a map comprised of;

(A) raster tile data;

(B) a generalized shape of one more objects located within the raster tiles;

(C) one or more offsets for locations of each objects with respect to an origin of the raster tile where each object is located; and

D) one or more bounds of each object; and

(ii) display the map on a screen of the personal digital assistant.

8. The system of claim 7 wherein the offset and bounds are encoded in an index.

9. The system of claim 8 wherein the raster tiles are stored in row major format followed by the index for each raster tile stored in an order corresponding to the storage of the raster tiles.

10. The system of claim 8 wherein the map further comprises a reference to a record containing generalized vector object data for the object.

11. The system of claim 7 wherein the application on the personal digital assistant is further configured to determine the object identified by a point selected by:

evaluating bounds of the one or more raster tiles to determine the raster tile containing the point; and

evaluating the bounds of objects within the raster tile containing the point to determine which object contains the point.

12. A method of storing object data relating to geographic information comprising:

(a) obtaining a map comprised of multiple raster tiles;

(b) obtaining vector object data for an object of the map;

(c) encoding the multiple raster tiles;

(d) generalizing a shape of the object by filtering out some of the vector object data;

(e) encoding the generalized shape of the object;

(f) differentially encoding a location of the object by encoding an offset for the location of the object with respect to an origin of the raster tile where the object is located; and

(g) spatially indexing the vector object data by encoding the bounds of the object.

13. The method of claim 12 wherein the offset and bounds are encoded in an index.

14. The method of claim 13 wherein the raster tiles are stored in row major format followed by the index for each raster tile stored in an order corresponding to the storage of the raster tiles.

15. The method of claim 13 further comprising encoding in the index a reference to a record containing the generalized vector object data.

16. The method of claim 12 further comprising transmitting the generalized, spatially indexed, differentially encoded object data to a personal digital assistant.

17. The method of claim 12 further comprising determining the object identified by a point by:

evaluating bounds of one or more raster tiles to determine the raster tile containing the point; and

evaluating the bounds of objects within the raster tile containing the point to determine which object contains the point.

18. A method of displaying object data relating to geographic information on a personal digital assistant comprising:

(a) obtaining a map comprised of;

(i) multiple raster tiles;

(ii) a generalized shape of an object;

(iii) an offset for the location of the object with respect to an origin of the raster tile where the object is located; and

(iv) the bounds of the object;

(b) displaying the map on a screen of the personal digital assistant.

19. The method of claim 18 wherein the offset and bounds are encoded in an index.

20. The method of claim 19 wherein the raster tiles are stored in row major format followed by the index for each raster tile stored in an order corresponding to the storage of the raster tiles.

21. The method of claim 18 wherein the map further comprises a reference to a record containing generalized vector object data for the object.

22. The method of claim 18 further comprising determining the object identified by a point by:

evaluating bounds of one or more raster tiles to determine the raster tile containing the point; and

evaluating the bounds of objects within the raster tile containing the point to determine which object contains the point.

23. An article of manufacture comprising a program storage medium readable by a computer hardware device and embodying one or more instructions executable by the computer hardware device to perform a method for storing object data relating to geographic information, the method comprising:

(a) obtaining a map comprised of multiple raster tiles;

(b) obtaining vector object data for an object of the map;

(c) encoding the multiple raster tiles;

(d) generalizing a shape of the object by filtering out some of the vector object data;

(e) encoding the generalized shape of the object;

(f) differentially encoding a location of the object by encoding an offset for the location of the object with respect to an origin of the raster tile where the object is located; and

(g) spatially indexing the vector object data by encoding the bounds of the object.

24. The article of manufacture of claim 23 wherein the offset and bounds are encoded in an index.

25. The article of manufacture of claim 24 wherein the raster tiles are stored in row major format followed by the index for each raster tile stored in an order corresponding to the storage of the raster tiles.

26. The article of manufacture of claim 24 wherein the method further comprises encoding in the index a reference to a record containing the generalized vector object data.

27. The article of manufacture of claim 23, the method further comprising transmitting the generalized, spatially indexed, differentially encoded object data to a personal digital assistant.

28. The article of manufacture of claim 23, the method further comprising determining the object identified by a point by:

evaluating bounds of one or more raster tiles to determine the raster tile containing the point; and

evaluating the bounds of objects within the raster tile containing the point to determine which object contains the point.

29. An article of manufacture comprising a program storage medium readable by a computer hardware device and embodying one or more instructions executable by the computer hardware device to perform a method for displaying object data relating to geographic information, the method comprising:

(a) obtaining a map comprised of;

(i) multiple raster tiles;

(ii) a generalized shape of an object;

(iii) an offset for the location of the object with respect to an origin of the raster tile where the object is located; and

(iv) the bounds of the object;

(b) displaying the map on a screen of the article of manufacture.

30. The article of manufacture of claim 29 wherein the offset and bounds are encoded in an index.

31. The article of manufacture of claim 30 wherein the raster tiles are stored in row major format followed by the index for each raster tile stored in an order corresponding to the storage of the raster tiles.

32. The article of manufacture of claim 29 wherein the map further comprises a reference to a record containing generalized vector object data for the object.

33. The article of manufacture of claim 29, the method further comprising determining the object identified by a point by:

evaluating bounds of one or more raster tiles to determine the raster tile containing the point; and

evaluating the bounds of objects within the raster tile containing the point to determine which object contains the point.