如何有效计算JavaScript中最近的2D点？

我有一组位置，我想根据它们当前的坐标以接近顺序（最接近最远）显示给用户。假设我们有大约100个包含每个经纬度（在某种对象或数组中）的位置的数据点，并且我们知道用户的lat和long。我们的目标是显示一个有序的位置列表 - 如果我们可以在计算出最接近的8-10个位置并向用户显示时显示剩余的距离，这将是有益的。如何有效计算JavaScript中最近的2D点？

我知道蛮力解决方案是循环遍历所有位置，计算与用户的距离，将它们按顺序排列，然后将它们全部显示给用户。但是这太慢了。

更好的解决办法是这样的一个：https://stackoverflow.com/a/2466908/1766230，你有界框内首先检查，扩大如有必要，然后做休息。

我也看到有其他算法 - 例如FLANN和other methods - 但我还没有看到任何用JavaScript编写的例子。

所以问题：什么是最快的方式来计算（并按顺序显示）JavaScript中的最近点？

来源

2014-03-06 Luke

约100个点，这是不可能的，你会看到很多，如果有的话，“分的利益，征服“方法而不是”天真（蛮力）“方法。天真的方法很容易实现。 – Xotic750

它实际上是使用Titanium的移动应用程序。必须做更多的挖掘才能知道为什么现在似乎是这样一个瓶颈......但是无论如何，如果它不是太困难，而不是蛮横暴力，我想找到最佳解决方案。 – Luke

根据我的理解，“分而治之”的方法是最优的O（n log n） - 取决于排序算法（我认为需要合并排序） – Xotic750

所以，如果你开始接触点的该列表，画一个小的边界框不会减少很多，因为你还是做一个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; 
}));

Here is the performance for it compared to bruteforce

Heap Code

js fiddle

使用我所描述的方法，以及预建堆另外一个人写的，我比较我们的方法。我想你会很开心！它在强力技术中执行了8,586次操作/秒，而566次操作！

来源

2014-03-06 21:03:36

您能详细说明最大长度堆解决方案吗？这是否仍然需要在显示最接近的8-10之前搜索所有位置？ – Luke

因此，除非您有服务器为您处理某些过滤，否则无法通过x点搜索。然而，这是做什么，而不是排序'n'的条款，你保持说，堆的长度为10.最大的元素是在顶部，W/E你检查另一个值，你比较它。如果您的电流小于最大值，请将其添加到堆中（如果已填充），请将顶部关闭。如果它更大，就去下一个元素。从根本上说，你不能真的不检查所有这些，所以这应该是及时获得前10个元素的好方法！ –

这在技术上与维护排序列表的情况大致相同，但平均值应该大大提高，尤其是， @更大的值。希望这可以更深入地解释一切！让我知道如果我可以有更多的帮助：D –

嗯，这是我的距离排序点的数组给定点的尝试。据我所知，这是蛮力。然后我给这个数组给你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

来源

2014-03-08 09:07:23 Xotic750

如何有效计算JavaScript中最近的2D点？

回答

相关问题