I have created an offline navigation app for garmin watches, it includes a routing algorithm so as to route offline across the coords data representing a road map of europe stored in the app. The routing algorithm is very slow, it can take 25 minutes for a route from London to Glasgow to generate, I am interested in modifying it to be faster or translating a faster algorithm to ConnectIQ, my ability to do so is hindered by ConnectIQ lacking some features of other langauges and vice versa as well as documentation being exceptionally jargony or not explaining each step. I have included my code with comments and an example piece of data for context:
Example shortened data, destination and start will always be one of the numbers in the data:
[[-0.369,53.795,-0.477,53.843,-0.656,53.859,-0.789,53.919,-1.012,53.957],[-0.993,51.448,-0.979,51.451],[-0.985,50.848,-0.988,50.786]]
if (MapArr != null) {
if (RoutePick != Map.size()){
//go through all inner arrays of current MapArr to find the closest point to start
var array = MapArr[add];
for (var j = 0; j < array.size(); j+=2) {
var CurrentX = array[j];
var CurrentY = array[j+1];
var package = [startLat,startLon,CurrentX,CurrentY];
var distance = distance(package);
hasit = route.indexOf(CurrentX);
hasit2 = route.indexOf(CurrentY);
//check if route contains point already
if (distance < minDistanceToStart && CurrentX != startLon && CurrentY != startLat && hasit == -1 && hasit2 == -1) {
currentArr = array;
minDistanceToStart = distance;
c2SIndex = j;
}
}
if (add == (MapArr.size() - 1)){
if (RoutePick != (Map.size() - 1)){
add = 0;
RoutePick = RoutePick + 1;
//go through the current array to find the closest point to destination
WatchUi.requestUpdate();}
else if (RoutePick == (Map.size() - 1)){
for (var k=0; k<currentArr.size(); k+=2) {
var CurrentX = currentArr[k];
var CurrentY = currentArr[k+1];
var package = [destLat,destLon,CurrentX,CurrentY];
var distance = distance(package);
hasit = route.indexOf(CurrentX);
hasit2 = route.indexOf(CurrentY);
//check if route contains point already
if (distance < minDistanceToDest && hasit == -1) {
closestToDestX = CurrentX;
closestToDestY = CurrentY;
minDistanceToDest = distance;
c2DIndex = k;
}
}
//reverse array if start index is greater than destination index and Add the points to the route array.
router = [];
if (c2SIndex > c2DIndex) {
for (var l = c2SIndex; l > c2DIndex; l-=2){
router.addAll([currentArr[l],currentArr[l+1]]);
}
}
// Add the points to the route array.
else if (c2SIndex < c2DIndex){
for (var l = c2SIndex; l < c2DIndex; l+=2) {
router.addAll([currentArr[l],currentArr[l+1]]);
}
//System.println(c2DIndex + "," + c2SIndex + "Don't reverse");
}
//if points are equal then add the points to the route array this way.
else if (c2SIndex == c2DIndex){
router.addAll([currentArr[c2SIndex],currentArr[c2SIndex + 1]]);
}
hasit = route.indexOf(router);
if (router.size() > 0 && hasit == -1){
route.addAll(router);}
router = null;
//if destination found then finish
if (closestToDestX == destLon && closestToDestY == destLat || route[0] == destLat && route[1] == destLon){
RoutePick = Map.size();
System.println("route finished");
route.add(destLon);
route.add(destLat);
generateRoute = null;
NumPick = 0;
var m = Position.getInfo().position;
m = m.toDegrees();
startLat = m[0];
startLon = m[1];
//begin process to draw map and route
MapviewerView.GenerateBitmap();
}
else {
reset iterations to keep searching, i believe this is where my troubles with the speed are.
add = 0;
RoutePick = 0;
startLat = closestToDestY;
startLon = closestToDestX;
minDistanceToDest = 2147483647;
minDistanceToStart = 2147483647;
WatchUi.requestUpdate();
}
}
}
else if (add < (MapArr.size() - 1)) {
add = add + 1;
WatchUi.requestUpdate();
}
}
}
}
The speed at which a solution can be calculated will be a reflection of the computing power available (which isn't much on a Garmin watch) and the efficiency of the algorithm/code used to calculate the route. Without running your code, it looks like your method is essentially O(n^2) which may run okay when the number of points n is small, but is grossly inefficient when n gets larger.
Off the top of my head, I would look at implementing a simple Greedy algorithm, which might be the best compromise given the constraints of the Connect IQ platform. This article on Medium should give you a good overview and also includes all the citations (for even more reading).
You may also want to look at doing some pre-processing of the data set prior to running the search; if the data contains information for France but the route is entirely in the UK then try dropping any data that is obviously out of scope.
Ultimately, though, you may find that the best solution, even though you originally asked for an offline one, would be to use an API call to an online resource. In today's 'Internet-almost-everywhere' life, it might work to have an option to calculate the route in the cloud (for the best solution) and calculate on device only if necessary and accept that the solution will be either fast (but not the best solution) or slow (with a better solution).
Another option is to start with a Greedy offline traverse, to minimize any delay and/or handle a lack of Internet, but ultimately use the cloud for your final solution.