search

NoahSchiro / every-street

GNU General Public License v3.0
2 stars 2 forks source link

Incorrect heatmap coloring #11

Open Sasni opened 4 months ago

Sasni commented 4 months ago

Hi, I tested your code. IS GREAT. I have a question about coloring routes that need to be traveled multiple times. I noticed that the colors are not presented correctly.

image

I don't understand why (inner road) is colored different colors. If it is a one-time ride, it should be blue, but if it is a round trip (i.e. 2 times), it should be green. In my opinion, vertices are incorrectly interpreted and every "point" is taken into account - every intersection with another object, e.g. a pedestrian path (and turns around on them?). I don't see any way to leave this road except to turn around, so in my opinion the color should be uniform (the same). Do I think right?

NoahSchiro commented 4 months ago

Thanks for the kind words, but the code isn't very good haha. It needs a rewrite / update. Your thinking is right though, those lines should be colored so that they all show green (you walk over it twice).

I've noticed this issue as well in some other tests. Could you send me whatever osm / polygon you are using as input? I want to be able to exactly copy what you have here in my testing.

I will look into it here, no promises on a speedy delivery

Sasni commented 3 months ago

I think you should assume that:

It would be a great help to add the ability to generate a GPX file with a route.

NoahSchiro commented 3 months ago

This problem is essentially the Route Inspection Problem so the solution is a Hamiltonian Path which is proven to be the optimal route and works in polynomial time so your assumptions are baked into a more general solution.

Essentially, the algorithm tries to find Euler Circuits. If it's possible to find an Euler Circuit that encompasses the whole map then that is an optimal path (you will only traverse each road once). This is very rare. In all other cases, it tries to compose as many Euler Circuits as it can and then connects them with a shortest path algorithm. The connections are "repeat" traversals of the same road but it is still optimal. I'm pretty sure the algorithm is sound, it's just the map coloring that is incorrect.

To be honest, I am a little busy with a research project this summer and it is consuming a little more time then I would like. I may not be able to spend a ton of time on this for a little bit but PRs are welcome :)