# US 2018/0025099 A1 · Method and an apparatus for calculating a distance in an area

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

- Number: US 2018/0025099 A1
- Document ID: US20180025099A1
- Status: Published application
- Kind: A1
- Application number: 15/657,257
- Filed: 2017-07-24
- Published: 2018-01-25
- Earliest claimed: 2016-07-25
- Assignees: Xinaps B.V.
- Applicants: Xinaps B.V.
- Inventors: Geert van Gorp; Thijs Boumans; Frank Schuyer
- Web page: https://patentgrep.com/patent/US20180025099A1

## CPC

- G06F 30/3323: using formal methods, e.g. equivalence checking or property checking
- G01C 21/206: {specially adapted for indoor navigation}
- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G06F 30/00: Computer-aided design [CAD]
- G06F 30/10: Geometric CAD
- G06F 30/13: Architectural design, e.g. computer-aided architectural design [CAAD] related to design of buildings, bridges, landscapes, production plants or roads
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- 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

A method for calculating a distance includes receiving a map of an area converted as a first polygon; determining a plurality of vertices of the first polygon; determining a pair of the plurality of vertices that does not have an obstruction of the area intersecting a connecting line of the pair; generating a navigation mesh with the pair as a connecting line of the navigation mesh; and determining a distance between two points in the area using the navigation mesh.

## Claims

### Claim 1

A method for calculating a distance comprising:
receiving a map of an area converted as a first polygon;
determining a plurality of vertices of the first polygon;
determining a pair of the plurality of vertices that does not have an obstruction of the area intersecting a connecting line of the pair;
generating a navigation mesh with the pair as a connecting line of the navigation mesh; and
determining a distance between two points in the area using the navigation mesh.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the first polygon is provided with a hole with vertices.

### Claim 3 (depends on 1)

The method according to claim 1, wherein determining a plurality of vertices of the first polygon comprises excluding vertices from the plurality of vertices of the first polygon with a convex internal angle.

### Claim 4 (depends on 3)

The method according to claim 3, further comprising excluding vertices of a hole inside the first polygon with a concave internal angle of the hole.

### Claim 5 (depends on 1)

The method according to claim 1, further comprising shifting the plurality of vertices towards the interior of the first polygon by a clearance variable generating a second polygon.

### Claim 6 (depends on 5)

The method according to claim 5, wherein the clearance variable depends on the position of the plurality of vertices on the first polygon.

### Claim 7 (depends on 5)

The method according to claim 5, further comprising rounding two edges of a vertex of the plurality of vertices by adding an additional vertex to the second polygon.

### Claim 8 (depends on 1)

The method according to claim 1, wherein the connecting line of the navigation mesh has a weight that is the length of the connecting line.

### Claim 9 (depends on 5)

The method according to claim 5, wherein the obstruction of the area comprises an edge of the first polygon and/or the second polygon.

### Claim 10 (depends on 1)

The method according to claim 1, wherein the map of the area comprises data from at least one of a Building Information Model, BIM, and Computer Aided Design, CAD data.

### Claim 11 (depends on 1)

The method according to claim 1, further comprising adding an additional point to the navigation mesh.

### Claim 12 (depends on 1)

The method according to claim 1, wherein determining a distance between two points in the area using the navigation mesh comprises using a navigation algorithm to determine the distance between the two points.

### Claim 13 (depends on 12)

The method according to claim 12, wherein the navigation algorithm is the Dijkstra's algorithm or the A* Pathfinding algorithm.

### Claim 14 (depends on 1)

The method according to claim 1, wherein the distance calculated is the shortest distance between two points in an area.

### Claim 15 (depends on 1)

The method according to claim 1, and further comprising the step of generating a distance map.

### Claim 16

A device for calculating a distance comprising
a loading module configured to
receive a map of an area converted as a first polygon; and
a processor configured to
determine a plurality of vertices of the first polygon
determine a pair of the plurality of vertices that does not have an obstruction of the area intersecting a connecting line of the pair;
generate a navigation mesh with the pair as a connecting line of the navigation mesh; and
determine a distance between two points in the area using the navigation mesh.

### Claim 17 (depends on 1)

A non-transitory computer-readable medium for calculating a distance, comprising instructions for causing a computer system to perform the method according to claim 1.
