algorithm - 如果在圆圈内，则选择点的子集

Question

想象一下像10M订单这样的很多点。

现在我在给定的空间中随机画一个圆圈。

这个圆现在将根据中心和半径包围一些点。

现在，我想选择这个圆圈内的所有点。

蛮力方法非常低效。

有没有更好的方法来解决这个问题。

PS-我正在用python编码。

谢谢

编辑：蛮力方法：

从空间中选择一个点，计算到中心的距离，如果它小于半径，那么它在里面，否则在外面。

蛮力是，我必须遍历所有点，这是有问题的，因为在下一次迭代中，我将再次随机选择一个点并重复上述步骤。所以这就像 O(n^2)..我能做得更好吗？

Answer 1

在一些空间划分结构中预先安排点。

例如，四叉树。遍历树。由于每个节点对应于平面上的一个正方形，您可以快速检查该正方形是否与您的圆相交（在圆内至少有一个角或圆完全在正方形内）。如果确实相交，则继续向下遍历该节点，如果不相交，则跳过其所有子节点，从而可能消除对该正方形中点的大量单独检查。