Как эффективно рассчитать ближайшие 2D-точки в JavaScript?

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

Я бы посоветовал использовать кучу максимальной длины или какую-либо другую форму частичной сортировки при повторении всех точек. Это позволяет вам отслеживать небольшое подмножество приблизительно максимальных / минимальных точек (как описано длиной), чтобы вы могли быстро отрендерить их, прежде чем разбираться с остальными. Если вам нужно больше пояснений по поводу того, что я говорю, дайте мне знать.

И что вы делаете из-за таких серьезных проблем с производительностью? Обычно такие вычисления не должны вызывать стресса, за исключением того, что у вас есть более 100 тысяч баллов. Манипуляции с DOM - обычно самое дорогое место

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

Вот его производительность по сравнению с брутфорс

Код кучи

js fiddle

Используя описанный мной метод и предварительно созданную кучу, написанную другим человеком, я сравнил наши методы. Думаю, будет тебе счастье! Он выполнял 8 586 операций в секунду по сравнению с 566 при использовании техники грубой силы!

Это моя попытка отсортировать массив точек по расстоянию до заданной точки. Насколько я понимаю, это перебор. Затем я slice массив, чтобы дать вам 10 ближайших точек.

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

На jsFiddle

Это, по крайней мере, даст вам возможность протестировать алгоритмы. А вот jsPerf для вышеупомянутого, так что вы можете добавить к нему другие подпрограммы и провести некоторые реальные сравнения производительности. .

Примечание: при этом не учитывается, что Земля - ​​сфера! Это вычисляет Euclidean distance, а не геодезическое расстояние. Это нормально, если точки находятся, например, в одном городе (или в непосредственной близости), но не в том случае, если они находятся в разных странах / континентах. Также предполагается, что вы преобразовали долготу и широту в десятичное представление.

В противном случае вам нужно будет посмотреть на такие вещи, как Great-circle distance и _ 5_

Фактически, Земля имеет очень немного эллипсовидную форму; использование сферической модели дает обычно ошибки до 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));

На jsFiddle