I have a set of locations that I want to display to a user in proximity order - closest to farthest - based on their current coordinates. Assume we have ~100 data points of locations which includes each one's latitude and longitude (in some kind of object or array), and we know the user's lat and long. The goal is to display an ordered list of locations -- and it is beneficial if we can get and display to the user the nearest 8-10 locations while we calculate then display the remaining distances.

I know the brute-force solution is to loop through all locations, calculate the distance from the user, put them in order, then display them all to the user. But this is too slow.

A better solution is this one: where you check within a bounded box first, expanding if necessary, then do the rest.

I've also seen there are other algorithms out there - like FLANN and other methods - but I haven't seen any examples written in JavaScript.

So the question: What is the fastest way to calculate (and display in order) nearest points in JavaScript?

I have a set of locations that I want to display to a user in proximity order - closest to farthest - based on their current coordinates. Assume we have ~100 data points of locations which includes each one's latitude and longitude (in some kind of object or array), and we know the user's lat and long. The goal is to display an ordered list of locations -- and it is beneficial if we can get and display to the user the nearest 8-10 locations while we calculate then display the remaining distances.

I know the brute-force solution is to loop through all locations, calculate the distance from the user, put them in order, then display them all to the user. But this is too slow.

A better solution is this one: https://stackoverflow./a/2466908/1766230 where you check within a bounded box first, expanding if necessary, then do the rest.

I've also seen there are other algorithms out there - like FLANN and other methods - but I haven't seen any examples written in JavaScript.

So the question: What is the fastest way to calculate (and display in order) nearest points in JavaScript?

• javascript
• algorithm
• maps
• distance

• With ~100 points it is unlikely that you will see much, if any, benefit of the "divide and conquer" method over the "naive (brute force)" method. The naive method is very simple to implement. – Xotic750 Commented Mar 6, 2014 at 21:55
• It's actually for a mobile app using Titanium. Have to do more digging to know why it appears to be such a bottleneck at the moment... but regardless, I'd like to find the optimal solution if it's not too difficult rather than just brute-force it. – Luke Commented Mar 6, 2014 at 22:00
• From what I understand the "divide and conquer" method is optimal O(n log n) - depending on sort algorithm (merge sort required, I think) – Xotic750 Commented Mar 6, 2014 at 22:06
• Do you have any examples of "divide and conquer" in JavaScript? – Luke Commented Mar 6, 2014 at 22:10
• Nope, only a wiki reference that describes the algorithm. en.wikipedia/wiki/… – Xotic750 Commented Mar 6, 2014 at 22:12

2 Answers 2

So, if you are starting out with that list of points, drawing a small bounding box won't cut down very much, because you still do an O(n) check against all points for their location.

I would advise using a max-length heap or some other form of partial sort while iterating through all of the points. This lets you keep track of a small subset of approximately maximum/minimal points (as described by the length), so you can render those quickly before dealing with the rest. If you need more explanation about what I'm saying precisely, let me know.

Also what are you making this for that has such stringent performance issues? Typically putation like this shouldn't be a stress point, barring that you have 100k+ points. DOM manipulation is usually the most expensive spot

var points = [];
for (i = 0; i < 100; i++) {
    var point = [getRandomInt(0, 999), getRandomInt(0, 999)];
    point.len = distanceBetweenPoints(point, [499,499]);
    points.push(point);
}

console.log(Heap.nsmallest(points, 10, function (a, b) {
  return a.len < b.len;
}));

Here is the performance for it pared to bruteforce

Heap Code

js fiddle

Using the method I described, and a prebuilt heap another person wrote, I pared our methods. I think you will be happy! It performed 8,586 ops/sec pared to the 566 in the brute force technique!

Well this is my attempt at sorting an array of points by distance to a given point. This is brute-force as far as I understand. Then I slice the array to give you the 10 closest points.

Javascript

function distanceBetweenPoints(p1, p2) {
    return Math.abs(Math.sqrt((p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1])));
}

function sortByDistance(location, arrayOfPoints) {
    arrayOfPoints.sort(function (a, b) {
        a.distance = distanceBetweenPoints(location, a);
        b.distance = distanceBetweenPoints(location, b);

        return a.distance - b.distance;
    });

    return arrayOfPoints;
}

function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

var points = [];

for (i = 0; i < 100; i += 1) {
    points.push([getRandomInt(-90, 90), getRandomInt(-180, 180)]);
}

console.log(sortByDistance([0, 0], points).slice(0, 10));

On jsFiddle

This will at least give you something to test algorithms against. And here is a jsPerf for the above, so you can add other routines to it and do some real performance parisons.

Note: This does not take into consideration that the Earth is a sphere! This is calculating Euclidean distance and not Geodesic distance. This is fine if the points, are for example, in the same town (or close proximity) but not if they are in different countries/continents. It also assumes that you have converted your longitude and latitude to a decimal representation.

Otherwise you will need to look at things like Great-circle distance and Haversine formula

In fact, the earth is very slightly ellipsoidal; using a spherical model gives errors typically up to 0.3%

Javascript

function toRadians(degrees) {
    return (degrees * Math.PI) / 180;
}

// Haversine formula
function distanceBetweenPoints(p1, p2) {
    var R = 6371, // mean earth radius in km
        lat1 = toRadians(p1[0]),
        lon1 = toRadians(p1[1]),
        lat2 = toRadians(p2[0]),
        lon2 = toRadians(p2[1]),
        dLat = lat2 - lat1,
        dLon = lon2 - lon1,
        a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.sin(dLon / 2) * Math.sin(dLon / 2) * Math.cos(lat1) * Math.cos(lat2),
        c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a)),
        d = R * c;

    return d;
}

function sortByDistance(location, arrayOfPoints) {
    arrayOfPoints.sort(function (a, b) {
        a.distance = distanceBetweenPoints(location, a);
        b.distance = distanceBetweenPoints(location, b);

        return a.distance - b.distance;
    });

    return arrayOfPoints;
}

function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

var points = [];

for (i = 0; i < 100; i += 1) {
    points.push([getRandomInt(-90, 90), getRandomInt(-180, 180)]);
}

console.log(sortByDistance([0, 0], points).slice(0, 10));

On jsFiddle