给定一组的几百万点x，y坐标，什么是选择用于快速地从一个位置找到顶端1000最近点的算法？ 快在这里是指一台家用电脑上的约100毫秒。

Given a set of several million points with x,y coordinates, what is the algorithm of choice for quickly finding the top 1000 nearest points from a location? "Quickly" here means about 100ms on a home computer.

蛮力将意味着数以百万计做乘法，然后对它们进行排序。而即使是一个简单的Python应用程序可以做到这一点，在不到一分钟，它仍然太长的交互式应用程序。

Brute force would mean doing millions of multiplications and then sorting them. While even a simple Python app could do that in less than a minute, it is still too long for an interactive application.

有该点的边界框将已知的，所以将所述空间分隔成一个简单的网格将是可能的。然而，点分布不均匀有点，所以我怀疑大多数方格将是空的，然后突然他们中的一些将包含点了一大截。

The bounding box for the points will be known, so partitioning the space into a simple grid would be possible. However the points are distributed somewhat unevenly, so I suspect most grid squares would be empty and then suddenly some of them would contain a large portion of the points.

编辑：没有确切的说，其实可以说是相当不准确的。它不会是一个巨大的交易，如果顶部1000实际上是从顶部2000例如只是一些随机点。

Does not have to be exact, actually can be quite inaccurate. It wouldn't be a huge deal if the top 1000 are actually just some random points from the top 2000 for example.

编辑：设置点很少改变

推荐答案

如何使用四叉树？

您划分区域以矩形，如果区域具有点的密度低，矩形是大的，并且如果区域具有点的高密度，矩形将是小的。你递归细分每个矩形四个子矩形，直到矩形是足够小或者几乎不包含足够的分数。

You divide area to rectangles, if area has low density of points, rectangles are large, and if area has high density of points, rectangles will be small. You recursively subdivide each rectangle to four sub rectangles until rectangles are small enough or contain few enough points.

您可以开始寻找点附近的位置矩形，并向外移动，直到你找到了你1000点。

You can then start looking at points in rectangles near the location, and move outwards until you have found your 1000 points.

$ C $下这有可能会有些复杂，所以也许你应该首先尝试用简单的网格，看看它是否足够快。

Code for this could get somewhat complex, so maybe you should try first with the simple grid and see if it is fast enough.