查询圆区域中的点
查询圆区域中的点
提问于 2018-06-05 19:42:55
这里有一张图片来说明这个问题：
在图片中，有一些特征点显示为蓝色十字。我知道所有功能的坐标(x,y)。现在我想查询哪些特征在圆区域内(绿色圆)。在实践中，大约有500个特征和300个查询(300个不同的圆，不同的中心和半径)。我知道圆的参数(位置、半径)。有没有好的算法可以完成这个任务？
目前我有两个想法。
- 最愚蠢的一个，就是遍历每个查询中的所有特征。这更慢。
- 是一个粗略的想法。将整个图片分成几个子图片。根据子图片将特征放入树结构中，如果特征在相同的子图片中，则将其放入相同的叶子中。在每个查询中，找出圆圈覆盖了哪些子图片，并检查这些子图片中的所有要素。
有没有人有更好的主意？
回答 1
Stack Overflow用户
发布于 2018-06-06 00:41:50
最常见的方法是将点放入K-D树或类似的树中：https://en.wikipedia.org/wiki/K-d_tree
要查找圆内的点，请按距圆心的距离递增的顺序获得点的列表，并在距离超过圆半径时停止。
要按距离递增的顺序获得点的列表，您可以使用优先级队列，该队列可以同时包含点和树的内部节点，这允许您按距离的顺序删除它们。
对于点(叶子)，距离就是点到中心点的距离。对于内部节点，距离是从中心点到可能位于该节点中的任何点的最小距离。
要进行搜索，只需将树的根放入优先级队列，然后重复：
- 删除优先级队列的头；
- 如果队列头是一个点，则它是树中尚未返回的最近点。您知道这一点，因为如果任何内部节点可能有一个更近的点，那么它将首先从优先级队列返回；
- 如果队列的头部是内部节点，则将其子节点放回到队列
中
这将按照与中心点的距离递增的顺序生成树中的所有点。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50699240
复制相关文章
相似问题