POLYGONAL ROUTING

摘要

Methods, systems, and computer program products for polygonal routing are described. A computer system can provide turn-by-turn navigation in a venue for a mobile device using a navigation graph. The navigation graph can include nodes representing a series of navigation areas leading from a start point to an end point in a venue including indoor space. Each navigation area can be a polygon occupying a non-zero geographic area. The computer system updates the turn-by-turn instructions when the mobile device enters or exits a navigation area in the series of navigation areas, until the device reaches the end point.

主权项

1. A method comprising:
receiving, by one or more processors, venue data, the venue data including a plurality of destination areas each representing a unit in a venue; receiving, by the one or more processors and from an input device, a plurality of primary waypoints, the plurality waypoints representing points on a path in the venue, wherein each unit is located adjacent to the path; determining a respective secondary waypoint on the path for each unit, wherein a distance between the secondary waypoint and a centroid of the unit is a shortest distance between the path and the centroid of the unit; determining a respective waypoint area surrounding each primary waypoint and each secondary waypoint, wherein each waypoint area has a perimeter that is limited by a width of the path; and providing a representation of the destination areas and waypoint areas as a navigation graph for generating instructions for turn-by-turn navigation in the venue.