CODEWITHSUNDEEP
javascriptalgorithmgoogle-mapssorting
andro1d
andro1d

Reputation: 568

Advanced Sorting Algorithm

I'm writing an app in Javascript that uses Google maps and calculates a full route between a series of legs based off closest legs.

Say I've got 4 legs on the map, each leg has a start and end Latitude and Longitude. The user specifies which two legs are the start and end of the route. Each end of a leg can only connect to another legs start. Then the end of that leg connects to another legs start, and so on. The code determines which legs start to connect to based off the closest leg it can find.

Something like this for example (the dashed lines are the legs):

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

I've got an array of all of the leg coordinates, and I want to sort this array so that it follows the proper progression of connections. Then I can utilize the array to generate the connectors by linearly looping through it.

The array looks something like this:

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

Those will be the inner legs. And then I'll have the outer legs (the two legs that are the start and the end of the entire route) stored in variables:

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

As an example it might end up something like:

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

Or it might end up like:

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

The algorithm needs to sort the array based off the start legs end_lat,end_lng and the end legs end_lat,end_lng.

The end result will be a big route connected together with the shortest path.

I'm struggling to think of a way of writing the sorting algorithm that takes these unique factors into consideration.

It's difficult to put this into words, and I'm not really sure how I can help make it clearer, but I'll edit this post if I can think of anything useful to add. Thanks.

Edit:

Here's a picture of what I'm talking about:

map

The black lines are the legs, the red lines are the connectors I will need to generate after I've sorted the array of leg coordinates into the correct order. The generating the connectors isn't part of this algorithm, but it's just an example of what I'm trying to accomplish so you can understand the big picture. As you can see there are gaps between the legs, none of the coordinates overlap.

Upvotes: 0

Views: 293

Answers (2)

user1472571
user1472571

Reputation: 71

I think DFS is Okay and transfer visited ordered leg list to next recursion. and in every recursion choose the last leg and recursive with each unvisted legs.

Upvotes: 0

plalx
plalx

Reputation: 43728

You could do something like this:

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));

Basically we find the next point that starts where start ends and let that point become the next start until there's no match and at each step we push the point into result.

EDIT:

This would work of the coordinates of the start and end point overlapped, but none of mine do, there is a large gap between them and I need to generate the 'connectors' between them...

I have expanded my first idea by using an algorithm to calculate the closest point insead of looking for overlapping coords.

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));

Notice that the points are geo coordinates and you will need to use a spherical distance algorithm, not the trivial pythagoras. I think GM provides such helper functions for their data structures; of course the algorithm will still work with a different distanceBetween implementation. – @Bergi

Upvotes: 2

Related Questions