Routing graphs for buildings

• US 9,116,003 B2
• Filed: 09/03/2010
• Issued: 08/25/2015
• Est. Priority Date: 10/01/2009
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Khorashadi, Behrooz, Das, Saumitra Mohan, Gupta, Rajarshi
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): LIN, ABBY YEE
• Application Number:
  US12/875,756
• Publication Number:
  US 20110082638A1
• Time in Patent Office: 1,817 Days
• Field of Search: 701/400, 701408-410, 701/420, 701433-439, 701450-469, 701532-533, 701537-541
• US Class Current: 1/1
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G06F 30/13 Architectural design, e.g. computer-aided architectural design [CAAD] related to design of buildings, bridges, landscapes, production plants or roads
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

The subject matter disclosed herein relates to systems, methods, etc. for creating a routing graph based at least partly on building information. For certain example implementations, a method includes obtaining building information descriptive of at least a portion of a building structure. A grid of points may be superimposed onto the building information. At least one routing graph may be created based at least in part on the superimposed grid of points and the building information. Other example implementations are also described.

Claims

1. A method being executed by a special purpose computing device comprising:

receiving, by the special purpose computing device, building information descriptive of at least a portion of a building structure and of doors of the building structure;

superimposing, by the special purpose computing device, a grid of points onto said building information, the grid of points comprising a set of points located at regular intervals in a plane;

modeling the doors of the building structure in a closed state;

determining a plurality of autonomous areas based on the superimposed grid of points wherein each autonomous area comprises a set of adjacent grid points interconnected by traversable links that is separated from any other autonomous area by non-traversable links; and

interconnecting in the plane, by the special purpose computing device, at least a portion of a plurality of door node points with at least a portion of the plurality of autonomous areas to create at least one routing graph wherein the plurality of door node points correspond to the doors of the building structure and further wherein the at least one routing graph is a routing topology indicating a set of discrete traversable paths interconnecting the plurality of autonomous areas.

2. The method of claim 1, wherein said method further comprises:

interconnecting, by the special purpose computing device, at least a portion of adjacent points of said superimposed grid of points with traversable links.

3. The method of claim 2, wherein said traversable links comprise links that do not intersect said building structure of said building information.

4. The method of claim 3, wherein points of said superimposed grid of points comprise nodes of said at least one routing graph, and said traversable links comprise edges of said at least one routing graph.

5. The method of claim 1, wherein said method further comprises:

providing to a mobile device navigational information relating to said building structure using said at least one routing graph.

6. The method of claim 1 wherein an interval distance between adjacent points of the superimposed grid of points varies within the superimposed grid of points.

7. The method of claim 1 wherein the building information comprises a computer-aided design (CAD) format file converted to an open format file wherein the open format file is parsable using text parsing utilities.

8. The method of claim 1 further comprising:

determining the plurality of autonomous areas based on one or more walls of the building structure, wherein the building information includes wall information for the one or more walls and further wherein the one or more walls include exterior walls and interior walls; and

determining that a given autonomous area of the plurality of autonomous areas is one or more hallways based on the given autonomous area being connected to at least a threshold number of the doors of the building structure.

9. The method of claim 1 wherein the building information is organized into at least two layers wherein first information in a first layer is parsed to extract the building structure and wherein second information in a second layer is parsed to extract one or more annotations associated with the building structure.

10. The method of claim 1 wherein the building information includes one or more annotations and further comprising linking the one or more annotations to the at least one routing graph.

11. A special purpose computing device comprising:

at least one memory to store instructions; and

one or more processors to execute said instructions to;

receive building information descriptive of at least a portion of a building structure and of doors of the building structure,

superimpose a grid of points onto said building information, the grid of points comprising a set of points located at regular intervals in a plane;

model the doors of the building structure in a closed state;

determine a plurality of autonomous areas based on the superimposed grid of points wherein each autonomous area comprises a set of adjacent grid points interconnected by traversable links that is separated from any other autonomous area by non-traversable links; and

interconnect in the plane at least a portion of a plurality of door node points with at least a portion of the plurality of autonomous areas to create at least one routing graph wherein the plurality of door node points correspond to the doors of the building structure and further wherein the at least one routing graph is a routing topology indicating a set of discrete traversable paths interconnecting the plurality of autonomous areas.

12. The device of claim 11, wherein said one or more processors are further to execute said instructions to:

interconnect at least a portion of adjacent points of said superimposed grid of points with traversable links.

13. The device of claim 12, wherein said traversable links comprise links that do not intersect said building structure of said building information.

14. The device of claim 12, wherein points of said superimposed grid of points comprise nodes of said at least one routing graph, and said traversable links comprise edges of said at least one routing graph.

15. The device of claim 11, wherein said one or more processors are further to execute said instructions to:

provide to a mobile device navigational information relating to said building structure using said at least one routing graph.

16. An article comprising:

at least one non-transitory storage medium having stored thereon instructions executable by one or more processors to;

receive building information descriptive of at least a portion of a building structure and of doors of the building structure,

superimpose a grid of points onto said building structure information, the grid of points comprising a set of points located at regular intervals in a plane;

model the doors of the building structure in a closed state;

determine a plurality of autonomous areas based on the superimposed grid of points wherein each autonomous area comprises a set of adjacent grid points interconnected by traversable links that is separated from any other autonomous area by non-traversable links; and

interconnect in the plane at least a portion of a plurality of door node points with at least a portion of the plurality of autonomous areas to create at least one routing graph based at least in part on said superimposed grid of points wherein the plurality of door node points correspond to the doors of the building structure and further wherein the at least one routing graph is a routing topology indicating a set of discrete traversable paths interconnecting the plurality of autonomous areas.

17. The article of claim 16, wherein said at least one non-transitory storage medium has stored thereon further instructions executable by one or more processors to:

interconnect at least a portion of adjacent points of said superimposed grid of points with traversable links.

18. The article of claim 17, wherein said traversable links comprise links that do not intersect said building structure of said building information.

19. The article of claim 17, wherein points of said superimposed grid of points comprise nodes of said at least one routing graph, and said traversable links comprise edges of said at least one routing graph.

20. The article of claim 16, wherein said at least one non-transitory storage medium has stored thereon further instructions executable by the one or more processors to:

provide to a mobile device navigational information relating to said building structure using said at least one routing graph.

21. An apparatus comprising:

means for receiving building information descriptive of at least a portion of a building structure and of doors of the building structure,

means for superimposing a grid of points onto said building information, the grid of points comprising a set of points located at regular intervals in a plane;

means for modeling the doors of the building structure in a closed state;

means for determining a plurality of autonomous areas based on the superimposed grid of points wherein each autonomous area comprises a set of adjacent grid points interconnected by traversable links that is separated from any other autonomous area by non-traversable links; and

means for interconnecting in the plane at least a portion of a plurality of door node points with at least a portion of the plurality of autonomous areas to create at least one routing graph wherein the plurality of door node points correspond to the doors of the building structure and further wherein the at least one routing graph is a routing topology indicating a set of discrete traversable paths interconnecting the plurality of autonomous areas.

22. The apparatus of claim 21, further comprising:

means for interconnecting at least a portion of adjacent points of said superimposed grid of points with traversable links.

23. The apparatus of claim 22, wherein said traversable links comprise links that do not intersect said building structure of said building information.

24. The apparatus of claim 23, wherein points of said superimposed grid of points comprise nodes of said at least one routing graph, and said traversable links comprise edges of said at least one routing graph.

25. The apparatus of claim 21, further comprising:

means for providing to a mobile device navigational information relating to said building structure using said at least one routing graph.