Routing graphs for buildings using schematics

• US 9,140,559 B2
• Filed: 09/03/2010
• Issued: 09/22/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,724
• Publication Number:
  US 20110080848A1
• Time in Patent Office: 1,845 Days
• Field of Search: 701400-527, 701532-541, 701300-302, 370254-256, 340/539.2, 340/990, 3409951-99528, 345/629
• 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, 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, by one or more processors, electrical signals representing a description of at least a portion of a building structure;

superimposing, by said one or more processors, a grid of points onto said description said of at least said portion of said building structure;

analyzing, by said one or more processors, said description of said at least said portion of said building structure using said superimposed grid of points by projecting multiple rays from multiple points of said superimposed grid of points;

interconnecting, by said one or more processors, one or more autonomous areas based at least partially on a number of impacts of said projecting multiple rays with a closed polygon; and

generating, by said one or more processors, electrical signals representing at least one routing graph responsive to said analyzing, said interconnecting, and based at least in part on said superimposed grid of points and said description of said at least said portion of said building structure.

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

determining, by said one or more processors, whether multiple points of said superimposed grid of points comprise exterior points or interior points with respect to said building structure, said determining of said interior points based at least partially on a first threshold number of impacts of said projecting multiple rays, said determining of said exterior points based at least partially on a second threshold number of impacts of said projecting multiple rays.

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 the building feature.

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

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

if said number of said multiple projected rays that impact the building feature is determined to meet said first threshold number, 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, by said one or more processors, one or more entry and/or exit points for multiple autonomous areas comprising one or more rooms or hallways 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, by said one or more processors, 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, by said one or more processors, 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, by said one or more processors, 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, by said one or more processors, 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, by said one or more processors, one or more entry and/or exit points for multiple autonomous areas comprising one or more rooms or hallways 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 comprising one or more rooms or hallways of said multiple autonomous areas and said particular autonomous area, comprises a hallway.

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

initiating, by said one or more processors, transmission to a mobile device directions, a full routing graph, a partial routing graph, or a combination thereof 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, by said one or more processors, whether any rays of said multiple rays projected 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, by said one or more processors, 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 comprising one or more rooms or hallways of said building structure, determining, by said one or more processors, 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 said 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 electrical signals representing a description of at least a portion of a building structure;

superimpose a grid of points onto said description of said at least said portion of said building structure;

analyze said description of said at least said portion of said building structure using said superimposed grid of points by projecting multiple rays from multiple points of said superimposed grid of points;

interconnecting one or more autonomous areas interior to said building structure based at least partially on a number of impacts of said projecting multiple rays with a closed polygon; and

create at least one routing graph responsive to said analyzing, said interconnecting, and based at least in part on said superimposed grid of points and said description of said at least said portion of said building structure.

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

determining whether multiple points of said superimposed grid of points comprise exterior points or interior points with respect to said building structure, said determining of said interior points based at least partially on a first threshold number of impacts of said projecting multiple rays, said determining of said exterior points based at least partially on a second threshold number of impacts of said projecting multiple rays.

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 the 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 the building feature meets at least one predetermined threshold; and

if said number of said multiple projected rays that impact the building feature is determined to meet said first threshold number, 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 description of said at least said portion of said building structure 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 comprising one or more rooms or hallways 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 description of said at least said portion of said building structure 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 comprising one or more rooms or hallways based at least in part on determining if a particular autonomous area of said multiple autonomous areas on an opposite side of a bounding wall, which is between a given feasible autonomous area comprising one or more rooms or hallways of said multiple autonomous areas and said 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 directions, a full routing graph, a partial routing graph, or a combination thereof 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 description of said at least said portion of said building structure said one or more processors are further to execute said instructions using said superimposed grid of points by:

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

35. The device of claim 34, wherein to analyze said description of said at least said portion of said building structure 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 comprising one or more rooms or hallways 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 a description of at least a portion of a building structure;

superimpose a grid of points onto said description of said at least said portion of said building structure;

analyze said description of said at least said portion of said building structure using said superimposed grid of points by projecting multiple rays from multiple points of said superimposed grid of points;

interconnect one or more autonomous areas interior to said building structure based at least partially on a number of impacts of said projecting multiple rays with a closed polygon; and

create at least one routing graph responsive to said analyzing, said interconnecting, and based at least in part on said superimposed grid of points and said description of said at least said portion of said building structure.

37. The article of claim 36, wherein to analyze said description of said at least said portion of said building structure 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, said determining of said interior points based at least partially on a first threshold number of impacts of said projecting multiple rays, said determining of said exterior points based at least partially on a second threshold number of impacts of said projecting multiple rays.

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 the 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:

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

if said number of said multiple projected rays that impact the building feature is determined to meet said first threshold number, 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 description of said at least said portion of said building structure 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 comprising rooms or hallways 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 comprising one or more rooms or hallways.

49. The article of claim 36, wherein to analyze said description of said at least said portion of said building structure 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 comprising one or more rooms or hallways based at least in part on determining if a particular autonomous area of said multiple autonomous areas on an opposite side of a bounding wall, which is between a given feasible autonomous area comprising one or more rooms or hallways of said multiple autonomous areas and said 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 directions, a full routing graph, a partial routing graph, or a combination thereof 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 description of said at least said portion of said building structure said at least one storage medium has stored thereon further instructions executable by one or more processors to:

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

52. The article of claim 51, wherein to analyze said description of said at least said portion of said building structure 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 comprising one or more rooms or hallways 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 a description of at least a portion of a building structure;

means for superimposing a grid of points onto said description of said at least said portion of said building structure;

means for analyzing said description of said at least said portion of said building structure using said superimposed grid of points by projecting multiple rays from multiple points of said superimposed grid of points;

means for interconnecting one or more autonomous areas comprising one or more rooms or hallways of said building structure based at least partially on a number of impacts of said projecting multiple rays with a closed polygon and

means for creating at least one routing graph responsive to said analyzing, said interconnecting, and based at least in part on said superimposed grid of points and said description of said at least said portion of said building structure.

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, said determining of said interior points based at least partially on a first threshold number of impacts of said projecting multiple rays, said determining of said exterior points based at least partially on a second threshold number of impacts of said projecting multiple rays.

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 the 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 the 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 the building feature is determined to meet said first threshold number.

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 comprising one or more rooms or hallways 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 comprising one or more rooms or hallways.

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 comprising one or more rooms or always based at least in part on determining if a particular autonomous area of said multiple autonomous areas on an opposite side of a bounding wall, which is between a given feasible autonomous area comprising one or more rooms or hallways of said multiple autonomous areas and said particular autonomous area, comprises a hallway.

67. The apparatus of claim 53, further comprising:

means for initiating transmission to a mobile device directions, a full routing graph, a partial routing graph, or a combination thereof 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 any rays of said multiple rays projected 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 comprising one or more rooms or hallways of said building structure.