I need an algorithm to group the closest GPS coordinates.
I am currently using OSRM to manage that for me, but due to its limitations (100 items per request), I’m going to have to make my own local implementation.
I’ve read about Dijkstra’s, A* (its variation), contraction hierarchies, etc… From what I understood, most of them, if not all, require the points to have a connection and that’s where my problem lies. In my scenario all coordinates are “connected” to each other. You could reach any by any. I just want them to be grouped by the closest.
One example is displayed in the image below (take it with a grain of salt, it’s just a visual representation to try and explain my problem):
In the scenario proposed by the image above, I have 187 coordinates and require them to be in groups of 5 of the closest coordinates. Given that using real maps would require a lot of memory, I’d like to just use the distance between points, ignoring edges, roads and profiles (walking, driving, etc – even though walking would be the way to go).
I understand that by not using a real map I will run into issues like: “closest GPS coordinate requires crossing a river”, but that’s something I can live with, at the moment.
Given the above explanation, my questions are:
1 – Is there an algorithm, other than the ones mentioned, that would help me solve that problem?
2 – If Dijkstra’s is the way to go, could I create manual connections between the coordinates so they would work? How would it work with Dijkstra’s?
Hopefully I was able to clearly explain the problem, but if not, please ask me any questions you may have so I can improve it.
- I was using OSRM
- I migrated to a local (erratic) solution using .NET’s
.Distance - I read about Dijkstra’s, A* (its variation) and contraction hierarchies algorithms