Как да изчислим ефективно най-близките 2D точки в JavaScript?

Така че, ако започвате с този списък от точки, рисуването на малка ограничителна кутия няма да намали много, защото все пак правите O(n) проверка спрямо всички точки за тяхното местоположение.

Бих посъветвал да използвате купчина с максимална дължина или някаква друга форма на частично сортиране, докато итерирате през всички точки. Това ви позволява да следите малко подмножество от приблизително максимални/минимални точки (както е описано от дължината), така че можете да ги изобразите бързо, преди да се занимавате с останалите. Ако имате нужда от повече обяснения за това, което точно казвам, уведомете ме.

Освен това за какво правите това, което има толкова строги проблеми с производителността? Обикновено изчисление като това не трябва да бъде точка на стрес, освен че имате 100k+ точки. Манипулирането на 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;
}));

Ето производителността за него в сравнение с груба сила

Heap код

js fiddle

Използвайки метода, който описах, и предварително изградена купчина, написана от друг човек, сравних нашите методи. Мисля, че ще бъдете щастливи! Той изпълни 8586 операции в секунда в сравнение с 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 и Haversine formula

Всъщност земята е много леко елипсоидална; използването на сферичен модел дава грешки обикновено до 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