/Indoor-Positioning-And-Navigation-Algorithms

Strongly accurate indoor positioning algorithms with the main focus on indoor navigation developed by Navigine company. Here we will step by step publish the source code of our algorithm starting with trilateration.

Primary LanguageC++MIT LicenseMIT

Indoor-navigation-algorithms
Build Build

Useful Links

  • Refer to the Navigine official website for complete list of downloads, useful materials, information about the company, and so on.
  • Get started with Navigine to get full access to Navigation services, SDKs, and applications.
  • Refer to the Navigine User Manual for complete product usage guidelines.
  • Find company contact information at the official website under Contacts tab.

Contents

This repository consists of the following components

  • src - the source code of Navigine positioning algorithms

  • standalone_algorithms - set of algorithms used in navigation

  • tests - test and utilities for the evaluation of source code quality

  • tools - utilities for data extraction from map and settings

Creating Navigation Client

Here are some examples to give you an idea how to use Navigation Client.

First, create variables that will store your data.

    // variables for storing location elements
    navigine::navigation_core::GeoLevel geoLevel;
    std::shared_ptr<navigine::navigation_core::LevelCollector> levelCollector;
    navigine::navigation_core::NavigationSettings navigationSettings;
    std::shared_ptr<navigine::navigation_core::NavigationClient> navClient;

Add transmitters (Beacon, Eddystone, WIFI, WIFI-RTT, etc.) as GeoTransmitters from your location.

Then they will be converted to XYTransmitters for internal evaluations

Parameters:
    - id - identifier of transmitter like (major,minor,uuid) for beacon, (namespaceId,instanceId) for eddystone, mac for WIFI;
    - point - latitude and longitude as GeoPoint;
    - pathlossModel - A, B and power of transmitter as `PathlossModel` struct variable;
    - type - type of transmitter, like Beacon, Eddystone, WIFI, WIFI-RTT, etc..

Inside for loop add all the transmitters from your location. Here is an example of adding one element

    geoLevel.transmitters.emplace_back(transmitterId,
                              navigine::navigation_core::GeoPoint(latitude, longitude),
                              navigine::navigation_core::PathlossModel{A, B, power},
                              navigine::navigation_core::TransmitterType::BEACON);

Create geometry of the level using method getGeometry from barriers_geometry_builder.h file. Geometry could be created using the barriers and the size of the level

Parameters:
    - barrierList - list of polygons, where each polygon describes the barrier of the level;
    - allowedArea - polygon, which is created using width and height of the map;

Create the list of Polygons which will describe all the barriers

    std::list<navigine::navigation_core::Polygon> barriersList;
    for (size_t i = 0; i < barriers.size(); ++i)
    {
        auto coords = barriers.at(i);
        navigine::navigation_core::Polygon barrier;
        for (const auto& coord : coords)
            boost::geometry::append(barrier, navigine::navigation_core::Point(coord.first, coord.second));

        barriersList.push_back(barrier);
    }

Create the polygon of allowed area

    navigine::navigation_core::Polygon levelArea;
    auto boundingBox = navigation_core::Box(
                                   navigation_core::Point(leftMin.latitude, leftMin.longitude),
                                   navigation_core::Point(rightMax.latitude, rightMax.longitude));
    boost::geometry::convert(boundingBox, allowedArea);
    geoLevel.geometry = navigine::navigation_core::getGeometry(barriersList, levelArea);

Create LevelCollector using method createLevelCollector and add all available geo levels.

    levelCollector = navigine::navigation_core::createLevelCollector();
    levelCollector->addGeoLevel(geoLevel);

Create NavigationSettings, with two parameters - level settings and common settings. (You can find them in navigation.xml i.e.)

Create NavigationClient using method createNavigationClient which will take as arguments level collector and navigation settings.

    navClient = navigine::navigation_core::createNavigationClient(levelCollector, navigationSettings);

Navigation test

The example of navigation is presented in a file Navigation Test. The test application takes 3 parameters:

  • path to the file of the location in geojson format
  • path to the file of logs gathered in this location in json format
  • path to the settings file in json format in which parameters of the algorithm are specified

Build

In order to build the test application go to the root directory of the repository and execute the following commands

cmake -H. -Bbuild
cmake --build build

To run the tests

cd build/
./navigation_test location.geojson log.json settings.json

Evaluate the navigation

Quality of navigation can be evaluated via calculation of different navigational errors. The most important among them are presented in the following table

Error Description
nav_err Average navigation error in meters
q_75_err 75% quantile of all the measurements have navigation error less than the value of nav_75_err
avr_fi Average angle error in degrees
level_err Percentage of wrongly determined levels
exec_time Execution time in seconds

Navigation Algorithms explanation

Here are lectures on navigational algorithms used in this repository