什么是计算最近点的有效方法？

我有位置数据存储在Core Data中的对象，我希望能够获取并显示与当前位置最近的点。我知道有些公式会计算从当前纬度/经度到存储纬度/经度的距离，但我很好奇最好的方式来对存储在核心数据中的一组1000+点执行此操作。我知道我可以将核心数据中的点返回给一个数组，然后循环遍历那些寻找点间距离的最小值，但我想可能会有更高效的方法，可能以某种方式利用核心数据。什么是计算最近点的有效方法？

任何有识之士将不胜感激。

编辑：我不知道我是如何在初始搜索时错过的，但this SO question建议只是遍历核心数据对象的数组，但使用基于当前位置的边界框限制数组大小。这是我能做的最好的吗？

来源

2010-03-11 conorgriffin

使用边界框听起来很合理，应该很快得到第一组点，如果猜测是好的，不需要迭代太多。技巧是猜测正确的盒子大小，我想你可以从一个小的开始，并通过某个因子增加它的高度和宽度，直到找到多个点，然后开始迭代。 – Douglas 2010-03-11 09:23:19

我认为[this]（http://en.wikipedia.org/wiki/Voronoi_diagrams）可以帮助你。 – user272879 2010-03-11 09:02:17

据我所知，它看起来好像在这种情况下，最好的办法是返回一个数组使用当前位置周围的边界框的点数。

如果返回的数组为空，则可以检索当前位置的某个范围内的点，然后增加框的大小。一旦某些结果回来，计算数组中最近的并使用该点。

来源

2010-03-18 00:39:34 conorgriffin

我不知道很多关于核心数据，但也有好喜欢Quadtree已知的算法来解决这个问题

来源

2010-03-11 08:54:27

什么你正在做被称为Nearest neighbor search并具有描述方法用于计算一个维基百科条目它。我认为这是一个良好的开端作为每个方法的复杂性是国家，所以你可以衡量如何实施将如何:)

到NNS 问题最简单的办法是从查询计算距离复杂指向数据库中的每个其他点，保持跟踪 “迄今为止最好的”。这种算法，有时被称为幼稚方法中，具有（ND）O的运行时间

局部性敏感散列（LSH）是用于分组在空间点分成基于一些距离“桶”一个技术度量在点上运行。这是在所选指标的彼此靠近点被映射到相同的桶高概率

来源

2010-03-11 09:13:15

什么是计算最近点的有效方法？

回答

相关问题