这里有一张图片来说明这个问题:
在图片中,有一些特征点显示为蓝色十字。我知道所有功能的坐标(x,y)
。现在我想查询哪些特征在圆区域内(绿色圆)。在实践中,大约有500个特征和300个查询(300个不同的圆,不同的中心和半径)。我知道圆的参数(位置、半径)。有没有好的算法可以完成这个任务?
目前我有两个想法。
有没有人有更好的主意?
发布于 2018-06-06 00:41:50
最常见的方法是将点放入K-D树或类似的树中:https://en.wikipedia.org/wiki/K-d_tree
要查找圆内的点,请按距圆心的距离递增的顺序获得点的列表,并在距离超过圆半径时停止。
要按距离递增的顺序获得点的列表,您可以使用优先级队列,该队列可以同时包含点和树的内部节点,这允许您按距离的顺序删除它们。
对于点(叶子),距离就是点到中心点的距离。对于内部节点,距离是从中心点到可能位于该节点中的任何点的最小距离。
要进行搜索,只需将树的根放入优先级队列,然后重复:
中
这将按照与中心点的距离递增的顺序生成树中的所有点。
https://stackoverflow.com/questions/50699240
复制相似问题