OPV Graphe

This document is written in Broken English
The goal of this module is to create virtual tour from a campaign of panorama taken in a hiking session.
At the end of the session, you only have the GPS position of the panorama, and it's not simple to link all panorama together to create a virtual tour. A simple way to resovle this problem is to take the hour of each panorama as a parameter to link them. But if you have multiples cameras or your cameras are not really precise (like time reset), you can't really create a "precise" tour.
The purpose of this module is to create the most precise tour with only the GPS position of each panrama. To resolv this problem, this module used Graphe and alogrithm like:

• Breadth First Search
• Dijktra

The main step of the resolution of this problems are:

• 1) Detect near nodes between each nodes, and create edges
• 2) Search endpoints of the merge graphe
• 3) Reduce the node number (take one paramater each X meters)

Installation

Create a virtualenv to test it

pyvenv venv
source venv/bin/activate

Install requirements

pip install -r requirements.txt

Install the package

python setup.py isntall

How to launch

You can launch the api with this command:

gunicorn --bind 0.0.0.0:5000 opv.graphe.__main__:app -w 8

How to test

The api came with a swagger, you can use it:

http://127.0.0.1:5000/apidocs/

You can test with our campaign at Parc national des Ecrins, data are store in:

cat example_data.json

Interface to show the graphe on a Leaflet map

To show a graphe on the leaflet map, you must convert it with a POST on /to_leaflet

I made a web interface to show graphe (don't judge me, I'm not a frontend guy). You can acces it with the /map endpoint:

http://127.0.0.1:5000/map

And simply click on the "Load Data" button to copy paste the json of your graphe.

And your graphe will be show:

The legend for the marker is:

• A blue marker is a node
• A red marker is a hot point
• A green marker is a endpoint

If you check the "Show nodes" checkbox, it will show all nodes:

1) /create_edges/{perimeter}/{radial_spacing} => Detect near nodes between each nodes, and create edges

To create edges between panorama, we will use a home algorithm that detect near panoras for each panoramas. It have 2 parammeters:

• perimeter d = The maximum distance bewteen two node, to consider it near
• radial_spacing alpha = The maximum angle between two nodes to consider it near

For example if we take 5 points (A, B, C, D, E)

The next steps are run on each point. For the example, we will run it on the A point.

1.1) Detect near nodes with distance

The first step is to detect the nodes that are d meters from the node A.

The node that are < distance are:

• B
• C
• D

The nearest node (node B in our example) is take as the referential.

Now we will use alpha to determine the other near panorama

1.2) Detect near panorama with alpha angle

Now we have our reference point (B), we will consider all node as near if the angle between BAX > alpha.

• Has the BAC angle is < alpha, we don't take it has a near panorama.
• But the BAD angle is > alpha, so we consider it has a near panorama.

1.3) Final graphe

If we run all previous step on each node, we will have this final graphe:

And you will understan the main problem. Our tour have holes, we must fill this holes.

1.4) Detect subgraphe and merge them

To fill all the holes, we will:

• Detect subgraphe with the Breadth First Search algorithm
• Merge all subgraphe

The detection of the subgraphe is a classical implementation of the Breadth First Search algorithm, so I will not describe it.
But the merge subgraphe algorithm is a home made, so I will describe it here:
So after the Breadth First Search algorithm:

It found 3 subgraphes:

• D, A, B, C
• E
• F, G, H

To merge this subpgraphe, we take a subgraphe as a referential (for the example, we will take the graphe D, A, B, C) and we found the nearest subgraphe and merge it.

REF
LIST_SUBGRAPHES
WHEN LIST_SUBGRAPHES NOT EMPTY
  FOUND NEAREST SUBGRAPHE
  MERGE IT WITH REF
END
        

The nearest subgraphe is E, so we merge it:

The nearest subgraphe is F, G, H, so we merge it:

With the data in example_data.json:

2) /detect_endpoints => Search endpoints of the merge graphe

The actual algorithm is pretty simple, it only consider as endpoint a node that only have one edge.

With the data in example_data.json:

3) /reduce/{reduce}/{min_path} => Reduce the graphe to keep a node each "reduce" meter

3.1) Compute path between endpoints and hotpoints and reduce the graphe

For this part, I simply used the Dijkstra alogrithm to compute the shortest path between ALL endpoints/hot point.

3.2) Reduce the node number (take one paramater each X meters)

TODO: Write the documentation

With the data in example_data.json with a reduction at 50 meters: