Расширенный алгоритм сортировки

Question

Я пишу приложение в Javascript, которое использует карты Google и вычисляет полный маршрут между сериями ног, основанных на самых близких ногах.

Скажем, у меня есть 4 ноги на карте, каждая нога имеет начало и конец Широта и долгота. Пользователь указывает, какие две ноги являются началом и концом маршрута. Каждый конец ноги может подключаться только к другому ногу. Затем конец этой ноги соединяется с началом других ног и так далее. Код определяет, какие ноги начинают соединяться с основанной на ближайшей ноге, которую он может найти.

Нечто подобное, например (пунктирные линии ноги):

start-----------end <-connector-> start----------end <-connector-> start----------end 

У меня есть массив всех координат ног, и я хочу, чтобы отсортировать этот массив, так что следует за правильное развитие соединений. Затем я могу использовать массив для генерации коннекторов путем линейного циклирования через него.

массив выглядит примерно так:

[ 
    {start_lat: X, start_lng: X, end_lat: X, end_lng: X}, 
    {start_lat: X, start_lng: X, end_lat: X, end_lng: X}, 
] 

Те будут внутренние ноги. И тогда я буду иметь наружные ноги (две ноги, которые являются началом и концом всего маршрута), хранящиеся в переменных:

var start = {end_lat: X, end_lng: X} 
var end = {start_lat: X, start_lng: X} 

В качестве примера он может в конечном итоге что-то вроде:

start -> array[0] -> array[1] -> end 

Или это может в конечном итоге, как:

start -> array[1] -> array[0] -> end 

алгоритма необходимо для сортировки массива на основе пусковой ноги end_lat, end_lng и end_lat конец ноги, end_lng.

Конечным результатом будет большой маршрут, соединенный с кратчайшим путем.

Я изо всех сил пытаюсь придумать способ написания алгоритма сортировки, учитывающий эти уникальные факторы.

Трудно выразить это словами, и я не совсем уверен, как я могу помочь сделать его более ясным, но я отредактирую этот пост, если смогу придумать что-нибудь полезное для добавления. Благодарю.

Edit:

Вот картина того, что я говорю о:

черные линии ноги, красные линии являются соединители, мне нужно будет генерировать после того как я отсортировал массив координат ног в правильном порядке. Генерация разъемов не является частью этого алгоритма, но это всего лишь пример того, что я пытаюсь выполнить, чтобы вы могли понять общую картину. Поскольку вы видите, что между ногами имеются промежутки, ни одна из координат не перекрывается.

Answer 1

Вы могли бы сделать что-то вроде этого:

DEMO

var start = { end_lat: 1, end_lng: 1 }, 
    end = { start_lat: 4, start_lng: 4 }, 
    coordsBetween = [ 
     { start_lat: 2, start_lng: 2, end_lat: 3, end_lng: 3 }, 
     { start_lat: 1, start_lng: 1, end_lat: 2, end_lng: 2 }, 
     { start_lat: 3, start_lng: 3, end_lat: 4, end_lng: 4 } 
    ]; 

function orderedCoords(start, coords) { 
    var result = [], 
     point = start; 

    while (point = coords.filter(function (item) { 
     return item.start_lat === point.end_lat 
     && item.start_lng === point.end_lng; 
    })[0]) { 
     result.push(point); 
    } 
    return result; 
} 

console.log(orderedCoords(start, coordsBetween)); 

В основном мы находим следующий point, которая начинается где start концы и пусть это point стать следующей start пока нет матча и на каждом шаге мы нажимаем точку на result.

EDIT:

Это будет работать координат начальной и конечной точки внахлест, но ни один из моих не делать, существует большой разрыв между ними и мне нужно генерировать «разъемы» между ними ...

Я раскрыл свою первую идею, используя insead, чтобы найти перекрывающиеся координаты.

DEMO

var start = { end_lat: 1, end_lng: 1 }, 
    end = { start_lat: 4, start_lng: 4 }, 
    segments = [ 
     { start_lat: 2, start_lng: 2, end_lat: 3, end_lng: 3 }, 
     { start_lat: 1, start_lng: 1, end_lat: 2, end_lng: 2 }, 
     { start_lat: 3, start_lng: 3, end_lat: 4, end_lng: 4 } 
    ]; 

function orderedSegments(start, segments) { 
    var result = [], 
     segment = start, 
     i; 

    while ((i = indexOfClosestSegment(segment, segments)) !== -1) { 
     result.push(segment = segments.splice(i, 1)[0]); 
    } 

    return result; 
} 

function indexOfClosestSegment(segment, segments) { 
    var i = 0, 
     len = segments.length, 
     segIndex = -1, 
     tempDistance, smallestDistance; 

    for (; i < len; i++) { 
     if (
      (tempDistance = distanceBetween(segment, segments[i])) < smallestDistance 
      || typeof smallestDistance === 'undefined') { 
      smallestDistance = tempDistance; 
      segIndex = i; 
     } 
    } 

    return segIndex;   
} 

function distanceBetween(segmentA, segmentB) { 
    return Math.sqrt(
     Math.pow(segmentB.start_lat - segmentA.end_lat, 2) 
     + Math.pow(segmentB.start_lng - segmentA.end_lng, 2) 
    ); 
} 

console.log(orderedSegments(start, segments)); 

Обратите внимание, что точки являются географическими координатами и вам нужно будет использовать алгоритм сферического расстояния, не тривиальный Пифагор. Я думаю, что GM предоставляет такие вспомогательные функции для своих структур данных; конечно алгоритм по-прежнему будет работать с разным расстоянием между . - @Bergi

Answer 2

Я думаю, что это ДФС Хорошо и передача посетили упорядоченный список ноги к следующему рекурсии. и в каждой рекурсии выберете последнюю ногу и рекурсивную с каждой ножкой.