Patent Document ID: 9173069
Application ID: 14118714
Patent Status: 1

Claim One:
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, 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, using a processor by a client device, 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 a server identifying an initial navigable pixel and expanding the 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 server provides the borders to the client device.