Navigating using an indoor map representation
First Claim
1. A computer implemented method for providing indoor navigation, the method comprising:
- determining a client location;
identifying the client location as being within a source polygon selected from a plurality of convex polygons having borders, the plurality of convex polygons defined by a map model that comprises the plurality of convex polygons and a set of adjacency relationships among the plurality of convex polygons, the plurality of convex polygons being associated with navigable space within a given geographical area;
receiving a destination location;
determining whether the destination location is located within navigable space or a non-navigable area;
determining a destination polygon based on the determination of whether the destination location is located within navigable space or the non-navigable area;
determining, with one or more processors, a route from the source polygon to the destination polygon using the map model by identifying a path defined by the set of adjacency relationships; and
providing the route from the source polygon to the destination polygon as a navigation path from the client location to the destination location;
wherein the borders of each convex polygon is determined at least in part by the one or more processors identifying an initial navigable pixel and expanding a border in a direction away from the initial navigable pixel until reaching at least one pixel associated with non-navigable space in said direction, and the one or more processors provides the borders to a client device.
2 Assignments
0 Petitions
Accused Products
Abstract
A method and system for providing an indoor map representation are provided herein. Aspects of this disclosure provide a representation of an indoor map environment whereby navigable areas are represented by a series of convex polygons in adjacency relationships with one another. Image analysis may be performed on a floor plan image to identify navigable areas and to determine the boundaries of the polygons, such as by assigning one or more colors to navigable space and one or more colors to non-navigable space. Route-finding operations may be performed using the adjacency relationships to find a path from a source area to a destination area.
-
Citations
20 Claims
-
1. A computer implemented method for providing indoor navigation, the method comprising:
-
determining a client location; identifying the client location as being within a source polygon selected from a plurality of convex polygons having borders, the plurality of convex polygons defined by a map model that comprises the plurality of convex polygons and a set of adjacency relationships among the plurality of convex polygons, the plurality of convex polygons being associated with navigable space within a given geographical area; receiving a destination location; determining whether the destination location is located within navigable space or a non-navigable area; determining a destination polygon based on the determination of whether the destination location is located within navigable space or the non-navigable area; determining, with one or more processors, a route from the source polygon to the destination polygon using the map model by identifying a path defined by the set of adjacency relationships; and providing the route from the source polygon to the destination polygon as a navigation path from the client location to the destination location; wherein the borders of each convex polygon is determined at least in part by the one or more processors identifying an initial navigable pixel and expanding a border in a direction away from the initial navigable pixel until reaching at least one pixel associated with non-navigable space in said direction, and the one or more processors provides the borders to a client device. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method comprising:
-
generating a map model that comprises a plurality of polygons having borders and a set of adjacency relationships among the plurality of polygons, the plurality of polygons being associated with navigable space within a given geographical area, by identifying an initial navigable pixel and expanding a border in a direction away from the initial navigable pixel until reaching at least one pixel associated with non-navigable space in said direction; determining a first location of a device; identifying, using one or more processors, the first location as being within a source polygon selected from a plurality of polygons having borders, the plurality of polygons defined by the map model; receiving a destination location; determining a destination polygon based on whether the destination location is located within navigable space or non-navigable space; determining, using the one or more processors, a route from the source polygon to the destination polygon using the map model by identifying a path defined by the set of adjacency relationships; and providing, for display to a user of the device, the route from the source polygon to the destination polygon as a navigation path from the first location to the destination location. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A system for providing indoor navigation comprising:
-
a navigation element for providing a current location of a device; one or more processors; and a memory accessible by the one or more processors, the memory comprising a map model that includes a plurality of convex polygons having borders and a set of adjacency relationships among the plurality of convex polygons, the plurality of convex polygons being associated with navigable space within a given geographical area, wherein the navigable space is determined by identifying a navigable pixel and analyzing adjacent pixels to identify one or more boundaries of the plurality of convex polygons by extrapolating one or more non-navigable areas; the memory further comprising instructions executable by the one or more processors, the instructions comprising; identifying the current location provided by the navigation element as being within a source polygon selected from the plurality of convex polygons; receiving a destination location; determining whether the destination location is located within navigable space or a non-navigable space; determining a destination polygon based on the determination of whether the destination location is located within navigable space or the non-navigable space; determining a route from the source polygon to the destination polygon using the map model by identifying a path defined by the set of adjacency relationships; providing the route from the source polygon to the destination polygon as a navigation path from the client location to the destination location; wherein the borders of each convex polygon is determined at least in part by one or more processors identifying an initial navigable pixel and expanding a border in a direction away from the initial navigable pixel until reaching at least one pixel associated with non-navigable space in said direction. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification