# US 2016/0252355 A1 · Generating routes using navigation meshes

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0252355 A1
- Document ID: US20160252355A1
- Status: Published application
- Kind: A1
- Application number: 14/633,751
- Filed: 2015-02-27
- Published: 2016-09-01
- Earliest claimed: 2015-02-27
- Assignees: HERE Global B.V.
- Applicants: HERE Global B.V.
- Inventors: Joseph Paul Mays; Robert Fernekes
- Web page: https://patentgrep.com/patent/US20160252355A1

## CPC

- G01C 21/206: {specially adapted for indoor navigation}
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)

## Abstract

Systems, apparatuses, and methods are provided for developing an improved route from a navigation mesh. A route is provided, wherein the route includes a plurality of connected nodes having a starting node, an ending node, and internal nodes. Each internal node of the plurality of connected nodes is scored by an algorithm, wherein the score provided for each internal node based on an importance of the respective internal node to the overall shape of the route. The internal node with a score having a least importance on the shape of the route is removed, so long a valid path between the starting node and the ending node is maintained. The process may be repeated until a threshold simplification of the route has been achieved or until no further internal nodes can be removed without creating an invalid path.

## Claims

### Claim 1

A method comprising:
receiving a route comprising a plurality of connected nodes having a starting node, an ending node, and internal nodes;
scoring, using a processor, each internal node of the plurality of connected nodes, wherein a score is provided for each internal node based on an importance of the respective internal node to a shape of the route;
removing an internal node with a score having a least importance on the shape of the route while maintaining a valid route between the starting node and the ending node such that the valid route does not cross into a non-navigable area;
repeating the scoring and the removing of the internal nodes, while maintaining the valid route, until no further internal nodes can be removed without creating an invalid route; and
providing an updated route.

### Claim at position 2

-3. (canceled)

### Claim 4 (depends on 1)

The method of claim 1, wherein the scoring of each internal node is based upon an incoming segment length from a first adjacent node to the respective internal node and an outgoing segment length from the respective internal node to a second, opposite adjacent node.

### Claim 5 (depends on 1)

The method of claim 1, wherein a higher importance is provided for a larger incoming segment length over a smaller incoming segment length, and a larger outgoing segment length over a smaller outgoing segment length.

### Claim 6 (depends on 1)

The method of claim 1, wherein the scoring of each internal node is based upon a path angle created between a first adjacent node, the respective internal node, and a second, opposite adjacent node.

### Claim 7 (depends on 6)

The method of claim 6, wherein a higher importance is provided for a smaller path angle over a larger path angle.

### Claim 8 (depends on 1)

The method of claim 1, wherein the scoring of each internal node is based upon a proximity of the respective node to a non-traversable object.

### Claim 9 (depends on 1)

The method of claim 1, wherein the scoring of each internal node is based upon (1) an incoming segment length from a first adjacent node to the respective internal node and an outgoing segment length from the respective internal node to a second, opposite adjacent node, and (2) a path angle created between the first adjacent node, the respective internal node, and the second, opposite adjacent node.

### Claim 10 (depends on 9)

The method of claim 9, wherein the scoring of each internal node is a weighted scoring based upon the incoming segment length, the outgoing segment length, and the path angle.

### Claim 11 (depends on 1)

The method of claim 1, wherein the scoring of each internal node is a weighted scoring based on the following equation:
Overall Node Value=w1*f1+w2*f2+ . . . +wN*fN,
wherein:
f1, f2, . . . , fN=scoring values for each individual factor for a total of N factors, and
w1, w2, . . . , wN=respective weights for each individual factor, and
w1+w2+ . . . +wN=1.

### Claim 12 (depends on 1)

The method of claim 1, wherein the scoring of each internal node is based upon a curve evolution algorithm.

### Claim 13 (depends on 1)

The method of claim 1, wherein the route is generated from a navigation mesh.

### Claim 14 (depends on 13)

The method of claim 13, wherein the scoring of each internal node is a weighted scoring based on a resolution of the navigation mesh.

### Claim 15 (depends on 1)

The method of claim 1, wherein the updated route is provided for use in an indoor map, video game, or robotic application.

### Claim 16

A method comprising:
receiving a route generated from a navigation mesh, the route comprising a plurality of connected nodes having a starting node, an ending node, and internal nodes;
scoring, using a processor, each internal node of the plurality of connected nodes, wherein a score is determined for each internal node based on an importance of the respective internal node to a shape of the route, the score being based upon (1) an incoming segment length from a first adjacent node to the respective internal node and an outgoing segment length from the respective internal node to a second, opposite adjacent node, and (2) a path angle created between the first adjacent node, the respective internal node, and the second, opposite adjacent node;
removing an internal node with a score having a least importance on the shape of the route while maintaining a valid route between the starting node and the ending node such that the valid route does not cross into a non-navigable area;
repeating the scoring and the removing of the internal nodes, while maintaining the valid route, until no further internal nodes can be removed; and
providing an updated route without the removed internal nodes.

### Claim 17

An apparatus comprising:
at least one processor; and
at least one memory including computer program code for one or more programs;
the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform:
receive a route comprising a plurality of connected nodes having a starting node, an ending node, and internal nodes;
score each internal node of the plurality of connected nodes, wherein a score is provided for each internal node based on an importance of the respective internal node to a shape of the route;
remove an internal node with a score having a least importance on the shape of the route while maintaining a valid route between the starting node and the ending node such that the valid route does not cross into a non-navigable area;
repeat the scoring and the removing of the internal nodes, while maintaining the valid route, until no further internal nodes can be removed without creating an invalid route; and
provide an updated route.

### Claim at position 17

-19. (canceled)

### Claim 20 (depends on 17)

The apparatus of claim 17, wherein the scoring of each internal node is based upon an incoming segment length from a first adjacent node to the respective internal node and an outgoing segment length from the respective internal node to a second, opposite adjacent node, wherein a higher importance is provided for a larger incoming segment length over a smaller incoming segment length, and a larger outgoing segment length over a smaller outgoing segment length.

### Claim 21 (depends on 17)

The apparatus of claim 17, wherein the scoring of each internal node is based upon a path angle created between a first adjacent node, the respective internal node, and a second, opposite adjacent node, wherein a higher importance is provided for a smaller path angle over a larger path angle.
