Polygonal routing

Patent metadata

Field	Value
Publication number	US-9823079-B2
Application number	US-201514869830-A
Country	US
Kind code	B2
Filing date	Sep 29, 2015
Priority date	Sep 29, 2015
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

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.

First claim

What is claimed is:

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.

Assignees

• Apple Inc

Inventors

• Marusco Austin A
• Agarwal Ashish
• Strawn Justin M
• Kumar Mithilesh
• Arroyo Vincent P
• Muller Iii Max
• Samsalovic Vojislav

Classifications

• G01C21/206 Primary

  specially adapted for indoor navigation · CPC title