Candidates algorithm: find unmapped routes

The following is the description of the algorithm steps that are being made when try to find unmapped routes: The main flow can be found in the following class AddibleGpxLinesFinderService:

1. Increase density - this steps takes the original GPS trace and adds point to make sure there aren't any big gaps in the recording, we use 2.5 meters (half of 5 which is defined as lines that are close enough):

2. Find missing lines (create initial candidates) - this step removes all the points that are close to existing lines. we use a 30 meter radius. and then removes short lines - we use 200 meters lines and above. here's an example of the results of a missing lines:

$\color{red}{red}$ are the candidates $\color{blue}{blue}$ is the original trace $\color{green}{green}$ is the existing line with the 30 meters radius

3. Split self loops and remove duplication - this step travel across the unmapped lines and split the lines when it finds a line that creates a self loop - this is done by going over every point from end to start going away from close proximity points and see if there are other points along the line that returns to the proximity of the first node. In the following image the red dot is the self closing point which will cause a split to the line. The red circle area is the proximity area - we use 30 meters.

step 2 will be performed now on new lines to remove duplication. here is the above example after this step:

4. Simplification step - to reduce the number of points Douglas-Packard and an updated version of the radial simplification is begin performed on the candidates.

5. Prolong lines according to original GPS trace - this step is used to connect some of the candidates. the algorithm for this travel back on the line between points, for every two "consecutive" points on the original gps trace the algorithm have the following options:

• the line creates a self loop - in this case the area of this loop is calculated and if it's big enough the loop will be closed, otherwise this section of the trace will be ignored. we use 1000 square meters.

• the line connects two lines that are already connected - which will create a closed area, the above is used again.

• the line connects two lines that are far from one another - in this case this section will be added.

We use 5 meter to define lines that are close enough to one another. Here's the results using the above example: