Polygonal routing

• US 9,823,079 B2
• Filed: 09/29/2015
• Issued: 11/21/2017
• Est. Priority Date: 09/29/2015
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Marusco, Austin A., Agarwal, Ashish, Strawn, Justin M., Kumar, Mithilesh, Arroyo, Vincent P., Muller, III, Max, Samsalovic, Vojislav
• Primary Examiner(s): Sweeney, Brian P
• Application Number:
  US14/869,830
• Publication Number:
  US 20170089709A1
• Time in Patent Office: 784 Days
• Field of Search: 701533
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation

Abstract

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.

Claims

1. A method comprising:

receiving, from a mobile device at one or more processors, a request to navigate from a start point in a venue to an end point in the venue;

receiving, at the one or more processors, a navigation graph representing the venue, the navigation graph including;

nodes representing destination areas and waypoint areas, wherein each destination area and waypoint area is defined by a respective geometric shape, and

one or more edges, wherein each edge connects two of the nodes, and wherein each edge is associated with a respective weight representing a distance between the areas represented by the two nodes connected by the edge;

determining, using the one or more processors, a first node representing a first area defined by a first geometric shape, wherein the first area intersects the start point in the venue, and a second node representing a second area defined by a second geometric shape, wherein the second area intersects the end point in the venue;

determining, using the one or more processors based on weights of the edges of the navigation graph, a shortest path from the first node to a second node, the shortest path including one or more intermediate nodes each representing a respective waypoint area; and

generating, using the one or more processors, turn-by-turn instructions for navigating from the start point to the end point, including updating a next-turn instruction upon determining that the mobile device has entered or exited a geometric shape of a waypoint area or destination area in the venue that is represented by a node on the shortest path.

2. The method of claim 1, wherein the one or more processors are components of the mobile device or components of a server that is located remotely from the mobile device.

3. The method of claim 1, wherein the distance between the two nodes includes:

a direct-line distance between centroids of two areas represented by the two nodes if no unit in the venue interrupts the direct-line distance;

or

a direct-line distance between centroids of two areas represented by the two nodes adjusted by a factor associated with a unit in the venue that interrupts the direct-line distance.

4. The method of claim 1, wherein each waypoint area has a centroid located on a path in the venue, a distance between the centroid and a centroid of a destination area being a shortest distance between the centroid of the destination area and the path.

5. The method of claim 1, wherein the navigation graph further includes a node representing a connection area, the connection area being a segment of a path in the venue, the path including at least a section of a walkway or an open area connecting a plurality of waypoint areas.

6. The method of claim 5, wherein:

determining the first node comprises determining that the start point intersects a connection area represented in the navigation graph but not a destination area or a waypoint area represented in the navigation graph; and

determining the shortest path comprises;

determining a plurality of candidate shortest paths each from a candidate area that intersects the connection area and neighbors the start point to the area that intersects the end point; and

selecting the shortest path from the candidate shortest paths based on lengths of the candidate shortest paths and a distance between the start point to each candidate area.

7. The method of claim 1, wherein updating a next-turn instruction is triggered by exit of the mobile device from a waypoint area in which the mobile device has been previously instructed to turn.

8. A system, comprising:

one or more processors; and

a non-transitory computer-readable medium storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising;

receiving, from a mobile device at the one or more processors, a request to navigate from a start point in a venue to an end point in the venue;

receiving, at the one or more processors, a navigation graph representing the venue, the navigation graph including;

nodes representing destination areas and waypoint areas, wherein each destination area and waypoint area is defined by a respective geometric shape, and

one or more edges, wherein each edge connects two of the nodes, and wherein each edge is associated with a respective weight representing a distance between the areas represented by the two nodes connected by the edge;

determining, using the one or more processors, a first node representing a first area defined by a first geometric shape, wherein the first area intersects the start point in the venue, and a second node representing a second area defined by a second geometric shape, wherein the second area intersects the end point in the venue;

determining, using the one or more processors based on weights of the edges of the navigation graph, a shortest path from the first node to a second node, the shortest path including one or more intermediate nodes each representing a respective waypoint area; and

generating, using the one or more processors, turn-by-turn instructions for navigating from the start point to the end point, including updating a next-turn instruction upon determining that the mobile device has entered or exited a geometric shape of a waypoint area or destination area in the venue that is represented by a node on the shortest path.

9. The system of claim 8, wherein the one or more processors are components of the mobile device or components of a server that is located remotely from the mobile device.

10. The system of claim 8, wherein the distance between the two nodes includes:

a direct-line distance between centroids of two areas represented by the two nodes if no unit in the venue interrupts the direct-line distance;

or

a direct-line distance between centroids of two areas represented by the two nodes adjusted by a factor associated with a unit in the venue that interrupts the direct-line distance.

11. The system of claim 8, wherein each waypoint area has a centroid located on a path in the venue, a distance between the centroid and a centroid of a destination area being a shortest distance between the centroid of the destination area and the path.

12. The system of claim 8, wherein the navigation graph further includes a node representing a connection area, the connection area being a segment of a path in the venue, the path including at least a section of a walkway or an open area connecting a plurality of waypoint areas.