DIGITAL MAP FOR NAVIGATION

Abstract

A digital map representing a physical location as a hierarchical structure of cells. Each cell has attributes including but not limited to permeability in each direction of a three-dimensional coordinate system and associated with one or more faces or edges of a boundary. The permeability pertains separately to transmissions of radio frequency signals and to physical travel of objects and persons.

Claims

1-13. (canceled)

14. A digital map numerically representing a physical space for a purpose of computational navigation, comprising data structures corresponding to a plurality of cells, each cell corresponding to a particular location within the physical space, said each cell comprising a boundary, the boundary being defined by a data set of numerical values within a corresponding data structure, the data set further comprising at least a numerical value for at least a permeability attribute recorded in said corresponding data structure, the permeability attribute numerically representing an ability of the boundary to be traversed.

15. The digital map of claim 14, wherein the boundary of said each cell is a two-dimensional boundary.

16. The digital map of claim 15, wherein the two-dimensional boundary comprises a plurality of edges, each edge having a data set of numerical values associated with said each edge, the data set of said each edge comprising at least a numerical permeability attribute, the data set of said each edge being recorded in the corresponding data structure.

17. The digital map of claim 14, wherein the boundary of said each cell is a three-dimensional boundary.

18. The digital map of claim 17, wherein the three-dimensional boundary comprises a plurality of faces, each face comprising a data set of numerical values associated with said each face, the data set of said each face comprising at least a numerical permeability attribute, the data set of said each face being recorded in the corresponding data structure.

19. The digital map of claim 14, wherein the permeability attribute pertains to a physical movement of objects.

20. The digital map of claim 19, wherein the permeability attribute pertains to a particular type of objects.

21. The digital map of claim 19, wherein the permeability attribute further comprises a reference to speed.

22. The digital map of claim 19, wherein the permeability attribute further comprises a reference to direction.

23. The digital map of claim 14, wherein the permeability attribute pertains to a transmission of radio signals.

24. The digital map of claim 23, wherein the permeability attribute pertains to the radio signals of a particular frequency.

25. The digital map of claim 14, wherein the data structures are further comprised into group data structures.

26. A memory device storing the digital map of claim 14.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0033] The invention will be better understood when reading the following description and examining the annexed Figures. These Figures are given only as an illustration and by no means as a restriction of the invention.

[0034] FIG. 1 is an illustration of a three-dimensional Cell 60 aligned with a 3-dimensional coordinate system having origin 100 and Boundary Faces 110, 120, 130, 140, 150 and 160;

[0035] FIG. 2 illustrates a single story of a building represented as a Group 50 of Cells 60, having Group Origin 10, with one cell having an entryway 510 and another cell having a stairway floor 500;

[0036] FIG. 3 is an elevation view of two Cells 60, each Cell having a sloping floor 500 with different Boundary Face floor heights 530 and 540;

[0037] FIG. 4 illustrates a Cell 60 having a stairway floor 500 with Boundary Face floor heights 530 and 540, permeable top Boundary Face 120 and left Boundary Face 130, and impermeable right Boundary Face 140 and bottom Boundary Face 110;

[0038] FIG. 5 shows a plan view of a Physical Location 20 having two distinct Groups 50 of Cells 60;

[0039] FIG. 6 is a plan view illustration of an embodiment representing a curved bi-directional roadway as a plurality of Groups 50 of Cells 60, each Group having a distinct coordinate system with origin 10 and cells of varied size to best represent the physical roadway;

[0040] FIG. 7 is a block diagram of a Map Data Structure 25 comprising illustrative Map Data and a plurality of Group Data Structures 55;

[0041] FIG. 8 is a block diagram of a Group Data Structure 55 comprising illustrative Group Data and a plurality of Cell Data Structures 65; and

[0042] FIG. 9 is a block diagram of an illustrative Cell Data Structure 65.

[0043] Identical, similar, or analogous elements share the same reference number throughout the Figures.

Detailed Description of the Representative Embodiments of the Invention

[0044] FIG. 1 shows a first representative embodiment of a digital map of a single story of a multi-level building. FIG. 2 illustrates diagrammatically how the map of the present invention represents a physical space 20 as a Group 50 of Cells 60, having Group Origin 10, with one cell having an entryway 510 which indicates a transition path to the exterior, and another cell having a stairway floor 500, which indicates a transition path to an upper level. Each transition path is represented as a permeability attribute of the corresponding Cell Face in the Cell Boundary.

[0045] The cell representing a stairway is further illustrated in FIG. 4. Shown is a Cell 60 having a stairway floor 500 with Boundary Face floor heights 530 and 540, permeable top Boundary Face 120 and left Boundary Face 130, and impermeable right Boundary Face 140 and bottom Boundary Face 110.

[0046] FIG. 8 is a diagrammatic representation of the Group data structure of the digital map of the embodiment. FIG. 9 is an illustration of a data structure corresponding to each Cell in the Group. It shall be obvious to one skilled in the art how to combine the representations of multiple levels, each level having its corresponding Group data structure, into an overall map data structure illustrated in FIG. 7.

[0047] FIG. 5 shows a plan view of a Physical Location 20 having two distinct Groups 50 of Cells 60, which is representative of a campus having a plurality of buildings or outdoor areas through which objects and signals may transit.

[0048] In some embodiments, electronic devices may be located in various locations corresponding to specific cells on the map. It may be desirable to transmit electronic messages between two such devices which are not in direct transmission range of each other. By evaluating signal Permeability values for the cell boundaries which lie between the source and the destination, and knowing the locations of candidate relay devices, an optimized relay chain of intermediary devices can be computed to ensure most efficient transmission of the message.

[0049] A representative embodiment having a sloping floor is illustrated in FIG. 3. Shown is an elevation view of two Cells 60, each Cell having a sloping floor 500 with different Boundary Face floor heights 530 and 540. The Cell data structure illustrated in FIG. 9 incorporates Z axis attributes for floor height as well as interior height associated with each face. It shall be obvious to one skilled in the art how the illustrated Cell data structure may be extended to include individual floor Z attributes associated specifically with each face.

[0050] An embodiment representing a curved bi-directional roadway as a plurality of Groups 50 of Cells 60, each Group having a distinct coordinate system with origin 10 and cells of varied size to best represent the physical roadway. The illustration shows how orthogonal Cells may be used to represent non-orthogonal spaces within the context of the present invention. Non-orthogonal cell representations conforming to physical space features are also possible, at the cost of additional data necessary to represent the boundary. Such representations are well known in the art.

[0051] The use of directional permeability attribute is also illustrated in FIG. 6, with direction corresponding to the designated direction of travel for each lane of the roadway. A speed limit attribute may also be incorporated.

[0052] A representative use of numerical Permeability value may include determining the trustworthiness of positional information such as GPS signal. If a vehicle was known to be located in a location associated with a first cell on the map at a known point in time and receives GPS information that it is now located in a location associated with a second cell. The numerical permeability of each cell boundary between last known location and current reported location can be first evaluated to determine whether a valid path between the two locations exists. If no path exists, the GPS reported location can be assumed to be erroneous.

[0053] If a valid path exists, the numerical values for speed across the cell boundaries can then be evaluated, and it can be determined whether the vehicle could have reasonably traveled between the two locations in the time available. If the answer is no, the reported GPS location would be considered not trustworthy.

[0054] Finally, if the GPS signal permeability of the top face of the cell where the vehicle is reported to be located is low, representing an overhead signal obstruction, the quality of the signal can be assumed to be low and the reported location less trustworthy.

[0055] The digital Map and the corresponding data structure can be stored in a memory device 200 (cf. FIG. 9). The memory device 200 can be, for example but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus or device. More specific examples (a non-exhaustive list) of the memory device 200 include the following: a portable computer diskette; a random access memory; a read-only memory; an erasable programmable read-only memory (or Flash memory); and a portable compact disc read-only memory. The memory device 200 is a computer-usable or computer-readable medium.

[0056] More specifically, the invention relates to a digital Map representing a physical space 20, said map comprising Data Structures 65 corresponding to a plurality of Cells 60, each said Cell 60 corresponding to a particular location within said physical space 20, each said Cell 60 further having a Boundary, said Boundary further having at least a Permeability attribute recorded in a Data Structure.

[0057] According to a particular embodiment, said Boundary of each of said Cells 60 is two dimensional.

[0058] According to a particular embodiment, said two dimensional Boundary comprises a plurality of Edges, each said Edge having at least a Permeability attribute recorded in a Data Structure.

[0059] According to a particular embodiment, said Boundary of each of said Cells 60 is three dimensional.

[0060] According to a particular embodiment, said Boundary comprises a plurality of Faces (110, 120, 130, 140, 150, 160), each said Face (110, 120, 130, 140, 150, 160) having at least a Permeability attribute recorded in a Data Structure.

[0061] According to a particular embodiment, said Permeability attribute pertains to physical movement of objects.

[0062] According to a particular embodiment, said Permeability attribute pertains to a particular type of objects.

[0063] According to a particular embodiment, said Permeability attribute further comprises a reference to speed.

[0064] According to a particular embodiment, said Permeability attribute further comprises a reference to direction.

[0065] According to a particular embodiment, said Permeability attribute pertains to transmission of radio signals.

[0066] According to a particular embodiment, said Permeability attribute pertains to radio signals of a particular frequency.

[0067] According to a particular embodiment, Cell Data Structures 65 are further included into Group Data Structures.

[0068] The invention also relates to a memory device storing a digital Map according to the invention.

[0069] The particular embodiments disclosed herein are illustrative and not limiting; other embodiments shall be readily apparent to those skilled in the art based upon the disclosures made herein, without departing from the scope of the present invention.