algorithm - 圆形区域内的查询点

Question

下面用一张图来说明问题:

图中有一些特征点显示为蓝色十字。我知道所有特征的坐标(x,y)。现在我想查询哪些要素在圆圈区域(绿色圆圈)内。实际上，大约有 500 个特征和 300 个查询(300 个不同的圆、不同的中心和半径)。我知道圆的参数(位置、半径)。有什么好的算法可以完成这个任务吗？

目前我有两个想法。

1. 最愚蠢的一个，只是迭代每个中的所有功能 询问。这比较慢。
2. 一个粗略的想法。将整个图片分成一些子图片。将特征按照子图放入树结构中，如果特征在同一子图中，则放入同一叶子。在每个查询中，找出哪些子图片被圆圈覆盖，并检查这些子图片中的所有特征。

有人有更好的想法吗？

Answer 1

最常见的方法是将点放入 K-D 树或类似的树中:https://en.wikipedia.org/wiki/K-d_tree

要查找圆内的点，您可以按照距中心距离递增的顺序获取点列表，并在距离超过圆半径时停止。

要按距离递增的顺序获取点列表，您可以使用优先级队列，该队列可以保存点和树的内部节点，这样您就可以按距离顺序删除它们。

对于点(叶子)来说，距离就是该点到中心点的距离。对于内部节点，该距离是从中心点到该节点中可能存在的任何点的最小距离。

要进行搜索，只需将树的根放入优先级队列中，然后重复:

1. 移除优先级队列的头部；
2. 如果队列的头部是一个点，那么它是树中尚未返回的最近的点。你知道这一点，因为如果任何内部节点可能有更接近的点，那么它就会首先从优先级队列中返回；
3. 如果队列头是内部节点，则将其子节点放回队列中

这将按照距中心点距离递增的顺序生成树中的所有点。