ROUTING GRAPHS FOR BUILDINGS USING SCHEMATICS

• US 20110080848A1
• Filed: 09/03/2010
• Published: 04/07/2011
• Est. Priority Date: 10/01/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Das, Saumitra Mohan, Khorashadi, Behrooz, Gupta, Rajarshi
• Granted Patent: US 9,140,559 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• 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, which may include relatively low-detail schematics. For certain example implementations, a method may include obtaining building information descriptive of at least a portion of a building structure and superimposing a grid of points onto the building information. The building information may be analyzed using the superimposed grid of points by projecting multiple rays from multiple points of the superimposed grid of points. At least one routing graph may be created responsive to the analyzing and based at least in part on the superimposed grid of points and the building information. Other example implementations are described herein.

Claims

1. A method comprising:

obtaining electrical signals representing building information descriptive of at least a portion of a building structure;

superimposing a grid of points onto said building information;

analyzing said building information using said superimposed grid of points by projecting multiple rays from multiple points of said superimposed grid of points; and

generating electrical signals representing at least one routing graph responsive to said analyzing and based at least in part on said superimposed grid of points and said building information.

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

determining whether multiple points of said superimposed grid of points comprise exterior points or interior points with respect to said building structure.

3. The method of claim 2, wherein said determining comprises:

projecting multiple rays from a selected point of said multiple points;

detecting a number of said multiple projected rays that impact a building feature of said building structure; and

identifying said selected point as comprising an interior point or an exterior point of said building structure based at least partly on said number of said multiple projected rays that impact a building feature.

4. The method of claim 3, wherein said identifying comprises:

determining whether said number of said multiple projected rays that impact a building feature meets at least one predetermined threshold; and

if said number of said multiple projected rays that impact a building feature is determined to meet said predetermined threshold, identifying said selected point as comprising an interior point.

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

interconnecting at least a portion of adjacent points of said superimposed grid of points with traversable links to form multiple disconnected graphs; and

determining multiple autonomous areas based at least partly on said multiple disconnected graphs.

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

ascertaining at least one autonomous area of said multiple autonomous areas that is external to said building structure based at least partly on one or more of said exterior points.

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

discovering one or more hallways of said building structure based at least in part on multiple spans corresponding to multiple autonomous areas of said building structure.

8. The method of claim 7, wherein said discovering comprises:

calculating multiple spans for said multiple autonomous areas of said building structure; and

identifying at least one autonomous area of said multiple autonomous areas as comprising at least one hallway based on said multiple calculated spans and at least one predetermined threshold.

9. The method of claim 8, wherein said identifying comprises:

comparing a particular span of said multiple calculated spans to said at least one predetermined threshold that is dependent on said multiple calculated spans;

determining whether said particular span meets said at least one predetermined threshold; and

if said particular span is determined to meet said at least one predetermined threshold, identifying a particular autonomous area corresponding to said particular span as comprising at least one hallway of said building structure.

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

overlaying building annotation information onto multiple autonomous areas definable on said superimposed grid of points; and

determining which one or more autonomous areas of said multiple autonomous areas are feasible and if any autonomous areas of said multiple autonomous areas are infeasible based at least in part on said overlaid building annotation information.

11. The method of claim 1, wherein said analyzing comprises:

determining one or more entry and/or exit points for multiple autonomous areas based at least in part on said multiple projected rays and at least one hallway of said building structure.

12. The method of claim 11, wherein said determining comprises:

projecting multiple rays from a point of said superimposed grid of points that corresponds to a point of interest associated with a particular autonomous area of said multiple autonomous areas;

detecting one or more impacts said multiple projected rays make with at least one building feature with regard to reaching said at least one hallway of said building structure; and

identifying said one or more entry and/or exit points for said particular autonomous area based at least partly on said one or more impacts with said at least one building feature.

13. The method of claim 11, wherein said method further comprises:

computing one or more paths to navigate to a point of interest of said building structure based at least in part on said one or more entry and/or exit points that are determined for an associated autonomous area.

14. The method of claim 1, wherein said analyzing comprises:

determining one or more entry and/or exit points for multiple autonomous areas based at least in part on determining if a particular autonomous area on an opposite side of a bounding wall, which is between a given feasible autonomous area of the multiple autonomous areas and the particular autonomous area, comprises a hallway.

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

initiating transmission to a mobile device navigational information relating to said building structure and derived at least partially from said at least one routing graph.

16. The method of claim 1, wherein said analyzing comprises:

detecting whether ray projections of said multiple projected rays impact one or more building features of said building structure.

17. The method of claim 16, wherein said analyzing further comprises:

for multiple points of said superimposed grid of points, determining whether said multiple points comprise exterior points or interior points with respect to said building structure based at least partly on said detecting; and

for multiple autonomous areas of said building structure, determining at least one entry and/or exit point for said multiple autonomous areas based at least partly on said detecting.

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

executing instructions, by a special purpose computing device, to direct the special purpose computing device to implement said method.

19. A special purpose computing device comprising:

at least one memory to store instructions; and

one or more processors to execute said instructions to;

obtain building information descriptive of at least a portion of a building structure;

superimpose a grid of points onto said building information;

analyze said building information using said superimposed grid of points by projecting multiple rays from multiple points of said superimposed grid of points; and

create at least one routing graph responsive to said analyzing and based at least in part on said superimposed grid of points and said building information.

20. The device of claim 19, wherein to analyze said building information said one or more processors are further to execute said instructions using said superimposed grid of points by:

determine whether multiple points of said superimposed grid of points comprise exterior points or interior points with respect to said building structure.

21. The device of claim 20, wherein to determine whether multiple points of said superimposed grid of points comprise exterior points or interior points said one or more processors are further to execute said instructions by:

projecting multiple rays from a selected point of said multiple points;

detecting a number of said multiple projected rays that impact a building feature of said building structure; and

identifying said selected point as comprising an interior point or an exterior point of said building structure based at least partly on said number of said multiple projected rays that impact a building feature.

22. The device of claim 21, wherein to identify said selected point said one or more processors are further to execute said instructions by:

determining whether said number of said multiple projected rays that impact a building feature meets at least one predetermined threshold; and

if said number of said multiple projected rays that impact a building feature is determined to meet said predetermined threshold, identifying said selected point as comprising an interior point.

23. The device of claim 20, 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 to form multiple disconnected graphs; and

determine multiple autonomous areas based at least partly on said multiple disconnected graphs

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

ascertain at least one autonomous area of said multiple autonomous areas that is external to said building structure based at least partly on one or more of said exterior points.

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

discover one or more hallways of said building structure based at least in part on multiple spans corresponding to multiple autonomous areas of said building structure.

26. The device of claim 25, wherein to discover one or more hallways said one or more processors are further to execute said instructions by:

calculating multiple spans for said multiple autonomous areas of said building structure; and

identifying at least one autonomous area of said multiple autonomous areas as comprising at least one hallway based on said multiple calculated spans and at least one predetermined threshold.

27. The device of claim 26, wherein to identify at least one autonomous area said one or more processors are further to execute said instructions by:

comparing a particular span of said multiple calculated spans to said at least one predetermined threshold that is dependent on said multiple calculated spans;

determining whether said particular span meets said at least one predetermined threshold; and

if said particular span is determined to meet said at least one predetermined threshold, identifying a particular autonomous area corresponding to said particular span as comprising at least one hallway of said building structure.

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

overlay building annotation information onto multiple autonomous areas definable on said superimposed grid of points; and

determine which one or more autonomous areas of said multiple autonomous areas are feasible and if any autonomous areas of said multiple autonomous areas are infeasible based at least in part on said overlaid building annotation information.

29. The device of claim 19, wherein to analyze said building information said one or more processors are further to execute said instructions using said superimposed grid of points by:

determining one or more entry and/or exit points for multiple autonomous areas based at least in part on said multiple projected rays and at least one hallway of said building structure.

30. The device of claim 29, wherein to determine one or more entry and/or exit points said one or more processors are further to execute said instructions by:

projecting multiple rays from a point of said superimposed grid of points that corresponds to a point of interest associated with a particular autonomous area of said multiple autonomous areas;

detecting one or more impacts said multiple projected rays make with at least one building feature with regard to reaching said at least one hallway of said building structure; and

identifying said one or more entry and/or exit points for said particular autonomous area based at least partly on said one or more impacts with said at least one building feature.

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

compute one or more paths to navigate to a point of interest of said building structure based at least in part on said one or more entry and/or exit points that are determined for an associated autonomous area.

32. The device of claim 19, wherein to analyze said building information said one or more processors are further to execute said instructions using said superimposed grid of points by:

determining one or more entry and/or exit points for multiple autonomous areas based at least in part on determining if a particular autonomous area on an opposite side of a bounding wall, which is between a given feasible autonomous area of the multiple autonomous areas and the particular autonomous area, comprises a hallway.

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

initiate transmission to a mobile device navigational information relating to said building structure and derived at least partially from said at least one routing graph.

34. The device of claim 19, wherein to analyze said building information said one or more processors are further to execute said instructions using said superimposed grid of points by:

detecting whether ray projections of said multiple projected rays impact one or more building features of said building structure.

35. The device of claim 34, wherein to analyze said building information said one or more processors are further to execute said instructions using said superimposed grid of points by:

for multiple points of said superimposed grid of points, determining whether said multiple points comprise exterior points or interior points with respect to said building structure based at least partly on said detecting; and

for multiple autonomous areas of said building structure, determining at least one entry and/or exit point for said multiple autonomous areas based at least partly on said detecting.

36. An article comprising:

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

obtain building information descriptive of at least a portion of a building structure;

superimpose a grid of points onto said building information;

analyze said building information using said superimposed grid of points by projecting multiple rays from multiple points of said superimposed grid of points; and

create at least one routing graph responsive to said analyzing and based at least in part on said superimposed grid of points and said building information.

37. The article of claim 36, wherein to analyze said building information said at least one storage medium has stored thereon further instructions executable by one or more processors to:

determine whether multiple points of said superimposed grid of points comprise exterior points or interior points with respect to said building structure.

38. The article of claim 37, wherein to determine whether multiple points of said superimposed grid of points comprise exterior points or interior points said at least one storage medium has stored thereon further instructions executable by one or more processors to:

project multiple rays from a selected point of said multiple points;

detect a number of said multiple projected rays that impact a building feature of said building structure; and

identify said selected point as comprising an interior point or an exterior point of said building structure based at least partly on said number of said multiple projected rays that impact a building feature.

39. The article of claim 38, wherein to identify said selected point said at least one storage medium has stored thereon further instructions executable by one or more processors to:

determine whether said number of said multiple projected rays that impact a building feature meets at least one predetermined threshold; and

if said number of said multiple projected rays that impact a building feature is determined to meet said predetermined threshold, identify said selected point as comprising an interior point.

40. The article of claim 37, wherein said at least one 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 to form multiple disconnected graphs;

determine multiple autonomous areas based at least partly on said multiple disconnected graphs.

41. The article of claim 40, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

ascertain at least one autonomous area of said multiple autonomous areas that is external to said building structure based at least partly on one or more of said exterior points.

42. The article of claim 36, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

discover one or more hallways of said building structure based at least in part on multiple spans corresponding to multiple autonomous areas of said building structure.

43. The article of claim 42, wherein to discover one or more hallways said at least one storage medium has stored thereon further instructions executable by one or more processors to:

calculate multiple spans for said multiple autonomous areas of said building structure; and

identify at least one autonomous area of said multiple autonomous areas as comprising at least one hallway based on said multiple calculated spans and at least one predetermined threshold.

44. The article of claim 43, wherein to identify at least one autonomous area said at least one storage medium has stored thereon further instructions executable by one or more processors to:

compare a particular span of said multiple calculated spans to said at least one predetermined threshold that is dependent on said multiple calculated spans;

determine whether said particular span meets said at least one predetermined threshold; and

if said particular span is determined to meet said at least one predetermined threshold, identify a particular autonomous area corresponding to said particular span as comprising at least one hallway of said building structure.

45. The article of claim 36, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

overlay building annotation information onto multiple autonomous areas definable on said superimposed grid of points; and

determine which one or more autonomous areas of said multiple autonomous areas are feasible and if any autonomous areas of said multiple autonomous areas are infeasible based at least in part on said overlaid building annotation information.

46. The article of claim 36, wherein to analyze said building information said at least one storage medium has stored thereon further instructions executable by one or more processors to:

determine one or more entry and/or exit points for multiple autonomous areas based at least in part on said multiple projected rays and at least one hallway of said building structure.

47. The article of claim 46, wherein to determine one or more entry and/or exit points said at least one storage medium has stored thereon further instructions executable by one or more processors to:

project multiple rays from a point of said superimposed grid of points that corresponds to a point of interest associated with a particular autonomous area of said multiple autonomous areas;

detect one or more impacts said multiple projected rays make with at least one building feature with regard to reaching said at least one hallway of said building structure; and

identify said one or more entry and/or exit points for said particular autonomous area based at least partly on said one or more impacts with said at least one building feature.

48. The article of claim 46, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

compute one or more paths to navigate to a point of interest of said building structure based at least in part on said one or more entry and/or exit points that are determined for an associated autonomous area.

49. The article of claim 36, wherein to analyze said building information said at least one storage medium has stored thereon further instructions executable by one or more processors to:

determine one or more entry and/or exit points for multiple autonomous areas based at least in part on determining if a particular autonomous area on an opposite side of a bounding wall, which is between a given feasible autonomous area of the multiple autonomous areas and the particular autonomous area, comprises a hallway.

50. The article of claim 36, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

initiate transmission to a mobile device navigational information relating to said building structure and derived at least partially from said at least one routing graph.

51. The article of claim 36, wherein to analyze said building information said at least one storage medium has stored thereon further instructions executable by one or more processors to:

detect whether ray projections of said multiple projected rays impact one or more building features of said building structure.

52. The article of claim 51, wherein to analyze said building information said at least one storage medium has stored thereon further instructions executable by one or more processors to:

for multiple points of said superimposed grid of points, determine whether said multiple points comprise exterior points or interior points with respect to said building structure based at least partly on said detecting; and

for multiple autonomous areas of said building structure, determine at least one entry and/or exit point for said multiple autonomous areas based at least partly on said detecting.

53. An apparatus comprising:

means for obtaining building information descriptive of at least a portion of a building structure;

means for superimposing a grid of points onto said building information;

means for analyzing said building information using said superimposed grid of points by projecting multiple rays from multiple points of said superimposed grid of points; and

means for creating at least one routing graph responsive to said analyzing and based at least in part on said superimposed grid of points and said building information.

54. The apparatus of claim 53, wherein said means for analyzing comprises:

means for determining whether multiple points of said superimposed grid of points comprise exterior points or interior points with respect to said building structure.

55. The apparatus of claim 54, wherein said means for determining comprises:

means for projecting multiple rays from a selected point of said multiple points;

means for detecting a number of said multiple projected rays that impact a building feature of said building structure; and

means for identifying said selected point as comprising an interior point or an exterior point of said building structure based at least partly on said number of said multiple projected rays that impact a building feature.

56. The apparatus of claim 55, wherein said means for identifying comprises:

means for determining whether said number of said multiple projected rays that impact a building feature meets at least one predetermined threshold; and

means for identifying said selected point as comprising an interior point if said number of said multiple projected rays that impact a building feature is determined to meet said predetermined threshold.

57. The apparatus of claim 54, further comprising:

means for interconnecting at least a portion of adjacent points of said superimposed grid of points with traversable links to form multiple disconnected graphs;

means for determining multiple autonomous areas based at least partly on said multiple disconnected graphs.

58. The apparatus of claim 57, further comprising:

means for ascertaining at least one autonomous area of said multiple autonomous areas that is external to said building structure based at least partly on one or more of said exterior points.

59. The apparatus of claim 53, further comprising:

means for discovering one or more hallways of said building structure based at least in part on multiple spans corresponding to multiple autonomous areas of said building structure.

60. The apparatus of claim 59, wherein said means for discovering comprises:

means for calculating multiple spans for said multiple autonomous areas of said building structure; and

means for identifying at least one autonomous area of said multiple autonomous areas as comprising at least one hallway based on said multiple calculated spans and at least one predetermined threshold.

61. The apparatus of claim 60, wherein said means for identifying comprises:

means for comparing a particular span of said multiple calculated spans to said at least one predetermined threshold that is dependent on said multiple calculated spans;

means for determining whether said particular span meets said at least one predetermined threshold; and

means for identifying a particular autonomous area corresponding to said particular span as comprising at least one hallway of said building structure if said particular span is determined to meet said at least one predetermined threshold.

62. The apparatus of claim 53, further comprising:

means for overlaying building annotation information onto multiple autonomous areas definable on said superimposed grid of points; and

means for determining which one or more autonomous areas of said multiple autonomous areas are feasible and if any autonomous areas of said multiple autonomous areas are infeasible based at least in part on said overlaid building annotation information.

63. The apparatus of claim 53, wherein said means for analyzing comprises:

means for determining one or more entry and/or exit points for multiple autonomous areas based at least in part on said multiple projected rays and at least one hallway of said building structure.

64. The apparatus of claim 63, wherein said means for determining comprises:

means for projecting multiple rays from a point of said superimposed grid of points that corresponds to a point of interest associated with a particular autonomous area of said multiple autonomous areas;

means for detecting one or more impacts said multiple projected rays make with at least one building feature with regard to reaching said at least one hallway of said building structure; and

means for identifying said one or more entry and/or exit points for said particular autonomous area based at least partly on said one or more impacts with said at least one building feature.

65. The apparatus of claim 63, further comprising:

means for computing one or more paths to navigate to a point of interest of said building structure based at least in part on said one or more entry and/or exit points that are determined for an associated autonomous area.

66. The apparatus of claim 53, wherein said means for analyzing comprises:

means for determining one or more entry and/or exit points for multiple autonomous areas based at least in part on determining if a particular autonomous area on an opposite side of a bounding wall, which is between a given feasible autonomous area of the multiple autonomous areas and the particular autonomous area, comprises a hallway.

67. The apparatus of claim 53, further comprising:

means for initiating transmission to a mobile device navigational information relating to said building structure and derived at least partially from said at least one routing graph.

68. The apparatus of claim 53, wherein said means for analyzing comprises:

means for detecting whether ray projections of said multiple projected rays impact one or more building features of said building structure.

69. The apparatus of claim 68, wherein said means for analyzing further comprises:

means for determining whether said multiple points comprise exterior points or interior points with respect to said building structure based at least partly on said means for detecting, said means for determining operating with multiple points of said superimposed grid of points; and

means for determining at least one entry and/or exit point for said multiple autonomous areas based at least partly on said means for detecting, said means for determining operating on multiple autonomous areas of said building structure.