Google maps — как построить логичный, короткий маршрут?

Question

[Алекс]

Собственно имеются точки.
А - стартовая
D - конечная

Маршрут строится по очередности точек в массиве. (a,b,c,d)
Возможно ли как то сделать маршрут более логичным с точки зрения человека?
Т.е. мы начинаем свой пусть в точке А, следующая у нас идет точка В, но короче и вероятно логичнее было бы глянуть точку D а затем уже В.
Может есть встроенный механизм или готовый алгоритм исчисления?

Comments

[Алексей Немиро]

Вроде Google сам может строить маршруты, более ли менее человеческие:
https://developers.google.com/maps/documentation/d...
https://developers.google.com/maps/documentation/d...

[Алекс]

Алексей Немиро: Есть параметр optimizeWaypoints: true,
Но результат с ним на скриншоте.

[Алекс]

Алексей Немиро:

var request = {
        origin: start,
        destination: end,
        waypoints: waypts,
        optimizeWaypoints: true,
        travelMode: google.maps.TravelMode.WALKING
      };

      directionsService.route(request, function(result, status) {
        if (status == google.maps.DirectionsStatus.OK) {
          directionsDisplay.setDirections(result);
        }
      });

[Дмитрий Энтелис]

Не знаю насчет google но вообще это задача коммивояжера в чистом виде

[Алекс]

Дмитрий Энтелис: Согласен. Но не разу не решал ее, да и не знаком с алгоритмом.

Answer 1

[Sergej]

Вам требуется вычислить самую дальнюю точку от стартовой.
Эта дальняя точка будет конечной, остальные точки построятся автоматически.
Формула:
Ri= SQRT((xi-x1)**2+(yi-y1)**2)

Пример изходя из прошлого вопроса:

var waypoints = [
      "40.7513888888889,-73.9777777777778",
      "40.7083333333333,-74.0141666666667",
      "40.7752777777778,-73.9769444444444",
      "40.7252222222222,-73.9993888888889",
      "40.7652777777778,-73.9791666666667"
    ];
var andrLT = []; 
var andrLN = []; 
var Ri;
for (i = 0; i < waypoints.length; i++) {
      andrLT.push(parseFloat(waypoints[i].split(',')[0]));
      andrLN.push(parseFloat(waypoints[i].split(',')[1]));
}

for (i = 0; i < waypoints.length; i++) {
      sqrt = Math.sqrt(((40.7791666666667 - andrLT[i])*2 + (73.9583333333333 - andrLT[i])*2)+300);
      Ri.push([ sqrt ]);
}

// Узнаем максимальное значение массива точек
console.log(Math.max.apply(Math, Ri));

Вы получили дальнюю точку, далее условиями получите координаты и уже реализуете механизм.

Answer 2

[Дмитрий Энтелис]

math.semestr.ru/kom/kom_practice.php
https://www.lektorium.tv/lecture/14235

Answer 3

[Avivar]

Посмотрите google maps api https://developers.google.com/maps/customize?hl=ru

Создание персонализированных вариантов маршрутов
API маршрутов позволяет создавать оптимальные варианты проезда. Если же реализовать функцию перетаскивания, пользователи смогут самостоятельно прокладывать маршруты непосредственно на карте. При оптимизации маршрута с целью сокращения времени в пути и расстояния выполняется упорядочивание до 25 пунктов маршрута. Использование API матрицы расстояний дает пользователям возможность просмотреть данные о расстоянии до пунктов назначения и времени в пути.

Comments

[Алекс]

Не совсем то. Хотя может проглядел.
Требуется делать без участия пользователя.
Т.е. пользователь выбрал объекты, на карте ему уже должен выйти готовый маршрут.
Что бы это сделать, требуется знать соответственно начальную точку а конечную придется вычислять.
Т.е. конечная точка, должна быть самая дальняя.