我正在开发一个模拟程序。这里有成群的动物（牛羚），在那群动物中，我需要能够找到一种远离牛群的动物。
在下面的图片上，绿点远离牛群。我希望能很快找到这些要点。
当然，有一个简单的算法来解决这个问题。数一数每个点附近的点数，然后如果该邻域是空的（其中0个点），那么我们知道该点远离羊群。
问题是这个算法根本没有效率。我有一百万个点，在一百万个点上应用这个算法是非常缓慢的。
有更快的吗？也许用树？
编辑@amit：我们想避免这种情况。左角的一组绿点会被选中，尽管它们不应该被选中，因为它不是一只远离牛群的动物，而是一群动物。我们只想找一只远离牛群的动物（不是一群）。
最佳答案
对于近邻查询，通常使用kd树。这将导致o（n logn）查询（一个查询在log（n）乘以n个查询中，构建kd树本身在o（n logn）中），我可以看到它在几百万个点上运行得非常快，而且有些库已经相当高效了（例如ANN）。
此外，ANN代表“近似最近邻”，并且当不需要精确距离时，可以更快。因为在您的情况下，您只想检测第一个最近邻距离是大是小，所以您可以设置一个相当高的阈值，这将使事情更快。
由此，您可以确定到每个最近邻居的距离分布，并找到异常值。对所有这些距离进行排序以确定异常值再次出现在o（n logn）中。
关于algorithm - 快速找到远离人群的动物的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14053456/