主权项 |
1. A computer-implemented method comprising:
accessing, by one or more processors, a preliminary map associated with an indoor space; converting, by the one or more processors, the preliminary map into a segmented map, wherein the segmented map distinguishes a navigable area of the indoor space from a non-navigable area of the indoor space; generating, by the one or more processors, a directed graph corresponding to the indoor space based on the segmented map, the directed graph comprising a plurality of nodes connected by a plurality of paths, the plurality of nodes corresponding to points of a set of points in the navigable area of the indoor space and the plurality of paths corresponding to routes between the points, wherein the directed graph is generated by:
executing a distance transform on the segmented map to generate a distance map, wherein the distance map identifies, for each point of the set of points in the navigable area, a distance between that point to a nearest point in the non-navigable area;for each point of the set of points in the navigable area, identifying a value that indicates the likelihood that a route would pass through that point, the value based on a position of that point in the indoor space; andgenerating the plurality of nodes for the directed graph based on the values, wherein the plurality of nodes correspond to points of the set of points of the navigable area;generating the plurality of paths for the directed graph based on the plurality of nodes, the plurality of paths corresponding to routes between the plurality of nodes; storing, by the one or more processors, the directed graph for subsequent access to identify a route between two locations in the indoor space; receiving, by the one or more processors, a request for directions to a location in the indoor space; and displaying, by the one or more processors, a route to the location based on the directed graph. |