圆形区域中的查询点 [英] Query points in circle areas

问题描述

以下是说明问题的图片:

Here is a picture to illustrate the problem:

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

In the picture there are some feature points shown as blue crosses. I know the coordinate (x,y) for all of the features. Now I want to query which features are inside the circle area (green circle). In practice, there are around 500 features and 300 queries (300 different circles, different centers and radius). I know the parameters (position, radius) of circles. Is there any good algorithm which can do this task?

目前，我有两个想法.

1. 最愚蠢的一个，只需遍历每个中的所有功能 询问.这比较慢.
2. 一个粗略的主意.将整个图片分离为一些子图片.根据子图片将特征放入树形结构中，如果特征在同一子图片中，则放入相同的叶子中.在每个查询中，找出圆覆盖了哪些子图片，并检查这些子图片中的所有特征.

1. Most stupid one, just iterate through all of the features in each query. This is slower.
2. A rough idea. Separate the whole picture to some sub-pictures. Put features into a tree structure according to sub-pictures, if features in the same sub-pictures, then put in the same leaf. In each query, find out which sub-picture are covered by the circle and check all of the feature in these sub-pictures.

外面有人有更好的主意吗?

Does anyone out there have any better ideas?

推荐答案

最常见的方法是将这些点放入KD树或类似的树中:

The most common way is to put the points into a K-D tree or similar: https://en.wikipedia.org/wiki/K-d_tree

要查找圆内的点，请按距中心的距离增加的顺序获取点列表，并在距离超过圆半径时停止.

To find the points within a circle, you get the list of points in order of increasing distance from the center, and stop when the distance exceeds the circle radius.

要按距离增加的顺序获取点列表，可以使用优先级队列，该队列可以同时容纳点和树的内部节点，从而可以按距离顺序将其删除.

To get list of points in order of increasing distance, you can use a priority queue that can hold both points and internal nodes of the tree, which lets you remove them in order of distance.

对于点(叶)，距离只是点到中心点的距离.对于内部节点，该距离是从中心点到该节点中可能存在的任何点的最小距离.

For points (leaves), the distance is just the distance of the point from the center point. For internal nodes, the distance is the smallest distance from the center point to any point that could possibly be in that node.

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

To search, you just put the root of the tree in the priority queue, and repeat:

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

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

This will produce all the points in the tree in order of increasing distance from the center point.

这篇关于圆形区域中的查询点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！