是否有快速的Python算法来查找数据集中位于给定圆中的所有点？

Question

我有大量数据（超过10E5）。我正在搜索一种快速算法，该算法可计算数据集中的所有点，对于给定点（圆心）和半径，它位于一个圆中。

我考虑过使用KDTree计算例如10个最近的点，然后检查它们是否在圆内。但是我不确定这是否正确。

Answer 1

要检查点(a, b)是否在中心(x, y)和半径r的圆内，则可以简单地进行计算：

within_circle = ((x-a)**2 + (y-b)**2) <= r*r)

此等式使用圆的属性，在该属性上可以获取到点的绝对距离（如果您注意到，在距离公式中也使用了该绝对距离）。

Answer 2

诸如k-d树或四叉树的空间分区数据结构可以准确回答您的查询；不需要像“ 10个最近的点”之类的启发式方法。

您可以递归搜索树：

1. 如果当前节点的边界矩形根本不与圆相交，则忽略它。
2. 否则，如果当前节点的边界矩形完全包含在圆内，请返回其中的所有点。
3. 否则，如果当前节点的边界矩形与圆部分重叠：
   • 如果当前节点是叶子，则分别测试每个点以查看其是否在圆内。
   • 否则，递归当前节点的子节点。

对于第2步，当且仅当矩形的四个角均相等时，矩形才完全包含在圆中。对于步骤1和3，您可以测试矩形是否与圆的边界框相交，然后保守地递归，因为矩形might与圆的相交；或者，您也可以在矩形和实际圆之间进行an exact（但要慢一些）的检查。

Answer 3

[如果您想先过滤大量数据集而不进行大量计算，则可以使用大小为平方（2r x 2r）的平方，且其中心与圆相同（其中r是圆的半径）。

看看这张照片：

如果具有中心坐标（a，b）且r为半径，则正方形内的点（x，y）进行验证：

a-r < x < a+r
b-r < y < b+r

最后在此过滤器之后，您可以应用圆方程：

(x-a)**2 + (y-b)**2 < r**2