METHODS AND APPARATUSES FOR USE IN GENERATING AN ENCODED ROUTEABILITY GRAPH DESCRIPTION

• US 20120016872A1
• Filed: 07/11/2011
• Published: 01/19/2012
• Est. Priority Date: 07/13/2010
• Status: Abandoned Application

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Khorashadi, Behrooz, Gupta, Rajarshi, Das, Saumitra Mohan
• Application Number:
  US13/180,153
• Publication Number:
  US 20120016872A1
• Time in Patent Office: Days
• US Class Current: 707/724
• 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: G09B 29/006 Representation of non-cartographic information on maps, e.g. population distribution, wind direction, radiation levels, air and sea routes

Abstract

Methods and apparatuses are provided that may be implemented in one or more electronic devices to generate an encoded routeability graph description corresponding to a diagram of a structure. The methods and apparatuses may, for example, implement a reduction process to reduce a number of grid points within an encoded routeability graph description, or which may be otherwise used to generate an encoded routeability graph description.

Claims

1. A method of generating an encoded routeability graph description, the method comprising:

projecting grid points over a diagram of an indoor area, said diagram indicating at least some route obstructions in said indoor area;

ranking said grid points based, at least in part, on distances between said grid points and said route obstructions; and

selectively merging grid points with locations of higher ranking neighboring grid points based, at least in part, on an absence of route obstructions between the locations and grid points which are neighboring said merged grid points.

2. The method as recited in claim 1, wherein said ranking said grid points further comprises:

determining distances along axes through at least one of said grid points; and

ranking said at least one of said grid points based, at least in part, on a shortest distance along said axes to at least one of said route obstructions.

3. The method as recited in claim 2, wherein said distances are determined as an integer number of grid point hops along said axes.

4. The method as recited in claim 1, and further comprising:

following said selectively merging said grid points, selectively merging remaining un-merged grid points with locations of neighboring un-merged grid points having a higher rank, at least in part, in the absence of route obstructions between the locations of said neighboring un-merged grid points neighboring said un-merged grid points to be merged.

5. The method as recited in claim 1, wherein said generating said reduced encoded routeability graph description further comprises connecting remaining neighboring un-merged grid points as nodes in said encoded routeability graph description.

6. A method comprising:

with a computing device;

assigning a set of grid points to locations on a diagram, wherein at least a portion of said diagram is indicative of at least one feature within a portion of a structure;

ranking at least a portion of said grid points based, at least in part, on proximities of said locations to said at least one feature; and

reducing said set of grid points by selectively merging a first grid point with a second grid point that is adjacent to said first grid point and which has a higher ranking than said first grid point, and provided that;

(1) there are no route obstructions in said diagram between said second grid point and any other grid points that are adjacent to said first grid point, and

(2) there would have been no route obstructions in said diagram between said second grid point and any grid points that were previously merged with said first grid point.

7. The method as recited in claim 6, wherein, by selectively merging said first grid point with said second gird point, said second grid point inherits said any grid points that were previously merged with said first grid point.

8. The method as recited in claim 6, where said reducing said set of grid points is performed iteratively beginning with a highest ranked grid point.

9. The method as recited in claim 6, where said reducing said set of grid points is performed iteratively until there are no further grid points available to be selectively merged.

10. The method as recited in claim 6, and further comprising:

generating an encoded routeability graph description based, at least in part, on at least a portion of said reduced set of grid points.

11. An apparatus for use in generating an encoded routeability graph description, the apparatus comprising:

means for projecting grid points over a diagram of an indoor area, said diagram indicating at least some route obstructions in said indoor area;

means for ranking said grid points based, at least in part, on distances between said grid points and said route obstructions; and

means for selectively merging grid points with locations of higher ranking neighboring grid points based, at least in part, on an absence of route obstructions between the locations and grid points which are neighboring said merged grid points.

12. The apparatus as recited in claim 11, and said means for ranking said grid points further comprises:

means for determining distances along axes through at least one of said grid points; and

means for ranking said at least one of said grid points based, at least in part, on a shortest distance along said axes to at least one of said route obstructions.

13. The apparatus as recited in claim 12, wherein said distances are determined as an integer number of grid point hops along said axes.

14. The apparatus as recited in claim 11, and further comprising:

means for selectively merging remaining un-merged grid points with locations of neighboring un-merged grid points having a higher rank, at least in part, in the absence of route obstructions between the locations of said neighboring un-merged grid points neighboring said un-merged grid points to be merged.

15. The apparatus as recited in claim 11, wherein said means for generating said encoded routeability graph description further comprises:

means for connecting remaining neighboring un-merged grid points as nodes in said encoded routeability graph description.

16. An apparatus for use in a computing device, the apparatus comprising:

means for assigning a set of grid points to locations on a diagram, wherein at least a portion of said diagram is indicative of at least one feature within a portion of a structure;

means for ranking at least a portion of said grid points based, at least in part, on proximities of said locations to said at least one feature; and

means for reducing said set of grid points by selectively merging a first grid point with a second grid point that is adjacent to said first grid point and which has a higher ranking than said first grid point, and provided that;

(1) there are no route obstructions in said diagram between said second grid point and any other grid points that are adjacent to said first grid point, and

(2) there would have been no route obstructions in said diagram between said second grid point and any grid points that were previously merged with said first grid point.

17. The apparatus as recited in claim 16, wherein, by selectively merging said first grid point with said second gird point, said second grid point inherits said any grid points that were previously merged with said first grid point.

18. The apparatus as recited in claim 16, where said means for reducing said set of grid points is performed iteratively beginning with a highest ranked grid point.

19. The apparatus as recited in claim 16, where said means for reducing said set of grid points is performed iteratively until there are no further grid points available to be selectively merged.

20. The apparatus as recited in claim 16, and further comprising:

means for generating an encoded routeability graph description based, at least in part, on at least a portion of said reduced set of grid points.

21. A device for generating an encoded routeability graph description, the device comprising:

memory; and

a processing unit to;

project grid points over a diagram of an indoor area, said diagram indicating at least some route obstructions in said indoor area;

rank said grid points based, at least in part, on distances between said grid points and said route obstructions; and

selectively merge grid points with locations of higher ranking neighboring grid points based, at least in part, on an absence of route obstructions between the locations and grid points which are neighboring said merged grid points.

22. The device as recited in claim 21, said processing unit to further:

determine distances along axes through at least one of said grid points; and

rank said at least one of said grid points based, at least in part, on a shortest distance along said axes to at least one of said route obstructions.

23. The device as recited in claim 22, wherein said distances are determined as an integer number of grid point hops along said axes.

24. The device as recited in claim 21, said processing unit to further, following said selectively merging said grid points, selectively merge remaining un-merged grid points with locations of neighboring un-merged grid points having a higher rank, at least in part, in the absence of route obstructions between the locations of said neighboring un-merged grid points neighboring said un-merged grid points to be merged.

25. The device as recited in claim 21, said processing unit to further connect remaining neighboring un-merged grid points as nodes in said encoded routeability graph description.

26. The device as recited in claim 21, said processing unit to further generate said encoded routeability graph description for storage in said memory.

27. A device comprising:

memory; and

a processing unit to;

assign a set of grid points to locations on a diagram, wherein at least a portion of said diagram is indicative of at least one feature within a portion of a structure;

rank at least a portion of said grid points based, at least in part, on proximities of said locations to said at least one feature; and

reduce said set of grid points by selectively merging a first grid point with a second grid point that is adjacent to said first grid point and which has a higher ranking than said first grid point, and provided that;

(1) there are no route obstructions in said diagram between said second grid point and any other grid points that are adjacent to said first grid point, and

(2) there would have been no route obstructions in said diagram between said second grid point and any grid points that were previously merged with said first grid point.

28. The device as recited in claim 27, wherein, by selectively merging said first grid point with said second gird point, said second grid point inherits said any grid points that were previously merged with said first grid point.

29. The device as recited in claim 27, said processing unit to further reduce said set of grid points iteratively beginning with a highest ranked grid point.

30. The device as recited in claim 27, said processing unit to further reduce said set of grid points iteratively until there are no further grid points available to be selectively merged.

31. The device as recited in claim 27, said processing unit to further:

generate an encoded routeability graph description for storage in said memory based, at least in part, on at least a portion of said reduced set of grid points.

32. An article for use in generating an encoded routeability graph description, the article comprising:

a non-transitory computer readable medium having stored therein computer implementable instructions executable by a processing unit to;

project grid points over a diagram of an indoor area, said diagram indicating at least some route obstructions in said indoor area;

rank said grid points based, at least in part, on distances between said grid points and said route obstructions; and

selectively merge grid points with locations of higher ranking neighboring grid points based, at least in part, on an absence of route obstructions between the locations and grid points which are neighboring said merged grid points.

33. The article as recited in claim 32, said computer implementable instructions being further executable by said processing unit to:

determine distances along axes through at least one of said grid points; and

rank said at least one of said grid points based, at least in part, on a shortest distance along said axes to at least one of said route obstructions.

34. The article as recited in claim 33, wherein said distances are determined as an integer number of grid point hops along said axes.

35. The article as recited in claim 32, said computer implementable instructions being further executable by said processing unit to, following said selectively merging said grid points, selectively merge remaining un-merged grid points with locations of neighboring un-merged grid points having a higher rank, at least in part, in the absence of route obstructions between the locations of said neighboring un-merged grid points neighboring said un-merged grid points to be merged.

36. The article as recited in claim 32, said computer implementable instructions being further executable by said processing unit to connect remaining neighboring un-merged grid points as nodes in said encoded routeability graph description.

37. An article comprising:

a non-transitory computer readable medium having stored therein computer implementable instructions executable by a processing unit to;

assign a set of grid points to locations on a diagram, wherein at least a portion of said diagram is indicative of at least one feature within a portion of a structure;

rank at least a portion of said grid points based, at least in part, on proximities of said locations to said at least one feature; and

reduce said set of grid points by selectively merging a first grid point with a second grid point that is adjacent to said first grid point and which has a higher ranking than said first grid point, and provided that;

(1) there are no route obstructions in said diagram between said second grid point and any other grid points that are adjacent to said first grid point, and

(2) there would have been no route obstructions in said diagram between said second grid point and any grid points that were previously merged with said first grid point.

38. The device as recited in claim 37, wherein, by selectively merging said first grid point with said second gird point, said second grid point inherits said any grid points that were previously merged with said first grid point.

39. The device as recited in claim 37, said computer implementable instructions being further executable by said processing unit to reduce said set of grid points iteratively beginning with a highest ranked grid point.

40. The device as recited in claim 37, said computer implementable instructions being further executable by said processing unit to reduce said set of grid points iteratively until there are no further grid points available to be selectively merged.

41. The device as recited in claim 37, said computer implementable instructions being further executable by said processing unit to generate an encoded routeability graph description based, at least in part, on at least a portion of said reduced set of grid points.