Finding unmapped routes

[Nerdyvedi]

Hi, I am very intrigued by the Candidate's algorithm and wish to understand it better and test it's accuracy.

I have GPS traces for some country other than Israel, and wish to test the algorithm's accuracy on them. Also, It would mean a lot if you could elaborate the wiki. I was not really able to understand everything clearly.

Thanks.

[HarelM]

Thanks for reaching out.
Since our server do not support other countries besides israel I think the best approach for you to test the algorithm is to create a local server and configure it with the relevant country.
I'll be happy to help out with guidance.
Regarding the wiki, please ask specific questions in order to understand and I'll do my best to answer, finally we could update the wiki for future use.

[HarelM]

The following is the definition of the file to fetch when updating the server's databases with an OSM pbf file:
https://github.com/IsraelHikingMap/Site/blob/master/IsraelHiking.API/Executors/OsmLatestFileFetcherExecutor.cs
It should probably move to a configuration file instead of being hard coded...
If you get to a point of updating the databases (using the swagger UI) I suggest to only update the highways database instead of all of them - it's faster and the only thing the algorithm really needs from the database.

[Nerdyvedi]

Questions on the wiki :
I got the first and second steps, but beyond that it seems a little complicated. I could not understand the step you are using to remove self loops. What would be great is if you could add images before and after applying the step, so we could understand from the images how the step worked.

Does the algorithm use all the existing roads on the map, or does it only use highways ?

I would be really grateful if you could add the steps to set up the server for MacOS as well.

Pardon me for troubling you.

[HarelM]

The third step is probably the most complex one code-wise and explanation-wise.
The reasoning for this step is that in many recordings you want know when the user went to a place and returned to the same place (back and forth). It's easy to describe it in words or see it, but hard to code it.
The way we decided to solve this is by a n^2 like algorithm:
This is what I tired to explain with the picture as it can't really be presented well using the map examples I added.
You start with the last point on the recording and define a radius around it. Now you travel backwards until you leave the radius - this means that you are far away enough from that starting point. You continue to travel backwards until you enter that radius again - if you do it means that the route has a "self loop" (a loop if you will).
The algorithm splits the route into the part up until that point and from that point on, and continues to do so until the end of the route.
If there were no self loops the algorithm continues to the second point from the end and does it again using a radius around that point and so on and so on.
Finishing this part means you now have a route that is split, every split doesn't have loops in it.
Now the second step can be used by adding one more part of the route after the other and remove points which are too close to a previously added route part, thus eliminating the parts of the route which the user traveled back and forth leaving only one direction.
Code can be found here if it help in any way:

Site/IsraelHiking.API/Services/AddibleGpxLinesFinderService.cs

Line 134 in 03bb62e

private List<LineString> SplitSelfLoopsAndRemoveDuplication(List<LineString> missingLines)

Site/IsraelHiking.API/Executors/GpxLoopsSplitterExecutor.cs

Line 48 in 03bb62e

public List<LineString> SplitSelfLoops(LineString gpxLine, double minimalDistanceToClosestPoint)

Regarding MacOS, I have recently bought a MacOS but didn't have the time to fully configure a development environment to be able to load the server there.
I thought about using Docker for this but encountered issues with System.Drawing that requires some kind of C library to be installed, and so it needs more work...

There are two options here regarding MacOS: 1. You can install a windows boot on mac and follow the windows step (I heard it's possible, haven't tried it myself).
2. You can play with it until you succeed and let me know which steps you took and I'll update the readme file, it should be able to work as .net core and node can be installed and run on a mac.
3. Wait for me to understand how to do it and update the readme file, it might take some time though...

[Nerdyvedi]

Okay, Thanks a lot. I will try to run it on my mac and let you know.
Just one more thing, Does the algorithm only use Highways, or does it require every marked road on the map.

[HarelM]

It uses a database, the database holds only osm ways that has the highway tag.
The algorithm itself only needs to be able to get existing lines in an area to work (an empty list is also valid).

[Nerdyvedi]

@HarelM , I tried to run the server on Mac, seems like a lot of work. Is it possible for you to just test your algorithm on a couple of GPS traces that I have.

No one in my team owns a windows machine, we want to quickly check if we can use your algorithm or not. Don't bother if it's a lot of trouble, but it would really mean a lot if you could help.

[HarelM]

I can try, it might take me a few days though and I can't promise it'll work. Please attach the traces here (preferably a GPX file that you've change its extension to .txt, or zipped it).
And I'll need an address to an OSM pbf file that contains highways of the relevant region. You can probably find one in Geofabrik...

[HarelM]

@Nerdyvedi any updates on this? KML can also work ;-)

[Nerdyvedi]

@HarelM , Just give me a couple of days. I am trying to find traces which would be a good test for the algorithm, Like traces where a road network is actually missing.

[HarelM]

@Nerdyvedi I have worked in the past few days on the ability to load the site using docker.
I'm not sure how well it will behave on MacOS, but I think it's worth a shot.
Please try and pull latest changes.
Search the code for israel-and-palestine and replace it as needed.
Run docker-compose up.
Make sure in docker setting that it has 4g memory and not 2g as elasticsearch will fail with only 2g.
If you manage to surf to localhost:5000 after the docker-compose up settles then I can continue the instructions on how to build the database to allow the algorithm to run.

[Nerdyvedi]

Okay, Thanks a lot for this, It would be really helpful. I will let you know

[HarelM]

I'm closing this issue, feel free to continue writing here, I just don't want this to appear in my issues list.